본문 바로가기

이분탐색4

[C++] 백준 2473번 : 세 용액 (이분 탐색, 두 포인터) https://www.acmicpc.net/problem/2473문제 이해하기 문제의 요구사항은 다음과 같습니다.세 용액의 특성값의 합이 0에 가장 가까운 세 용액을 구하여라.시간복잡도 어림하기브루트포스 알고리즘 단순히 모든 경우의 수를 살펴본다면 O(N^3)의 시간복잡도가 걸립니다. 문제에서 N의 최댓값이 5000이므로 5000^3 = 125,000,000,000(1250억) 번 반복됩니다. 이는 제한시간 내에 해결하기 불가능한 수치이므로 브루트포스 알고리즘을 사용할 수 없습니다.DP 알고리즘 DP 알고리즘을 사용하기 위해 이전에 계산된 상태를 이용할 수 있어야 합니다. 이번 문제는 이전 계산 상태를 사용하여 현재 상태를 계산하기 애매한 유형이므로 DP 알고리즘을 사용하지 않습니다.이분탐색, 두 포인터.. 2024. 8. 23.
[C++] 백준 2110번: 공유기 설치 (이분 탐색) https://www.acmicpc.net/problem/2110문제 이해하기 문제의 요구사항은 다음과 같습니다.C개의 공유기를 설치할 때, 인접한 두 공유기 사이의 최대 거리를 구하여라.시간복잡도 어림하기브루트 포스 알고리즘 브루트 포스 알고리즘을 통해 가능한 모든 경우의 수를 구하기 위해서는 n개중 c개를 뽑는 조합 알고리즘이 필요합니다. 하지만 n의 최댓값은 200,000이고 c의 최댓값은 n이므로 경우의 수가 너무 많습니다. 따라서 브루트 포스 알고리즘은 적절하지 않습니다. DP 알고리즘 dp배열에 각 상태(공유기 설치 위치)를 담기 애매하고, 현재 상태를 구하기 위해 이전 상태를 사용하기 어려우므로 DP 알고리즘 역시 적절하지 않습니다. 이분탐색 알고리즘 주어진 배열을 정렬할 수 있고, 설치할 .. 2024. 6. 12.
[C++] 백준 2805번: 나무 자르기 (이분 탐색) 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 이해하기 이번 문제의 요구사항은 다음과 같습니다. 절단기 높이 H보다 높은 나무 길이 만큼 나무를 가져갈 때, 적어도 총합 M만큼의 나무를 가져가기 위한 절단기의 최대 높이를 구하여라. 시간복잡도 어림하기 브루트 포스 알고리즘 절단기의 높이에 따라 가져가는 나무의 양을 구하기 위해서는 절단기 높이 h에 대해 나무의 수인 n만큼 탐색해야해야 합니다. 이때, 높이 h는 0부터 나무의 최대 높이인 1,000,000,000까.. 2024. 3. 30.
[C++] 백준 1072번: 게임 (이분 탐색) https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 문제 이해하기 이 문제를 요약해보면 다음과 같습니다. 승률을 올리기 위해 최소 몇 게임을 더 이겨야 하는지 구하여라. 시간복잡도 어림하기 브루트 포스 알고리즘 X의 범위가 1,000,000,000으로 최대 10억까지므로 탐색 횟수도 이에 비례하여 아주 커질 것입니다. 따라서 브루트 포스 알고리즘은 적절하지 않습니다. DP 알고리즘 역시 X의 범위가 최대 10억까지이므로 필요한 값의 양이 너.. 2024. 3. 27.

티스토리툴바