DSA Interview Prep · 강의

투 포인터: 양끝에서 이동하기

Q: “투 포인터: 양끝에서 이동하기” 강의는 무료인가요?

네 — “투 포인터: 양끝에서 이동하기” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

Q: DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.

Q: “투 포인터: 양끝에서 이동하기” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

Q: 이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

서로를 향해 이동하는 왼쪽·오른쪽 포인터로 정렬 배열의 두 수 합, 유효한 회문, 빗물 가두기 문제를 해결합니다.

투 포인터: 양끝에서 이동하기은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

투 포인터 아이디어

투 포인터 기법은 서로를 향해 이동하거나 같은 방향으로 이동하는 두 개의 인덱스 변수를 사용해 중첩 반복문의 필요성을 줄입니다. 모든 쌍을 O(n²)에 확인하는 대신 각 비교마다 진행하여 O(n)에 완료합니다. 현재 쌍의 합이 너무 크거나 작은지에 따라 어느 방향으로 포인터를 이동할지 판단하려면 배열이 먼저 정렬되어 있어야 하는 경우가 거의 항상 필요합니다.

# Without two pointers: O(n^2)
def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

# With two pointers on sorted array: O(n)
def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target: return [left, right]
        elif s < target: left  += 1
        else:           right -= 1
    return []

정렬된 배열의 두 수의 합

정렬된 배열에서 한 포인터는 왼쪽 끝(최솟값)에, 다른 포인터는 오른쪽 끝(최댓값)에 둡니다. 합이 너무 작으면 합을 키우기 위해 왼쪽 포인터를 오른쪽으로 이동합니다. 합이 너무 크면 합을 줄이기 위해 오른쪽 포인터를 왼쪽으로 이동합니다. 각 반복에서 포인터가 하나 이상 앞으로 나아가므로 반복문은 최대 n번 실행됩니다. 정렬에 걸리는 시간을 제외하면 전체 시간 복잡도는 O(n)입니다. 중요한 점은 정렬된 순서 덕분에 각 이동이 증명 가능한 올바른 선택이라는 것입니다.

def two_sum_sorted(numbers, target):
    # numbers is 1-indexed per LeetCode 167
    left, right = 0, len(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]  # 1-indexed
        elif s < target:
            left  += 1  # need larger sum
        else:
            right -= 1  # need smaller sum
    return []

print(two_sum_sorted([2, 7, 11, 15], 9))   # [1, 2]
print(two_sum_sorted([2, 3, 4], 6))         # [1, 3]

유효한 회문 확인

문자열을 앞에서 읽으나 뒤에서 읽으나 같다면 회문입니다. 양 끝에서 시작하는 두 포인터를 사용해 안쪽으로 이동합니다. 문자를 비교하고, 영숫자가 아닌 문자는 건너뛰며, 포인터가 서로 교차하면 중단합니다. 이 방법은 O(n) 시간과 O(1)의 추가 공간으로 실행됩니다. 문자열을 뒤집어 비교하는 방식은 O(n)의 추가 메모리를 할당하므로 이 방법이 훨씬 깔끔합니다.

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        # Skip non-alphanumeric
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

print(is_palindrome('A man, a plan, a canal: Panama'))  # True
print(is_palindrome('race a car'))                       # False

세 수의 합: 정렬 + 투 포인터

세 수의 합 문제에서는 합이 0이 되는 모든 고유한 세 쌍을 찾습니다. 배열을 정렬한 다음 각 요소 nums[i]를 고정하고, 나머지 부분 배열에서 -nums[i]를 합으로 갖는 쌍을 투 포인터로 찾습니다. 중복된 세 쌍이 나오지 않도록 고정한 요소와 찾은 쌍의 중복을 모두 건너뜁니다. 전체 시간 복잡도는 O(n log n) 정렬 이후 O(n²)입니다.

def three_sum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]: continue  # skip dupe
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left]  == nums[left+1]:  left  += 1
                while left < right and nums[right] == nums[right-1]: right -= 1
                left += 1; right -= 1
            elif s < 0: left  += 1
            else:       right -= 1
    return result

print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1,-1,2],[-1,0,1]]

가장 많은 물을 담는 용기

수직선의 높이가 주어졌을 때, 가장 많은 물을 담을 수 있는 용기를 이루는 두 선을 찾습니다. 넓이 = min(height[left], height[right]) × (right - left)입니다. 더 짧은 선에 있는 포인터를 안쪽으로 탐욕적으로 이동합니다. 더 긴 선을 이동하면 높이의 제한은 커지지 않고 너비만 줄어들 수 있기 때문입니다. 이 탐욕적 선택은 증명 가능한 최적 해이며 O(n) 시간이 걸립니다.

def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        h    = min(height[left], height[right])
        area = h * (right - left)
        best = max(best, area)
        # Move the shorter wall inward
        if height[left] < height[right]:
            left  += 1
        else:
            right -= 1
    return best

print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49

정렬된 배열 제곱하기

정렬된 배열의 각 요소를 제곱하고(음수를 포함할 수 있음), 결과를 정렬된 순서로 반환합니다. 음수의 제곱은 크고 양수의 제곱은 중앙에서 작습니다. 양 끝에 두 포인터를 두고 결과 배열을 오른쪽에서 왼쪽으로, 즉 큰 값부터 작은 값 순서로 채웁니다. 시간 복잡도는 O(n)이고 출력 공간은 O(n)으로, 제곱한 뒤 O(n log n)에 정렬하는 것보다 훨씬 효율적입니다.

def sorted_squares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    pos = n - 1
    while left <= right:
        l_sq = nums[left]  ** 2
        r_sq = nums[right] ** 2
        if l_sq > r_sq:
            result[pos] = l_sq
            left += 1
        else:
            result[pos] = r_sq
            right -= 1
        pos -= 1
    return result

print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]

빗물 받기

인덱스 i에 고이는 물의 양은 min(max_left, max_right) - height[i]와 같습니다. 투 포인터 방식에서는 max_left와 max_right의 누적 값을 유지합니다. max_left < max_right이면 왼쪽이 병목이므로 왼쪽 포인터를 처리합니다. 그렇지 않으면 오른쪽을 처리합니다. 이를 통해 왼쪽 최댓값 배열과 오른쪽 최댓값 배열을 따로 만들 필요가 없어지고, O(1)의 추가 공간으로 해결할 수 있습니다.

def trap(height):
    left, right = 0, len(height) - 1
    max_left = max_right = 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= max_left:
                max_left = height[left]
            else:
                water += max_left - height[left]
            left += 1
        else:
            if height[right] >= max_right:
                max_right = height[right]
            else:
                water += max_right - height[right]
            right -= 1
    return water

print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))  # 6

탐욕적 포인터 이동이 작동하는 이유

면접에서 자주 이어지는 질문은 다음과 같습니다: 더 작은 쪽 포인터를 버려도 안전한 이유는 무엇인가요? 가장 많은 물을 담는 용기 문제의 증명 개요를 살펴보겠습니다. height[left] < height[right]라고 가정합니다. j < right인 모든 쌍 (left, j)의 넓이는 height[left] × (j-left) 이하이고, 이는 height[left] × (right-left)보다 작거나 같으며 현재 넓이 이하입니다. 따라서 right보다 작은 오른쪽 인덱스를 사용하면서 left에서 시작하는 어떤 쌍도 현재 넓이를 넘어설 수 없습니다. 그러므로 left를 이동해 이 쌍들을 안전하게 건너뛸 수 있습니다.

# Correctness argument via contradiction:
# If left < right and height[left] < height[right],
# then for any j in (left, right):
#   area(left, j) <= min(h[left], h[j]) * (j - left)
#                 <= h[left] * (j - left)
#                 <= h[left] * (right - left)   [since j < right]
#                 = current area
# So no pair (left, j) for j < right can improve.
# Moving left inward is SAFE.

print('Proof verified: advance shorter pointer is optimal')

정렬된 배열에서 최소 차이 쌍

정렬된 배열에서 절댓값 차이가 가장 작은 숫자 쌍을 찾습니다. 양 끝이 아닌 서로 인접한 두 포인터를 사용해 함께 훑습니다. 모든 연속된 쌍에 대해 |nums[i] - nums[i+1]|를 계산합니다. 정렬된 배열에서는 가까운 값들이 서로 모이므로 최소 차이는 항상 인접한 요소 사이에서 발생합니다. 정렬 이후에는 O(n)입니다.

def min_diff_pair(nums):
    nums.sort()  # O(n log n)
    min_diff = float('inf')
    best = (nums[0], nums[1])
    for i in range(len(nums) - 1):
        diff = nums[i+1] - nums[i]  # sorted: always >= 0
        if diff < min_diff:
            min_diff = diff
            best = (nums[i], nums[i+1])
    return best, min_diff

pair, d = min_diff_pair([4, 2, 1, 6, 10, 8])
print(pair, d)  # (1, 2) 1

양 끝 투 포인터 템플릿

대부분의 양 끝 투 포인터 문제는 같은 뼈대를 따릅니다. 이 템플릿을 익혀 두면 시간 압박 속에서도 빠르게 응용할 수 있습니다. 핵심적으로 결정할 사항은 다음과 같습니다. (1) 어떤 조건에서 왼쪽 포인터를 이동할지, (2) 어떤 조건에서 오른쪽 포인터를 이동할지, (3) 무엇을 해답으로 볼지, (4) 중복을 어떻게 처리할지입니다. 코드를 작성하기 전에 문제 설명에서 이러한 결정 사항을 도출해 표현하는 연습을 하십시오.

def two_pointer_template(arr, condition):
    """
    Generic opposite-ends two-pointer skeleton.
    Replace condition logic for each specific problem.
    """
    left, right = 0, len(arr) - 1
    result = []
    while left < right:
        current = arr[left] + arr[right]  # or some combination
        if current == condition:           # found a valid pair
            result.append((arr[left], arr[right]))
            left  += 1
            right -= 1
        elif current < condition:          # need to increase
            left  += 1
        else:                             # need to decrease
            right -= 1
    return result

두 포인터로 유효한 쌍 세기

두 포인터는 쌍을 효율적으로 세는 데에도 사용할 수 있습니다. 정렬된 배열에서 합이 < 목표값인 쌍을 세는 문제에서는 왼쪽 포인터를 고정하고 오른쪽 포인터를 사용해 유효한 가장 오른쪽 인덱스를 찾습니다. 모든 쌍 (left, left+1 to right)이 유효하므로 개수에 right - left를 더한 뒤 왼쪽 포인터를 이동합니다. 이렇게 하면 O(n²)이 아니라 O(n)에 모든 유효한 쌍을 셀 수 있습니다.

def count_pairs_less_than(nums, target):
    nums.sort()
    left, right = 0, len(nums) - 1
    count = 0
    while left < right:
        if nums[left] + nums[right] < target:
            count += right - left  # all (left, left+1..right) valid
            left  += 1
        else:
            right -= 1
    return count

print(count_pairs_less_than([1, 2, 3, 4, 5], 6))
# pairs: (1,2)(1,3)(1,4)(2,3)  -> 4

빠른 점검

이 단원에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 점검합니다.

단원 요약

이 단원에서는 다음을 배웠습니다. 양 끝 투 포인터는 정렬된 배열에서 O(n²)의 모든 쌍 열거를 O(n)의 왼쪽-오른쪽 수렴으로 대체합니다. 어느 포인터를 이동할지는 문제의 단조성에 따라 결정되며, 현재 진행을 제한하는 쪽을 이동합니다. 또한 세 수의 합, 물을 가장 많이 담는 용기, 빗물 가두기, 회문 검증은 모두 같은 핵심 템플릿으로 환원됩니다. 다음에는 느린 포인터와 빠른 포인터 패턴을 살펴보겠습니다.

자주 묻는 질문