잡 인터뷰 - 투포인터 알고리즘(Two Pointer Approach)

학교 다니고 있을 땐 이런 이런 부분을 자세히 들여다 보고 설명까지도 가능했(?) 을지도 모른다..ㅋ

10여 년 전 배웠던 기억도 나고 그것으로 숙제를 해서 제출까지 했던 기억이 스멀스멀 나지만,

직접 회사인터뷰때 질문을 받으니 설명을 제대로 하기가 쉽지가 않다.

어떻게든 대답은 헀어도.. 얼버무려버리는 바람에 이번 인터뷰도 틀린 거겠지..

그래도 이렇게 그냥 지나가버리면 인터뷰 시간을 낭비해 버리는 게 되어버리니 일단 자세히 찾아봐야겠다.

투포인터 알고리즘이 뭐지?

투포인터 알고리즘은 리스트나 배열에서 두 개의 포인터를 이용하여 원하는 결과를 얻는 알고리즘이다.

이 알고리즘은 보통 리스트에서 부분합, 또는 특정 조건을 만족하는 가장 짧은 구간을 찾는 등의 문제를 해결하는 데 활용될 수 있다.

알고리즘의 동작 방식은 다음과 같이 리스트의 시작과 끝을 가리키는 두 개의 포인터를 놓고 이후 두 포인터 사이의 원소를 조작하며 원하는 결과를 얻을 수 있다. 보통 이 알고리즘에서는 두 포인터의 위치를 이동시키는 규칙을 잘 설정하는 것이 중요하다.

예를 들면, 주어진 리스트에서 합이 S 이상인 가장 짧은 구간을 찾는 문제를 해결한다고 가정해 볼 때. 이 경우 시작 포인터와 끝 포인터를 리스트의 맨 처음 위치에 놓고, 끝 포인터들을 이동시켜 가며 리스트의 원소들을 더해 나갑니다. 만약 합이 S 이상이 되면, 시작 포인터를 이동시키면서 구간의 길이를 최소화하고 이 과정을 반복하여 가장 짧은 구간의 길이를 찾으면 된다.

이렇게 하면 리스트를 한 번 순회하는 O(N) 시간 안에 원하는 결과를 얻을 수 있다.

 

투포인터 알고리즘을 파이썬으로 구현한 코드를 예로 보자. 이 코드는 리스트에서 합이 S 이상인 가장 짧은 구간을 찾는 문제다.

def shortest_subarray(nums, S):
    # 시작 포인터와 끝 포인터 초기화
    left, right = 0, 0
    # 현재 구간의 합 초기화
    curr_sum = 0
    # 최소 구간 길이 초기화
    min_len = float('inf') 

    while right < len(nums):
    	# 현재 구간에 새로운 원소 추가
        curr_sum += nums[right] 
        # 현재 구간의 합이 S 이상이면 시작 포인터 이동
        while curr_sum >= S: 
        	# 최소 길이 갱신
            min_len = min(min_len, right - left + 1) 
			# 시작 포인터 이동
			curr_sum -= nums[left] 
            left += 1
        # 끝 포인터 이동
        right += 1 
    
    return min_len if min_len != float('inf') else 0

위 코드에서 nums는 주어진 리스트이고, S는 찾으려는 합의 값일 때, left와 right는 각각 시작 포인터와 끝 포인터를 나타낸다.

curr_sum은 현재 구간의 합을 나타내며, min_len은 합이 S 이상인 가장 짧은 구간의 길이를 저장한다.

코드의 주요 로직은 while 루프 안에 있고 이 루프에서는 right 포인터를 이동시키면서 현재 구간에 새로운 원소를 추가한다. 그리고 현재 구간의 합이 S 이상이 되면 left 포인터를 이동시키면서 구간의 길이를 최소화하며 이 과정을 반복하여 가장 짧은 구간의 길이를 찾을 수 있다. 마지막으로 min_len이 float('inf')인 경우에는 0을 반환한다.

 

또한, slow 포인터와 fast 포인터를 사용하여 문제를 해결하는 경우도 있다. 이 경우 slow 포인터와 fast 포인터는 같은 방향으로 움직이며, slow 포인터는 한 번에 한 칸씩 이동하고, fast 포인터는 한 번에 두 칸씩 이동하는 식으로 원하는 것을 찾을수 있다.

 

따라서 투 포인터 알고리즘은 문제에 따라서 성능이 다르게 나타날 수 있지만. 대부분의 경우 시간 복잡도는 O(n)으로 매우 효율적이다.