알고리즘/백준

문제 풀이 이분 탐색을 사용한다. 나눠줄 보석의 수를 이분 탐색하여 진행한다. 보석은 최소 1개 나눠줄 수 있고, 최대 가장 수가 많은 보석의 수만큼 나눠줄 수 있다. 보석마다 mid만큼 나눠준다면 (현재 보석의 수 / mid)만큼의 학생에게 나눠줄 수 있으며, 나눠준 후 보석이 남았다면 1명의 학생에게 추가적으로 나눠줄 수 있다. mid만큼 보석을 나눠줬을 때, 나눠줄 수 있는 학새의 수와 N을 비교하여 다음 이분 탐색의 범위를 새로 한다. 질투심은 mid만큼 나눠줬을 때의 mid가 해당 검사에서의 최댓값이다. 코드 #include #include #include using namespace std; vector jewels; int main() { ios_base::sync_with_stdio(0);..

문제 풀이 이분 탐색 사용 조각을 하나 선택하고 나머지 조각의 길이가 (필요한 길이 - 선택한 조각 길이)라면 문제에 만족된다. 선택한 조각과 맞는 조각을 찾을 때 이분 탐색을 실시한다. 두 포인터 사용 양 옆에서부터 좁혀가며 검사한다. start와 end에서의 조각의 길이의 합이 필요한 길이와 같다면 문제에 만족된다. 코드 이분 탐색 사용 #include #include #include using namespace std; vector legos; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int x, n; while (cin >> x >> n) { x *= 10'000'000; for (int i = 0; i <..

문제 풀이 이분 탐색을 사용한다. 최악의 경우는 각 동물이 모든 사로에 대해 사냥이 가능한지 검사하는 것으로 O(N * M)으로 100억번의 탐색이 이루어져 시간초과이다. N이나 M 중 하나를 log로 바꿔야 한다. 각 동물마다 이분 탐색으로 해당 사대에서 사냥 가능한지 검사한다. 시간 복잡도가 O(N * log M)으로 줄어든다. 동물이 mid 사대의 왼쪽에 있다면 end를 감소시키고, 오른쪽에 있다면 start를 증가한다. 코드 #include #include #include using namespace std; vector shoots; vector animals; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); i..

문제 풀이 모든 합을 저장하여 이분 탐색으로 진행할 경우, 자기 자신이 합에서 사용되었는지 알 수 없기에 사용할 수 없다. unordered_map 사용 모든 합을 피연산자와 함께 unordered_map에 저장한다. input이 unordered_map에 있는지 확인하고, 피연산자로 자기 자신이 사용되었는지 확인한다. 두 포인터 사용 입력된 수열을 정렬하고 양 옆에서 두 포인터 알고리즘을 시작한다. 같은 수가 합에 사용되면 안 되므로 start < end일 때까지만 반복한다. 자기 자신은 합에 포함되면 안 되므로 start와 end를 조정 코드 unordered_map 사용 #include #include #include #include using namespace std; vector inputs; ..

문제 풀이 이분 탐색을 사용한다. 석순과 종유석의 길이를 이분 탐색한다. 석순의 길이가 날아가는 높이 i 이하이면 부서진다. 종유석의 (H - i) 초과라면 부서진다. 석순과 종유석의 길이를 정렬하고 i일때 부서지는 구간의 길이를 vector로 보관한다. vector[0] 값의 구간의 길이가 장애물이 최소인 구간의 수이다. 코드 #include #include #include using namespace std; vector lower; vector high; vector destroyed; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int N, H; cin >> N >> H; for (int i = 0; i < N..

문제 풀이 이분 탐색을 사용한다. 블루레이의 크기를 이분 탐색하며 최소를 구한다. 블루레이 크기의 최솟값은 lesson 중 가장 긴 시간이다. (start) 블루레이 크기의 최댓값은 lesson 시간의 총 합이다. (end) mid 만큼 블루레이 크기를 설정하였을 때, 만들어지는 CD의 수가 M이하라면 answer를 갱신하고 블루레이 시간을 줄인다. M을 초과했다면 블루레이 시간을 늘린다. 코드 #include #include #include using namespace std; vector lessons; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int N, M; cin >> N >> M; int total_ti..

문제 풀이 이분 탐색을 사용한다. 현재 만들 수 있는 최소 레벨은 입력받은 레벨 중 가장 낮은 레벨이다. 이 값을 start로 설정한다. 현재 만들 수 있는 최대 레벨은 입력받은 레벨 중 가장 높은 레벨 + K이다. 이 값을 end로 설정한다. mid = (start + end) / 2로 설정한다. mid보다 낮은 레벨들을 mid까지 올렸을 때 필요한 레벨이 K 이하일 경우 정답을 갱신하고, start를 mid + 1로 변경한다. 초과일 경우 end를 mid - 1로 변경한다. 코드 #include #include #include using namespace std; vector levels; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.ti..

문제 풀이 이분 탐색을 사용한다. 공유기를 설치할 간격을 이분 탐색으로 좁혀서 진행한다. 집의 좌표를 오름차순으로 정렬한다. 공유기를 설치할 수 있는 최소 간격과 최대 간격을 구한다. 최소 간격: 집 사이의 최소 거리인 1 최대 간격: 마지막 집과 처음 집 사이의 거리 설치할 간격을 이분 탐색으로 좁혀서 진행한다. 첫 집은 무조건 설치한다. 설치할 간격인 mid만큼 거리를 벌려서 공유기를 설치했을 때, 설치한 공유기의 수가 C이상인 경우 간격을 늘리고, 미만인 경우 간격을 줄인다. 설치한 공유기 수가 C를 만족한 경우 답을 갱신한다. 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); ci..

문제 풀이 다이나믹 프로그래밍 문제다. 모든 단계에서 모든 발의 위치의 최솟값을 cache로 담는다. 현재 단계를 검사할 때, 이전 단계의 cache를 사용한다. 이전 단계에서 발의 위치가 존재할 수 없는 것은 제외한다. 이전 단계에서 왼발/오른발을 현재 옮겨야 하는 위치로 옮겼을 때의 비용의 최솟값을 cache로담는다. 왼발을 움직이는 경우 cache[현재 단계][현재 옮겨야 하는 위치][오른발] = min( cache[현재 단계][현재 옮겨야 하는 위치][오른발], cache[이전 단계][이전 왼발의 위치][오른발] + (이전 왼발발에서 현재 옮겨야 하는 위치로의 비용) ) 오른발을 움직이는 경우 cache[현재 단계][왼발][현재 옮겨야 하는 위치] = min( cache[현재 단계][왼발][현재 ..

문제 풀이 방향 비순환 그래프와 위상 정렬 알고리즘을 사용한다. B를 거치기 위해서는 무조건 A가 먼저 거쳐야 한다. B의 indegree가 증가하고, A의 outdegree가 B로 저장된다. indegree가 0인 학생부터 queue에 넣는다. queue에서 나온 학생의 outdegree에 해당하는 학생의 indegree를 1차감한다. indegree가 0이 되면 queue에 넣는다. 코드 #include #include using namespace std; int indegree[32001]; vector outdegree[32001]; vector path; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int N..