1. 투 포인터 (Two Pointers)

투 포인터는 두 개의 포인터를 사용하여 배열이나 리스트를 탐색하는 기법입니다. 보통 O(n²)을 O(n)으로 최적화할 수 있습니다.

1.1 투 포인터의 유형

1.2 양 끝에서 시작하는 투 포인터

가장 일반적인 형태로, 정렬된 배열에서 두 값의 합을 찾을 때 사용합니다.

def two_sum_sorted(arr, target):
    """
    정렬된 배열에서 합이 target인 두 수의 인덱스 찾기
    O(n) 시간복잡도
    """
    left, right = 0, len(arr) - 1
 
    while left < right:
        current_sum = arr[left] + arr[right]
 
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1   # 합이 작으면 왼쪽 포인터 증가
        else:
            right -= 1  # 합이 크면 오른쪽 포인터 감소
 
    return []
 
 
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(two_sum_sorted(arr, 10))  # [0, 8] (1 + 9 = 10)
print(two_sum_sorted(arr, 15))  # [5, 8] (6 + 9 = 15)

def two_sum_sorted(arr, target):
    """
    정렬된 배열에서 합이 target인 두 수의 인덱스 찾기
    O(n) 시간복잡도
    """
    left, right = 0, len(arr) - 1
 
    while left < right:
        current_sum = arr[left] + arr[right]
 
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1   # 합이 작으면 왼쪽 포인터 증가
        else:
            right -= 1  # 합이 크면 오른쪽 포인터 감소
 
    return []
 
 
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(two_sum_sorted(arr, 10))  # [0, 8] (1 + 9 = 10)
print(two_sum_sorted(arr, 15))  # [5, 8] (6 + 9 = 15)

동작 과정 시각화

1.3 같은 방향 투 포인터

두 포인터가 같은 방향으로 이동하며 구간을 관리합니다.

def min_subarray_length(arr, target):
    """
    합이 target 이상인 가장 짧은 연속 부분 배열의 길이
    """
    n = len(arr)
    left = 0
    current_sum = 0
    min_length = float('inf')
 
    for right in range(n):
        current_sum += arr[right]
 
        # 조건을 만족하면 왼쪽 포인터 이동
        while current_sum >= target:
            min_length = min(min_length, right - left + 1)
            current_sum -= arr[left]
            left += 1
 
    return min_length if min_length != float('inf') else 0
 
 
arr = [2, 3, 1, 2, 4, 3]
print(min_subarray_length(arr, 7))  # 2 ([4, 3])

def min_subarray_length(arr, target):
    """
    합이 target 이상인 가장 짧은 연속 부분 배열의 길이
    """
    n = len(arr)
    left = 0
    current_sum = 0
    min_length = float('inf')
 
    for right in range(n):
        current_sum += arr[right]
 
        # 조건을 만족하면 왼쪽 포인터 이동
        while current_sum >= target:
            min_length = min(min_length, right - left + 1)
            current_sum -= arr[left]
            left += 1
 
    return min_length if min_length != float('inf') else 0
 
 
arr = [2, 3, 1, 2, 4, 3]
print(min_subarray_length(arr, 7))  # 2 ([4, 3])

1.4 세 수의 합 (3Sum)

def three_sum(arr):
    """
    세 수의 합이 0인 모든 조합 찾기 (중복 제거)
    """
    arr.sort()
    result = []
    n = len(arr)
 
    for i in range(n - 2):
        # 중복 건너뛰기
        if i > 0 and arr[i] == arr[i - 1]:
            continue
 
        # 투 포인터로 나머지 두 수 찾기
        left, right = i + 1, n - 1
        target = -arr[i]
 
        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
 
 
print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1, -1, 2], [-1, 0, 1]]

def three_sum(arr):
    """
    세 수의 합이 0인 모든 조합 찾기 (중복 제거)
    """
    arr.sort()
    result = []
    n = len(arr)
 
    for i in range(n - 2):
        # 중복 건너뛰기
        if i > 0 and arr[i] == arr[i - 1]:
            continue
 
        # 투 포인터로 나머지 두 수 찾기
        left, right = i + 1, n - 1
        target = -arr[i]
 
        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
 
 
print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1, -1, 2], [-1, 0, 1]]

2. 슬라이딩 윈도우 (Sliding Window)

슬라이딩 윈도우는 고정 크기의 윈도우를 이동시키며 배열을 탐색하는 기법입니다.

2.1 슬라이딩 윈도우의 핵심

윈도우 크기가 고정된 경우
연속된 부분 배열/문자열 처리
새로 들어오는 요소 추가, 빠지는 요소 제거

2.2 고정 크기 윈도우

def max_sum_subarray(arr, k):
    """
    크기 k인 연속 부분 배열의 최대 합
    """
    n = len(arr)
    if n < k:
        return None
 
    # 첫 윈도우의 합
    window_sum = sum(arr[:k])
    max_sum = window_sum
 
    # 윈도우 이동
    for i in range(k, n):
        # 새 요소 추가, 이전 요소 제거
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
 
    return max_sum
 
 
arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]
print(max_sum_subarray(arr, 4))  # 24 ([2, 10, 2, 3])

def max_sum_subarray(arr, k):
    """
    크기 k인 연속 부분 배열의 최대 합
    """
    n = len(arr)
    if n < k:
        return None
 
    # 첫 윈도우의 합
    window_sum = sum(arr[:k])
    max_sum = window_sum
 
    # 윈도우 이동
    for i in range(k, n):
        # 새 요소 추가, 이전 요소 제거
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
 
    return max_sum
 
 
arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]
print(max_sum_subarray(arr, 4))  # 24 ([2, 10, 2, 3])

동작 과정

배열: [1, 4, 2, 10, 2, 3, 1, 0, 20]
k = 4

Step 1: [1, 4, 2, 10] = 17
Step 2: [4, 2, 10, 2] = 18
Step 3: [2, 10, 2, 3] = 17
Step 4: [10, 2, 3, 1] = 16
Step 5: [2, 3, 1, 0] = 6
Step 6: [3, 1, 0, 20] = 24 ← 최대

배열: [1, 4, 2, 10, 2, 3, 1, 0, 20]
k = 4

Step 1: [1, 4, 2, 10] = 17
Step 2: [4, 2, 10, 2] = 18
Step 3: [2, 10, 2, 3] = 17
Step 4: [10, 2, 3, 1] = 16
Step 5: [2, 3, 1, 0] = 6
Step 6: [3, 1, 0, 20] = 24 ← 최대

2.3 가변 크기 윈도우

조건에 따라 윈도우 크기가 변하는 경우입니다.

def longest_substring_k_distinct(s, k):
    """
    최대 k개의 서로 다른 문자를 포함하는 가장 긴 부분 문자열
    """
    from collections import defaultdict
 
    char_count = defaultdict(int)
    left = 0
    max_length = 0
 
    for right in range(len(s)):
        # 오른쪽 문자 추가
        char_count[s[right]] += 1
 
        # 서로 다른 문자가 k개 초과하면 왼쪽 축소
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1
 
        max_length = max(max_length, right - left + 1)
 
    return max_length
 
 
print(longest_substring_k_distinct("eceba", 2))    # 3 ("ece")
print(longest_substring_k_distinct("aabbcc", 2))   # 4 ("aabb" 또는 "bbcc")

def longest_substring_k_distinct(s, k):
    """
    최대 k개의 서로 다른 문자를 포함하는 가장 긴 부분 문자열
    """
    from collections import defaultdict
 
    char_count = defaultdict(int)
    left = 0
    max_length = 0
 
    for right in range(len(s)):
        # 오른쪽 문자 추가
        char_count[s[right]] += 1
 
        # 서로 다른 문자가 k개 초과하면 왼쪽 축소
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1
 
        max_length = max(max_length, right - left + 1)
 
    return max_length
 
 
print(longest_substring_k_distinct("eceba", 2))    # 3 ("ece")
print(longest_substring_k_distinct("aabbcc", 2))   # 4 ("aabb" 또는 "bbcc")

2.4 중복 없는 가장 긴 부분 문자열

def longest_substring_without_repeating(s):
    """
    중복 문자 없는 가장 긴 부분 문자열의 길이
    """
    char_index = {}  # 문자: 마지막 등장 인덱스
    left = 0
    max_length = 0
 
    for right, char in enumerate(s):
        # 중복 문자가 있고, 윈도우 내에 있으면
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
 
        char_index[char] = right
        max_length = max(max_length, right - left + 1)
 
    return max_length
 
 
print(longest_substring_without_repeating("abcabcbb"))  # 3 ("abc")
print(longest_substring_without_repeating("bbbbb"))     # 1 ("b")
print(longest_substring_without_repeating("pwwkew"))    # 3 ("wke")

def longest_substring_without_repeating(s):
    """
    중복 문자 없는 가장 긴 부분 문자열의 길이
    """
    char_index = {}  # 문자: 마지막 등장 인덱스
    left = 0
    max_length = 0
 
    for right, char in enumerate(s):
        # 중복 문자가 있고, 윈도우 내에 있으면
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
 
        char_index[char] = right
        max_length = max(max_length, right - left + 1)
 
    return max_length
 
 
print(longest_substring_without_repeating("abcabcbb"))  # 3 ("abc")
print(longest_substring_without_repeating("bbbbb"))     # 1 ("b")
print(longest_substring_without_repeating("pwwkew"))    # 3 ("wke")

3. 투 포인터/슬라이딩 윈도우 실전 문제

3.1 모든 종류 포함 최소 구간

def min_range_with_all_types(items):
    """
    여러 종류의 아이템이 있는 배열에서
    모든 종류의 아이템을 포함하는 가장 짧은 연속 구간을 찾습니다.
 
    items: 아이템 이름 리스트
    반환: [시작인덱스, 끝인덱스] (1-indexed)
    """
    from collections import defaultdict
 
    item_types = len(set(items))
    item_count = defaultdict(int)
 
    left = 0
    answer = [0, len(items) - 1]
    count = 0
 
    for right in range(len(items)):
        # 새 아이템 추가
        if item_count[items[right]] == 0:
            count += 1
        item_count[items[right]] += 1
 
        # 모든 종류를 포함하면 왼쪽 축소 시도
        while count == item_types:
            # 더 짧은 구간이면 업데이트
            if right - left < answer[1] - answer[0]:
                answer = [left, right]
 
            # 왼쪽 아이템 제거
            item_count[items[left]] -= 1
            if item_count[items[left]] == 0:
                count -= 1
            left += 1
 
    return [answer[0] + 1, answer[1] + 1]  # 1-indexed
 
 
print(min_range_with_all_types(["A", "B", "B", "A", "A", "C", "D", "A"]))
# [3, 7]

def min_range_with_all_types(items):
    """
    여러 종류의 아이템이 있는 배열에서
    모든 종류의 아이템을 포함하는 가장 짧은 연속 구간을 찾습니다.
 
    items: 아이템 이름 리스트
    반환: [시작인덱스, 끝인덱스] (1-indexed)
    """
    from collections import defaultdict
 
    item_types = len(set(items))
    item_count = defaultdict(int)
 
    left = 0
    answer = [0, len(items) - 1]
    count = 0
 
    for right in range(len(items)):
        # 새 아이템 추가
        if item_count[items[right]] == 0:
            count += 1
        item_count[items[right]] += 1
 
        # 모든 종류를 포함하면 왼쪽 축소 시도
        while count == item_types:
            # 더 짧은 구간이면 업데이트
            if right - left < answer[1] - answer[0]:
                answer = [left, right]
 
            # 왼쪽 아이템 제거
            item_count[items[left]] -= 1
            if item_count[items[left]] == 0:
                count -= 1
            left += 1
 
    return [answer[0] + 1, answer[1] + 1]  # 1-indexed
 
 
print(min_range_with_all_types(["A", "B", "B", "A", "A", "C", "D", "A"]))
# [3, 7]

3.2 원형 배열 부분합 종류

def count_circular_sums(elements):
    """
    원형 배열에서 연속 부분 수열의 합으로 만들 수 있는 서로 다른 수의 개수를 구합니다.
 
    원형 배열이므로 마지막 요소 다음은 첫 번째 요소와 연결됩니다.
 
    elements: 원형 배열
    """
    n = len(elements)
    sums = set()
 
    # 길이 1부터 n까지
    for length in range(1, n + 1):
        # 첫 윈도우
        window_sum = sum(elements[:length])
        sums.add(window_sum)
 
        # 슬라이딩
        for start in range(1, n):
            # 이전 요소 빼고 새 요소 더하기 (원형)
            window_sum -= elements[start - 1]
            window_sum += elements[(start + length - 1) % n]
            sums.add(window_sum)
 
    return len(sums)
 
 
print(count_circular_sums([7, 9, 1, 1, 4]))  # 18

def count_circular_sums(elements):
    """
    원형 배열에서 연속 부분 수열의 합으로 만들 수 있는 서로 다른 수의 개수를 구합니다.
 
    원형 배열이므로 마지막 요소 다음은 첫 번째 요소와 연결됩니다.
 
    elements: 원형 배열
    """
    n = len(elements)
    sums = set()
 
    # 길이 1부터 n까지
    for length in range(1, n + 1):
        # 첫 윈도우
        window_sum = sum(elements[:length])
        sums.add(window_sum)
 
        # 슬라이딩
        for start in range(1, n):
            # 이전 요소 빼고 새 요소 더하기 (원형)
            window_sum -= elements[start - 1]
            window_sum += elements[(start + length - 1) % n]
            sums.add(window_sum)
 
    return len(sums)
 
 
print(count_circular_sums([7, 9, 1, 1, 4]))  # 18

3.3 시간 기반 요금 계산

import math
from collections import defaultdict
 
def calculate_parking_fee(fees, records):
    """
    주차 요금을 계산합니다.
 
    fees: [기본시간(분), 기본요금, 단위시간(분), 단위요금]
    records: ["시간 차량번호 IN/OUT", ...] 형태의 기록
 
    규칙:
    - 기본시간 이하면 기본요금만 부과
    - 초과 시간은 단위시간당 단위요금 추가 (올림 적용)
    - 출차 기록 없으면 23:59에 출차한 것으로 계산
    """
    base_time, base_fee, unit_time, unit_fee = fees
 
    # 차량별 입출차 기록
    parking = {}  # 현재 주차 중인 차량
    total_time = defaultdict(int)  # 차량별 총 주차 시간
 
    for record in records:
        time, car_num, action = record.split()
        h, m = map(int, time.split(':'))
        minutes = h * 60 + m
 
        if action == 'IN':
            parking[car_num] = minutes
        else:  # OUT
            total_time[car_num] += minutes - parking[car_num]
            del parking[car_num]
 
    # 출차 기록 없는 차량 (23:59 출차로 계산)
    last_time = 23 * 60 + 59
    for car_num, in_time in parking.items():
        total_time[car_num] += last_time - in_time
 
    # 요금 계산
    result = []
    for car_num in sorted(total_time.keys()):
        time = total_time[car_num]
 
        if time <= base_time:
            fee = base_fee
        else:
            fee = base_fee + math.ceil((time - base_time) / unit_time) * unit_fee
 
        result.append(fee)
 
    return result
 
 
fees = [180, 5000, 10, 600]
records = [
    "05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT",
    "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN",
    "19:09 0148 OUT", "22:59 5961 IN", "23:00 5961 OUT"
]
print(calculate_parking_fee(fees, records))  # [14600, 34400, 5000]

import math
from collections import defaultdict
 
def calculate_parking_fee(fees, records):
    """
    주차 요금을 계산합니다.
 
    fees: [기본시간(분), 기본요금, 단위시간(분), 단위요금]
    records: ["시간 차량번호 IN/OUT", ...] 형태의 기록
 
    규칙:
    - 기본시간 이하면 기본요금만 부과
    - 초과 시간은 단위시간당 단위요금 추가 (올림 적용)
    - 출차 기록 없으면 23:59에 출차한 것으로 계산
    """
    base_time, base_fee, unit_time, unit_fee = fees
 
    # 차량별 입출차 기록
    parking = {}  # 현재 주차 중인 차량
    total_time = defaultdict(int)  # 차량별 총 주차 시간
 
    for record in records:
        time, car_num, action = record.split()
        h, m = map(int, time.split(':'))
        minutes = h * 60 + m
 
        if action == 'IN':
            parking[car_num] = minutes
        else:  # OUT
            total_time[car_num] += minutes - parking[car_num]
            del parking[car_num]
 
    # 출차 기록 없는 차량 (23:59 출차로 계산)
    last_time = 23 * 60 + 59
    for car_num, in_time in parking.items():
        total_time[car_num] += last_time - in_time
 
    # 요금 계산
    result = []
    for car_num in sorted(total_time.keys()):
        time = total_time[car_num]
 
        if time <= base_time:
            fee = base_fee
        else:
            fee = base_fee + math.ceil((time - base_time) / unit_time) * unit_fee
 
        result.append(fee)
 
    return result
 
 
fees = [180, 5000, 10, 600]
records = [
    "05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT",
    "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN",
    "19:09 0148 OUT", "22:59 5961 IN", "23:00 5961 OUT"
]
print(calculate_parking_fee(fees, records))  # [14600, 34400, 5000]

4. 투 포인터 vs 슬라이딩 윈도우

특성	투 포인터	슬라이딩 윈도우
포인터 이동	양 끝에서 또는 같은 방향	항상 같은 방향
윈도우 크기	가변적	고정 또는 가변
주요 용도	두 수의 합, 정렬된 배열	연속 부분 배열/문자열
시간복잡도	O(n)	O(n)

5. 문제 유형별 접근법

5.1 투 포인터를 사용하는 경우

정렬된 배열에서 두 수의 합/차
팰린드롬 확인
정렬된 배열 병합
물 채우기 문제 (Container With Most Water)

5.2 슬라이딩 윈도우를 사용하는 경우

고정 크기 구간의 최대/최소/평균
연속된 k개의 합이 조건을 만족
조건을 만족하는 가장 긴/짧은 구간
문자열에서 특정 패턴 찾기

투 포인터/슬라이딩 윈도우 키워드

"연속된", "부분 배열", "구간"
"최대/최소 길이"
"합이 X인", "조건을 만족하는"
"정렬된 배열에서"
"중복 없는"

6. 연습문제

(투 포인터) 두 수의 합: https://pyalgo.co.kr/?page=7
(투 포인터) 구간 합 가우스: https://pyalgo.co.kr/?page=9
(투 포인터) 두 수의 합 찾기: https://100.pyalgo.co.kr/?page=26
(슬라이딩 윈도우) 연속 부분 수열의 합: https://100.pyalgo.co.kr/?page=27
(슬라이딩 윈도우) 구간 최대합: https://100.pyalgo.co.kr/?page=28

코딩 테스트 에센셜 with 파이썬

투 포인터와 슬라이딩 윈도우