PostsSeriesLabsAlgo

기초 개념

투 포인터

양쪽에서 좁혀 오기

카드는 작은 수부터 줄을 섰습니다. 합이 13 인 두 장을 찾으세요. 양끝 두 장의 합만 볼 수 있습니다

목표 13

1
3
4
6
8
10
13
왼쪽 끝오른쪽 끝

1 + 13 = 14목표 13 보다 큽니다

합을 본 횟수 1

합을 0번 보고 찾았습니다. 카드가 7장이라 모든 쌍은 21가지입니다.

1 + 13 → 1 + 10 → 3 + 10양끝만 보고 볼 때마다 카드 한 장을 버렸습니다.

모든 쌍 · 7장21번
양끝에서 좁히기 · 7장3번
같은 카드, 같은 목표. 100,000장이면 4,999,950,000번 대 99,999번까지 벌어집니다.

줄 선 카드의 양끝에서 시작해 가운데로 좁혀 가는 방법 = 투 포인터

왜 버려도 될까

  • 합이 크면 — 오른쪽 끝은 남은 카드 중 가장 작은 왼쪽 끝과 더해도 이미 크다. 짝이 없으니 버린다
  • 합이 작으면 — 왼쪽 끝은 남은 카드 중 가장 큰 오른쪽 끝과 더해도 아직 작다. 짝이 없으니 버린다
  • 그래서 — 가장 작은 카드와 가장 큰 카드가 양끝에 있어야 한다. 줄이 작은 수부터 서 있어야 한다는 뜻이다

줄이 흐트러진 [3, 9, 10, 1] 에서 목표 13 을 찾는다고 해 봅니다. 처음 합 3 + 1 = 4 는 작으니 왼쪽 3 을 버립니다. 그런데 3 + 10 = 13 이 정답이었습니다. 버리면 안 되는 카드를 버린 것입니다.

코드는 끝 두 개를 가리키는 변수 둘이 전부다

누르기 전에 맞혀 보세요. 처음 합 1 + 13 = 14 는 목표 13 보다 큽니다. 다음에 움직이는 변수는 무엇일까요?

다음을 눌러 한 줄씩 넘겨 보세요

left = 0 right = 6

has_pair.py
  1. 1def has_pair(arr, target):
  2. 2 left, right = 0, len(arr) - 1
  3. 3 while left < right:
  4. 4 total = arr[left] + arr[right]
  5. 5 if total == target:
  6. 6 return True
  7. 7 elif total < target:
  8. 8 left += 1
  9. 9 else:
  10. 10 right -= 1
  11. 11 return False
0 / 15
  • left · right — 남은 카드의 양끝 칸 번호. 둘 사이가 아직 안 버린 카드다
  • total — 지금 양끝의 합. 이 값 하나로 어느 쪽을 버릴지 정한다
  • left < right — 두 끝이 만나면 멈춘다. 같은 카드를 두 번 쓰지 않는다

줄이 흐트러진 [3, 9, 10, 1] 에 같은 코드를 돌립니다. 3 + 10 = 13 이 있는데 목표 13 을 찾을까요?

쌍이 있는데 없다고 하거나, 없는데 있다고 한다

  • 줄이 안 섰다 — 위 문제처럼 쌍을 놓친다. 먼저 arr.sort() 로 줄을 세운다. 줄 세우는 데 N log N 이 든다
  • left <= right — 같은 카드를 두 번 쓴다. [1, 6, 9] 에서 목표 12 는 쌍이 없는데 6 + 6 을 쌍이라고 한다
  • 끝까지 못 찾으면 — 두 끝이 만나서 반복문이 끝난다. 그때 return False

문제에서 이 말이 보이면

정렬돼 있다두 수의 합양끝에서 좁힌다

다음 장에서는 창문을 밀면서 보는 슬라이딩 윈도우를 봅니다.