📶 백준 2470번 : 두 용액 (이분 탐색 활용)
🧐 문제 해석
- 산성 또는 알칼리성의 n개의 용액이 주어진다.
🎯 목표:
- 특성값의 합이 가장 0에 가까운 두 용액을 특정한다.
🔍 핵심 아이디어 및 자료구조 & 알고리즘
💭 아이디어
모든 용액에 대해서 특성값의 합이 최소인 두 용액을 찾아내기 위해서는 결국 모든 조합을 고려해야 한다는것이다. 브루트포스, 이분탐색, 조합 등 탐색을 위한 방식만 결정하면 되는 문제이다.
🤖 자료구조 & 알고리즘
시간복잡도를 최소화할 수 있는 알고리즘을 찾아야 했다.
또한 양수/음수가 존재하기 때문에 0에 가까운 절대값을 갖는 조합을 위해서는 결국 양수를 증가/감소 하면서 음수도 증가/감소 해야한다. 그럼 특성값을 기준으로 정렬한 배열에서 왼쪽 끝과 오른쪽 끝을 이용해서 포인터를 이동시키는 방식이 적절하다고 생각했다.
⁉️ 투 포인터 vs 이분탐색
해당 문제는 이분탐색/투포인터로 분류가 되어 있었다.
🔹 이분 탐색 (Binary Search)
- 아이디어: 정렬된 구간에서 중간(mid) 값을 기준으로 절반을
버리며 범위를 좁힌다. - 탐색 방식: 매 단계마다 탐색 범위를 절반으로 줄인다.
- 시간복잡도:
O(log n)
🔹 투 포인터 (Two Pointers)
- 아이디어: 정렬된 배열(혹은 특정 조건)을 활용해 양 끝에서
시작하거나, 두 개의 포인터를 움직이며 탐색한다. - 탐색 방식: 포인터를 하나씩 이동 → 전체 배열을 한 번 훑는다.
- 시간복잡도: 보통
O(n)
📌 공통점 & 차이점
공통점
정렬 구조를 전제로 한다.
탐색 범위를 줄이면서 효율적으로 답을 찾는다.
선형 탐색보다 훨씬 빠르다.
차이점
시간복잡도: log n vs n
접근 방식: mid로 반을 날림 vs 포인터를 조건에 맞게 이동
🚩 결론
- 투 포인터와 이분 탐색은 같은 개념이 아니다.
- 다만, 둘 다 "정렬된 배열에서 범위를 줄이는 탐색" 이라는 점
때문에 "이분 탐색 계열" 카테고리에 묶이기도 한다. - 두 용액 문제는 사실상 투 포인터 문제이고, 이분 탐색 풀이도
가능하지만 시간복잡도를 고려했을때 최적의 선택은 아니다.
⚙️ 코드 설계 포인트
point 1
s = arr[L] + arr[R]
if abs(s) < abs(best):point 2
if s > 0:
R -= 1
else:
L += 1🔑 특성값의 차이
- 특성값의 합이 양수를 갖는다 = 양수의 절대값이 더 크다 = 양수를 줄여서 최적값을 탐색해야 한다
- 특성값의 합이 음수를 갖는다 = 음수의 절대값이 더 크다 = 음수를 키워서 최적값을 탐색해야 한다
💯 정답 코드
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
best = float('inf')
L, R = 0, n - 1
ans_l, ans_r = arr[L], arr[R]
while L < R:
s = arr[L] + arr[R]
if abs(s) < abs(best):
best = s
ans_l, ans_r = arr[L], arr[R]
if s == 0:
break
if s > 0:
R -= 1
else:
L += 1
print(ans_l, ans_r)
💭 생각
⁉️ 최적화 포인트
산성 또는 알칼리성만 있는 경우는 정렬 결과의 왼쪽 끝 또는 오른쪽 끝의 양수, 음수 여부를 보고 알 수 있고 두 케이스는 비교할 필요 없이 한쪽끝에서 2개의 값을 더한게 최솟값일 것이다.
if(ans_l>=0):
print(arr[0], arr[1])
sys.exit()
if(ans_r<=0):
print(arr[-2], arr[-1])
sys.exit()- 시간복잡도 : 108ms -> 96ms
특수한 케이스에 대한 최적화이기 때문에 효과가 좋은 것 같지는 않다.
⭐️ 중요
처음에 문제를 보고 이분탐색이라는 키워드에 꽂혀서 무조건 mid를 사용해서 탐색의 범위를 반으로 좁혀 나가야 된다는 생각에 박혀있다보니
- 양수와 음수를 나눈뒤에 각각 투포인터를 써야 하나?
- mid를 도대체 무슨 의미로 써야 하나?
등의 생각에 사로잡혀있었다.
결국 이 문제는 탐색 범위를 좁혀 나간다는 것 뿐 직접적으로 mid를 쓰는 것이 좋은 문제는 아니었던 것이다..
다음부터는 키워드에 너무 강박을 갖지말자 😭
