투 포인터 알고리즘은 이름에서 알 수 있듯이 두 개의 포인터를 활용하는 알고리즘이다.
포인터는 쉽게 말해 마우스 포인터와 같이 위치를 표시하는 것이다.
투 포인터는 시작과 끝 또는 왼쪽과 오른쪽을 표시하는 포인터를 각각 저장하고 이를 이동해가며 얻고자하는 최적의 해를 찾는 알고리즘이다.
이번 글에서는 하나의 아주 쉬운 문제를 예시로 투 포인터 알고리즘을 설명할 것이다.
문제
자연수로 구성된 리스트 [1,3,5,7,4,1,5,8,2,6] 이 주어졌을 때 연속되는 원소들의 합(부분합)이 15를 만족하는 원소들의 리스트들을 출력해라.
해설
이런 아주 단순한 문제는 brute force로도 해결할 수 있겟지만 투 포인터로 해결해보자.
1. 우선 start,end 포인터를 리스트의 시작부분에 둔다. 시작 index는 0이고 현재까지의 sum은 1이 된다.
2. sum<15이므로 sum>=15가 될 때까지 end만 오른쪽으로 이동시킨다. (한 칸씩 end를 이동해가며 sum을 계산하고 15와 비교해본다.)
3. sum>15이므로 sum<15가 될 때까지 start만 오른쪽으로 이동시킨다. (한 칸씩 start를 이동해가며 sum을 계산하고 15와 비교해본다.)
sum = 15 -> [output : 3 5 7]
4. sum<15 이므로 2번 과정을 진행한다.
5. sum>15이므로 3번 과정을 진행한다.
이런식으로 2,3번 과정을 반복하다보면 아래 그림과 같이 한번 더 sum = 15인 부분 리스트를 찾게 된다. (직접 한번 해보면 좋을 것 같다.)
sum = 15 -> [output : 5 8 2]
end가 마지막 인덱스에 도달한 경우:
1. sum>15인 경우 : 3번 과정을 수행하고 다시 sum을 비교한다.
2. sum<15인 경우 : end가 더 이상 이동할 수 없으므로 종료한다.
문제를 투 포인터 알고리즘을 통해 해결해 보았다.
투 포인터 알고리즘은 그림에서 보았듯이 리스트를 한번 훑는 식으로 진행된다. 따라서 투 포인터 알고리즘의 시간 복잡도는 O(N)에 해당된다.
따라서 Brute force 알고리즘을 이용하여 풀면 O(N^2)이 걸리지만 투 포인터 알고리즘을 사용하면 O(N)으로 시간을 확 줄일 수 있다.
그러나 여기서 주의해야 할 점이 있는데 리스트의 원소가 음수도 허용한다면 투 포인터 알고리즘을 사용할 수 없다. 왜냐하면 end를 증가하면 sum이 증가하고 start를 증가하면 sum이 감소한다고 가정할 수 있었던건 리스트 내 모든 원소가 자연수이기 때문이다. (음수이면 반대의 상황이 벌어질 수도 있다.)
즉, 투 포인터 알고리즘은 linear time이라는 장점이 있지만 반드시 용도에 맞게 사용해야 한다.
포인터는 쉽게 말해 마우스 포인터와 같이 위치를 표시하는 것이다.
투 포인터는 시작과 끝 또는 왼쪽과 오른쪽을 표시하는 포인터를 각각 저장하고 이를 이동해가며 얻고자하는 최적의 해를 찾는 알고리즘이다.
이번 글에서는 하나의 아주 쉬운 문제를 예시로 투 포인터 알고리즘을 설명할 것이다.
문제
자연수로 구성된 리스트 [1,3,5,7,4,1,5,8,2,6] 이 주어졌을 때 연속되는 원소들의 합(부분합)이 15를 만족하는 원소들의 리스트들을 출력해라.
해설
이런 아주 단순한 문제는 brute force로도 해결할 수 있겟지만 투 포인터로 해결해보자.
1. 우선 start,end 포인터를 리스트의 시작부분에 둔다. 시작 index는 0이고 현재까지의 sum은 1이 된다.
2. sum<15이므로 sum>=15가 될 때까지 end만 오른쪽으로 이동시킨다. (한 칸씩 end를 이동해가며 sum을 계산하고 15와 비교해본다.)
3. sum>15이므로 sum<15가 될 때까지 start만 오른쪽으로 이동시킨다. (한 칸씩 start를 이동해가며 sum을 계산하고 15와 비교해본다.)
sum = 15 -> [output : 3 5 7]
4. sum<15 이므로 2번 과정을 진행한다.
5. sum>15이므로 3번 과정을 진행한다.
이런식으로 2,3번 과정을 반복하다보면 아래 그림과 같이 한번 더 sum = 15인 부분 리스트를 찾게 된다. (직접 한번 해보면 좋을 것 같다.)
sum = 15 -> [output : 5 8 2]
end가 마지막 인덱스에 도달한 경우:
1. sum>15인 경우 : 3번 과정을 수행하고 다시 sum을 비교한다.
2. sum<15인 경우 : end가 더 이상 이동할 수 없으므로 종료한다.
문제를 투 포인터 알고리즘을 통해 해결해 보았다.
투 포인터 알고리즘은 그림에서 보았듯이 리스트를 한번 훑는 식으로 진행된다. 따라서 투 포인터 알고리즘의 시간 복잡도는 O(N)에 해당된다.
따라서 Brute force 알고리즘을 이용하여 풀면 O(N^2)이 걸리지만 투 포인터 알고리즘을 사용하면 O(N)으로 시간을 확 줄일 수 있다.
그러나 여기서 주의해야 할 점이 있는데 리스트의 원소가 음수도 허용한다면 투 포인터 알고리즘을 사용할 수 없다. 왜냐하면 end를 증가하면 sum이 증가하고 start를 증가하면 sum이 감소한다고 가정할 수 있었던건 리스트 내 모든 원소가 자연수이기 때문이다. (음수이면 반대의 상황이 벌어질 수도 있다.)
즉, 투 포인터 알고리즘은 linear time이라는 장점이 있지만 반드시 용도에 맞게 사용해야 한다.
댓글