두포인터2 [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++] 백준 2470: 두 용액 (두 포인터) https://www.acmicpc.net/problem/2470문제 이해하기 문제의 요구사항은 다음과 같습니다.두 용액을 조합하여 특성합이 0에 가장 가까운 조합을 구하여라.시간복잡도 어림하기브루트 포스 알고리즘 한 용액에 대해 가능한 모든 특성합을 구하는 알고리즘은 O(n^2)의 시간복잡도를 가집니다. 문제에서 n의 최댓값은 100,000이므로 10,000,000,000의 시간복잡도를 가집니다. 이는 제한 시간 내에 문제를 해결하기 어려운 수치입니다. DP 알고리즘 DP 알고리즘을 사용해도 합이 0에 가까운 두 용액을 찾기 위해서는 O(n^2)의 시간복잡도를 가지므로 DP 알고리즘도 사용할 수 없습니다. 이분 탐색, 두 포인터 알고리즘 이 문제는 합이 0에 가까운 두 용액을 구하는 것입니다. 여기서.. 2024. 5. 12. 이전 1 다음