DevTips

코딩테스트 필수 유형: 투 포인터(Two Pointers) 완벽 가이드 – 연습 문제와 상세 풀이

투 포인터(Two Pointers) 알고리즘이란?

투 포인터는 1차원 배열이나 리스트에서 두 개의 포인터를 조작하며 문제를 해결하는 기법입니다. 특히 정렬된 배열에서 특정 조건을 만족하는 부분을 찾거나, 연속된 구간의 합을 구하는 문제에서 효과적입니다.

핵심 아이디어: 이중 for문으로 O(N2)O(N^2)이 걸릴 문제를 두 포인터를 적절히 이동시켜 O(N)O(N)으로 해결할 수 있습니다.

투 포인터의 두 가지 패턴

패턴 설명 대표 문제
양 끝에서 시작 배열의 시작(left)과 끝(right)에서 포인터를 두고 좁혀가며 탐색 두 수의 합, 회문 검사
같은 방향 이동 두 포인터가 모두 배열의 시작에서 출발하여 조건에 따라 이동 부분 배열 합, 슬라이딩 윈도우

예제 1: 두 수의 합 (양 끝 포인터)

문제

정렬된 배열 arr과 목표값 target이 주어질 때, 배열의 두 원소의 합이 target과 같은 쌍을 찾으세요.

입력 예시

arr = [1, 2, 3, 4, 6, 8, 9]
target = 10

출력 예시

[1, 9] (또는 [2, 8])

알고리즘 원리

  1. 배열이 정렬되어 있다는 점을 활용합니다
  2. 왼쪽 포인터 left는 0에서, 오른쪽 포인터 right는 배열 끝에서 시작
  3. 두 포인터가 가리키는 값의 합(current_sum)을 계산:
    – current_sum == target: 정답 발견!
    – current_sum < target: 합을 키워야 하므로 left 증가 (더 큰 값 필요)
    – current_sum > target: 합을 줄여야 하므로 right 감소 (더 작은 값 필요)

시간/공간 복잡도

  • 시간 복잡도: O(N)O(N) – 각 포인터가 최대 N번 이동
  • 공간 복잡도: O(1)O(1) – 추가 메모리 사용 없음

Python 풀이

def two_sum_sorted(arr, target):
    """
    정렬된 배열에서 합이 target인 두 수 찾기

    Args:
        arr: 정렬된 정수 배열
        target: 목표 합

    Returns:
        [left_value, right_value] 또는 None
    """
    left = 0
    right = len(arr) - 1

    while left < right:
        current_sum = arr[left] + arr[right]

        if current_sum == target:
            # 정답 발견
            return [arr[left], arr[right]]
        elif current_sum < target:
            # 합이 작으므로 left를 증가시켜 더 큰 값 시도
            left += 1
        else:
            # 합이 크므로 right를 감소시켜 더 작은 값 시도
            right -= 1

    return None  # 답이 없는 경우

# 테스트
arr = [1, 2, 3, 4, 6, 8, 9]
target = 10
result = two_sum_sorted(arr, target)
print(f"두 수의 합이 {target}인 쌍: {result}")
# 출력: 두 수의 합이 10인 쌍: [1, 9]

동작 과정 시각화

arr = [1, 2, 3, 4, 6, 8, 9], target = 10

Step 1: left=0, right=6 → 1 + 9 = 10 ✓ 정답!

다른 예시로 target = 7인 경우:

Step 1: left=0, right=6 → 1 + 9 = 10 > 7 → right 감소
Step 2: left=0, right=5 → 1 + 8 = 9 > 7 → right 감소
Step 3: left=0, right=4 → 1 + 6 = 7 ✓ 정답!

예제 2: 부분 배열의 합 (같은 방향 포인터)

문제

양의 정수 배열 arr과 목표값 target이 주어질 때, 연속된 부분 배열의 합이 target 이상이 되는 최소 길이를 구하세요.

입력 예시

arr = [2, 3, 1, 2, 4, 3]
target = 7

출력 예시

2  # [4, 3]의 길이

알고리즘 원리

  1. start와 end 두 포인터를 배열 시작에 배치
  2. current_sum에 현재 구간의 합을 유지
  3. 구간을 확장하거나 축소:
    – current_sum < target: end를 증가시켜 구간 확장
    – current_sum >= target: 최소 길이 갱신 후 start를 증가시켜 구간 축소

시간/공간 복잡도

  • 시간 복잡도: O(N)O(N) – 각 원소가 최대 2번 방문 (start, end 각 1회)
  • 공간 복잡도: O(1)O(1)

Python 풀이

def min_subarray_len(arr, target):
    """
    합이 target 이상인 연속 부분 배열의 최소 길이

    Args:
        arr: 양의 정수 배열
        target: 목표 합

    Returns:
        최소 길이 (없으면 0)
    """
    n = len(arr)
    min_length = float('inf')  # 무한대로 초기화
    current_sum = 0
    start = 0

    for end in range(n):
        # end 포인터를 이동하며 구간에 원소 추가
        current_sum += arr[end]

        # 현재 합이 target 이상이면 start를 이동하며 최소 길이 갱신
        while current_sum >= target:
            min_length = min(min_length, end - start + 1)
            current_sum -= arr[start]  # start 원소 제거
            start += 1

    return min_length if min_length != float('inf') else 0

# 테스트
arr = [2, 3, 1, 2, 4, 3]
target = 7
result = min_subarray_len(arr, target)
print(f"최소 부분 배열 길이: {result}")
# 출력: 최소 부분 배열 길이: 2

동작 과정 시각화

arr = [2, 3, 1, 2, 4, 3], target = 7

Step 1: end=0 [2] sum=2 < 7
Step 2: end=1 [2,3] sum=5 < 7
Step 3: end=2 [2,3,1] sum=6 < 7
Step 4: end=3 [2,3,1,2] sum=8 >= 7 ✓ length=4
  → start=1 [3,1,2] sum=6 < 7
Step 5: end=4 [3,1,2,4] sum=10 >= 7 ✓ length=4
  → start=2 [1,2,4] sum=7 >= 7 ✓ length=3
  → start=3 [2,4] sum=6 < 7
Step 6: end=5 [2,4,3] sum=9 >= 7 ✓ length=3
  → start=4 [4,3] sum=7 >= 7 ✓ length=2 (최소!)
  → start=5 [3] sum=3 < 7

최종 답: 2

예제 3: 세 수의 합 (응용)

문제

정렬되지 않은 배열에서 세 수의 합이 0이 되는 모든 조합을 찾으세요 (중복 제거).

입력 예시

arr = [-1, 0, 1, 2, -1, -4]

출력 예시

[[-1, -1, 2], [-1, 0, 1]]

알고리즘 원리

  1. 먼저 배열을 정렬 – O(Nlog⁡N)O(N \log N)
  2. 첫 번째 수를 고정하고, 나머지 두 수는 투 포인터로 탐색 – O(N2)O(N^2)
  3. 중복 제거를 위해 같은 값은 건너뜀

시간/공간 복잡도

  • 시간 복잡도: O(N2)O(N^2) – 정렬 O(Nlog⁡N)O(N \log N) + 이중 루프 O(N2)O(N^2)
  • 공간 복잡도: O(1)O(1) (결과 저장 공간 제외)

Python 풀이

def three_sum(arr):
    """
    세 수의 합이 0인 모든 조합 찾기

    Args:
        arr: 정수 배열

    Returns:
        세 수 조합의 리스트
    """
    arr.sort()  # 정렬 필수
    result = []
    n = len(arr)

    for i in range(n - 2):
        # 중복된 첫 번째 수 건너뛰기
        if i > 0 and arr[i] == arr[i - 1]:
            continue

        # 첫 번째 수 고정 후 투 포인터 탐색
        left = i + 1
        right = n - 1
        target = -arr[i]  # 나머지 두 수의 합이 target이 되어야 함

        while left < right:
            current_sum = arr[left] + arr[right]

            if current_sum == target:
                result.append([arr[i], arr[left], arr[right]])

                # 중복 제거: 같은 값 건너뛰기
                while left < right and arr[left] == arr[left + 1]:
                    left += 1
                while left < right and arr[right] == arr[right - 1]:
                    right -= 1

                left += 1
                right -= 1
            elif current_sum < target:
                left += 1
            else:
                right -= 1

    return result

# 테스트
arr = [-1, 0, 1, 2, -1, -4]
result = three_sum(arr)
print(f"세 수의 합이 0인 조합: {result}")
# 출력: 세 수의 합이 0인 조합: [[-1, -1, 2], [-1, 0, 1]]

동작 과정 시각화

정렬 후: [-4, -1, -1, 0, 1, 2]

i=0, arr[i]=-4, target=4
  left=1, right=5 → -1+2=1 < 4 → left++
  left=2, right=5 → -1+2=1 < 4 → left++
  left=3, right=5 → 0+2=2 < 4 → left++
  left=4, right=5 → 1+2=3 < 4 → left++
  left >= right, 종료

i=1, arr[i]=-1, target=1
  left=2, right=5 → -1+2=1 ✓ 발견: [-1, -1, 2]
  중복 제거 후 left=3, right=4
  left=3, right=4 → 0+1=1 ✓ 발견: [-1, 0, 1]

i=2, arr[i]=-1 (중복) → 건너뜀

자주 하는 실수와 엣지 케이스

실수 1: 포인터 이동 조건 오류

# ❌ 잘못된 예시
while left <= right:  # left == right일 때도 포함
    # 같은 원소를 두 번 사용하는 오류 발생 가능

# ✅ 올바른 예시
while left < right:  # 엄격한 부등호 사용

실수 2: 정렬 여부 미확인

양 끝 포인터 패턴은 반드시 정렬된 배열에서만 작동합니다.

# ❌ 정렬 안 함
def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    # ...

# ✅ 정렬 확인/수행
def two_sum_sorted(arr, target):
    arr.sort()  # 정렬 보장
    left, right = 0, len(arr) - 1
    # ...

엣지 케이스

케이스 처리 방법
배열 길이 < 2 함수 시작 부분에서 예외 처리
모든 원소가 양수/음수 정상 작동하도록 초기값 설정
중복 원소 중복 제거 로직 추가 (예제 3 참고)
답이 없는 경우 None 또는 빈 리스트 반환

난이도별 접근법

쉬움: 기본 투 포인터

  • 특징: 정렬된 배열, 단일 정답
  • 예시: 두 수의 합, 회문 검사
  • 핵심: 포인터 이동 조건만 정확히 구현

보통: 슬라이딩 윈도우

  • 특징: 구간 합/최대/최소, 연속 부분 배열
  • 예시: 부분 배열 합, 최대 연속 부분 배열
  • 핵심: start와 end 이동 타이밍 결정

어려움: 복합 투 포인터

  • 특징: 다중 포인터, 정렬 + 탐색 결합
  • 예시: 세 수의 합, 네 수의 합, 빗물 트래핑
  • 핵심: 고정 포인터 + 이동 포인터 조합, 중복 제거

관련 변형 문제

1. 컨테이너 문제 (Container With Most Water)

두 수직선 사이에 담을 수 있는 물의 최대 면적을 구하는 문제. 넓이 = min(height[left], height[right]) * (right - left)

2. 빗물 트래핑 (Trapping Rain Water)

높이 배열에서 빗물이 고이는 총량 계산. 양쪽에서 최대 높이를 추적하며 투 포인터 이동.

3. 회문 판별

문자열이 회문인지 확인. left는 증가, right는 감소하며 문자 비교.

4. 정렬된 배열 합치기

두 정렬된 배열을 하나로 병합. 각 배열에 포인터를 두고 작은 값부터 선택.

실전 팁

언제 투 포인터를 사용할까?

  1. 문제에서 “정렬된 배열” 또는 “연속 부분 배열”이 언급될 때
  2. 이중 for문 O(N2)O(N^2) 해법이 떠오르지만 시간 제한이 빡빡할 때
  3. 특정 조건을 만족하는 구간을 찾는 문제일 때

구현 체크리스트:
– [ ] 배열이 정렬되어야 하는가? → 필요시 arr.sort()
– [ ] 포인터 초기 위치는? (양 끝 vs 같은 시작점)
– [ ] 포인터 이동 조건은 명확한가?
– [ ] 중복 처리가 필요한가?
– [ ] 엣지 케이스 처리 (빈 배열, 길이 1, 답 없음)

마무리

투 포인터는 배열 탐색 문제의 시간 복잡도를 O(N2)O(N^2)에서 O(N)O(N)으로 획기적으로 줄이는 강력한 기법입니다. 핵심은 다음과 같습니다:

  1. 정렬 여부 확인 – 양 끝 포인터는 정렬 필수
  2. 포인터 이동 조건 – 현재 값이 목표보다 크면/작으면 어느 포인터를 움직일지 결정
  3. 패턴 선택 – 양 끝에서 좁히기 vs 같은 방향 이동

코딩테스트에서 “정렬된 배열에서 조건 만족하는 쌍 찾기” 또는 “연속 부분 배열의 합” 유형을 만나면 가장 먼저 투 포인터를 떠올리세요. 위 예제들을 손으로 직접 시뮬레이션해보면서 포인터 이동 과정을 체화하면, 실전에서 빠르게 적용할 수 있습니다.

관련 글

데이터분석데이터분석가 취준생을 위한 필수 데이터분석 기법 5가지와 실전 예제2026.01.30미분류배열 vs 연결 리스트: 자료구조 선택 가이드와 실무 활용법2026.01.29데이터분석고객 이탈 예측 프로젝트: 실무에서 쓰이는 머신러닝 파이프라인 구축하기2026.01.30코딩테스트이분 탐색(Binary Search) 완벽 가이드 – 알고리즘 원리부터 코딩테스트 응용까지2026.01.30

이 글이 도움이 되셨나요?

Buy me a coffee

댓글

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

TODAY 45 | TOTAL 244