투 포인터 알고리즘 Two Pointer Algorithm

프로그래머스에서 구명보트 문제를 풀다가 알게 된 투 포인터.

사실 예에전에 코딩테스트에서 한번 맞닥뜨리고, 완탐으로 풀었던 나는 처참히 망해버렸다...후후...

 

복습하지 않고 있었는데, 이번 문풀을 기회 삼아 정리해 보자!

 

투 포인터 알고리즘이란?

 

투 포인터(Two Pointer) 알고리즘은 배열, 리스트 또는 문자열과 같은 선형 데이터 구조에서 두 개의 포인터를 사용해 특정 조건을 만족하는 부분을 탐색하거나 계산하는 알고리즘 기법이다.

두 포인터가 데이터 구조의 양 끝에서 시작하거나, 같은 위치에서 출발하여 서로 다른 방향으로 이동하며 문제를 해결한다.

 

왜 쓰이는지?

 

• 효율적으로 배열이나 리스트에서 특정 조건을 만족하는 부분을 찾거나 연산을 수행.
• 중첩 루프(이중 반복문) 없이 문제를 해결하여 시간 복잡도를 줄이는 것.

 

언제 사용하면 좋은가?

• 배열이 정렬된 경우: 정렬된 데이터에서 특정 조건을 만족하는 값을 효율적으로 찾을 때.
• 구간 합 계산이 필요한 경우: 슬라이딩 윈도우와 결합하여 연속된 구간을 탐색할 때.
• 특정 값의 쌍 찾기: 두 숫자의 합, 세 숫자의 합 등에서 조건을 만족하는 경우.
• 중복 제거: 문자열이나 배열에서 고유 요소를 추적하는 문제.
• 효율성 중시: 이중 반복문으로 풀 경우 O(n2)O(n^2)O(n2) 복잡도를 O(n)O(n)O(n)으로 줄여야 할 때.

 

programmers - 구명보트 문제

def solution(people, limit):
    people.sort()
    answer = 0
    start = 0
    end = len(people) - 1
    while(start <= end) :
        if people[start] + people[end] <= limit:
            start += 1
        end -=1
        answer += 1
    return answer

 

구명보트에 최대 두 명만이 탑승 가능한 상황에서, 사람들의 무게가 주어졌을 때 사용 가능한 가장 최소의 구명보트의 수를 구하는 문제이다. 

가장 무게가 많이 나가는 사람이 타면, 자연스레 가장 몸무게가 적게 나가는 사람과 비교하게 된다.(Greedy) 이를 활용해서 투포인터 알고리즘을 활용해서 답을 구하면 된다.

 

중요한 건 배열이 정렬되어있어야 한다는 것을 기억하자!