본문 바로가기

분류 전체보기

 (54)
[C++][프로그래머스] 외벽 점검 - 완전탐색 문제 https://programmers.co.kr/learn/courses/30/lessons/60062 풀이 외벽 점검을 위해 최소로 투입해야 하는 친구의 수를 구하는 문제였습니다.dist의 크기가 1 이상 8 이하로 매우 작기 때문에 완전탐색 방식으로 풀었습니다. dist가 [1, 2, 3, 4]와 같을 때길이 4를 이동할 수 있는 친구를 1명 투입해보고 모든 취약점 점검이 불가능하다면 추가로 길이 3을 이동할 수 있는 친구를 1명 투입해보고 모든 취약점 점검이 불가능하다면 추가로 길이 2를 이동할 수 있는 친구를 1명 투입해보는 작업을 모든 취약점 점검이 가능할때까지 반복하였습니다. 1단계에서 투입인원을 정하게 되면 투입인원을 배치하는 순서에 따라 모든 취약점을 커버할 수도, 커버하지 못할 수도 ..
[C++] 순열, 조합, 부분 집합 순열과 조합 - N개 중 M개를 뽑는 Case {1, 2, 3, 4, 5} 중 3개를 뽑는 Case에 대해 알아보자 순열 순서에 상관이 있고 중복을 허용하지 않고 나올 수 있는 모든 수열 #include #include #include #include using namespace std; int arr[5] = { 1, 2, 3, 4, 5 }; bool check[5]; // 중복된 값을 선택하지 않기 위한 배열 int temp[3]; // 5개 중 3개를 뽑은 순열 void dfs(int x) { if (x >= 3) { for (int i = 0; i < 3; i++) { cout
[C++][백준] 비밀 보임 (13424) - 플로이드와샬 문제 해리와 친구들은 엄브릿지의 감시를 피해 어둠의 마법 방어술을 연습하기 위한 비밀 모임을 하려고 한다. 그들은 아무도 모르게 모임의 장소를 전달하기 위해 가짜 갈레온을 사용하는데, 해리가 자신의 가짜 갈레온에 모임의 장소를 적으면 친구들이 가진 가짜 갈레온에 해리가 적은 장소가 나타난다. 해리가 다니고 있는 호그와트 마법 학교에는 모임에 사용할만한 N개의 방이 있다. 각 방에는 1부터 N까지 번호가 붙어 있으며 중복된 번호는 없다. 마법 학교답게 N개의 방은 M개의 마법으로 만들어진 비밀통로로 연결되어있다. 모든 비밀통로는 양방향 통행이 가능하며 자연수의 길이를 가진다. 모임에 참여하는 친구들은 총 K명이다. 해리는 N개의 방 중에서 한 곳을 정해 오늘 모임의 장소로 이용하려고 한다. 모임 장소를 정..
[C++][백준] 욕심쟁이 판다 (1937) - dp 문제 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 ..
[C++][프로그래머스] 메뉴 리뉴얼 - 비트마스크 완전탐색 문제 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다. 단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다. 각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 풀이 코스요리 메뉴를 구성해야합니다. 코스요리는 2가지 이상의 단품메뉴로 구성되어있으며 ..
[C++][백준] 텀 프로젝트 (9466) - 스택 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다. 예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으..
[C++][백준] 크게 만들기(2812) - 세그먼트 트리, 스택 문제 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 출력 입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다. 풀이 이 문제는 세그먼트 트리, 스택(그리디)이라는 두가지 방식을 이용하여 풀어보았습니다. 먼저 스택을 이용한 풀이 방식입니다. 199999보다 911111가 큰 수 입니다. 가장 큰 수를 얻기 위해서는 앞 자리수에 최대한 큰 수를 배치해야 합니다. 따라서 스택에 순차적으로 수를 집어넣다가 현재 스택 top보다 큰 수가 존재하는 경우 delete_cnt가 허용하는 내로 숫자를 지워가며 최대한 앞자리에 큰 수가 올 수 있도록 만들어줍니다. #include #include #include using na..
[C++][백준] 준표의 조약돌(15831) - 투포인터 문제 준표는 오랜만에 미미와 함께 산책을 나왔다. 산책로에는 일렬로 검은색과 흰색 조약돌이 놓여 있다. 총 N개의 조약돌은 1번부터 N번까지 차례로 번호가 붙여져 있다. 준표는 이 조약돌을 주워 집에 장식하려고 한다. 준표는 임의의 지점에서 산책을 시작하고, 원하는 지점에서 산책로를 빠져나와 집으로 돌아간다. 이때 준표는 산책한 구간에 있는 모든 조약돌을 줍는다. 미미의 건강을 위해 준표는 조금이라도 더 긴 구간을 산책하고 싶다. 하지만 준표에게는 확고한 취향이 있어, 아래 조건을 만족하는 구간만을 산책할 수 있다. 준표는 까만색을 싫어한다. 그래서 까만색 조약돌은 B개 이하로 줍고 싶다. 준표는 미미와 같은 흰색을 좋아한다. 그래서 흰색 조약돌은 W개 이상 줍고 싶다. 만약 위 조건을 만족하는 구간이 ..

티스토리툴바