학습 철학 회고
단방향으로 이동하는 '애벌레' 투 포인터에 이어, 정렬된 배열에서 양끝에서 마주 보며 좁혀오는 '양끝 교차 투 포인터'의 뼈대를 세웠습니다. 특히 "왜 지나온 포인터를 다시 되돌려보지 않아도 모든 경우의 수를 보장하는가?"에 대한 수학적 의심을 품고, 탐색 공간이 소거되는 원리를 완벽하게 논리적으로 증명해 냈습니다.
📌 개념 요약: 양끝 교차 투 포인터 (Meeting in the Middle)
오름차순으로 정렬된 1차원 배열에서 두 개의 포인터(left, right)를 각각 양끝(인덱스 0과 N-1)에 배치하고, 서로를 향해 좁혀오며 원하는 타겟을 찾는 알고리즘입니다. 주로 '두 수의 합'을 구할 때 강력한 위력을 발휘하며, 의 시간 복잡도를 단 한 번의 스캔인 으로 압축합니다.
💻 추상화된 템플릿 코드
정렬된 배열에서 두 수의 합이 target_sum이 되는 쌍의 개수를 찾는 순수 뼈대입니다.
def two_pointers_opposite_template(arr, target_sum):
"""
:param arr: 오름차순으로 '정렬된' 1차원 배열
:param target_sum: 찾고자 하는 두 수의 합
"""
count = 0
left = 0
right = len(arr) - 1
# 두 포인터가 교차하기 전까지 반복 (같은 원소를 두 번 고를 수 없으므로 < 사용)
while left < right:
current_sum = arr[left] + arr[right]
# 1. 정답을 찾은 경우
if current_sum == target_sum:
count += 1
# 다른 쌍을 찾기 위해 두 포인터 모두 안쪽으로 좁힘
left += 1
right -= 1
# 2. 합이 타겟보다 작은 경우 -> 값을 키워야 하므로 left를 오른쪽으로
elif current_sum < target_sum:
left += 1
# 3. 합이 타겟보다 큰 경우 -> 값을 줄여야 하므로 right를 왼쪽으로
else:
right -= 1
return count🚨 [핵심 회고] 탐색 공간의 소거: 우리는 왜 뒤돌아보지 않는가?
투 포인터를 공부할 때 가장 큰 의문은 이것이었습니다.
"합이 목표보다 크거나 작아서 포인터를 한쪽으로 이동시켰다면, 반대쪽 포인터를 과거로 되돌려서 다시 조합해 봐야 모든 경우의 수를 다 확인하는 것 아닌가?"
이 의문에 대해 치열하게 고민한 결과, 다음과 같은 '탐색 공간 소거의 절대 법칙'을 깨달았습니다. 투 포인터가 지나온 길을 미련 없이 버릴 수 있는 이유는, 직접 더해보지 않아도 결과를 100% 확신할 수 있기 때문입니다.
💡 나의 깨달음: 투 포인터 소거의 미학
합이 목표보다 작을 때
left가 오른쪽으로 이동하며 사라지는 이유:
유효한 원소들 중 가장 큰 값(right)과 더해졌는데도 목표보다 작았다면, 앞으로 만날 그 어떤 더 작은right값들과 더해봐야 어차피 무조건 작을 것이 수학적으로 확실하기 때문이다. 따라서 해당left는 영구 폐기된다.합이 목표보다 클 때
right가 왼쪽으로 이동하며 사라지는 이유:
유효한 원소들 중 가장 작은 값(left)과 더해졌는데도 목표보다 컸다면, 앞으로 만날 그 어떤 더 큰left값들과 더해봐야 어차피 무조건 클 것이 수학적으로 확실하기 때문이다. 따라서 해당right는 더 이상 볼 필요 없이 영구 폐기된다.
이중 for문이 무식하게 모든 것을 다 계산해보는 방식이라면, 투 포인터는 정렬의 성질을 이용해 "안 해봐도 오답인 걸 아니까 전체 경우의 수를 통째로 날려버리는" 극강의 지능적인 알고리즘이라는 것을 완벽히 체화했습니다.
