『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.
투 포인터
- 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.
- 두 개의 포인터를 이동해가며 리스트에 순차적으로 접근한다.
- 의 시간 복잡도 알고리즘을 갖고 있다.
- 루프를 돌면서 두 포인터 중 하나를 1씩 증가시키고, 각 포인터가 배열의 끝까지 도달(N번)하면 루프가 끝난다.
연속된 자연수의 합
투 포인터 알고리즘의 대표적인 문제로, 연속된 자연수의 합이 특정한 값인 것을 찾는 문제이다.
몇 개의 연속된 자연수의 합으로 나타낼 수 있는 어떠한 자연수 N이 있다. 이때, N을 몇 개의 연속된 자연수의 합으로 나타낼 수 있는 가지수를 구할 때 투 포인터를 사용할 수 있다.
예를 들어, N이 15라면 다음 총 4가지가 있다.
1) 15
2) 7+8
3) 4+5+6
4) 1+2+3+4+5
또 다른 예로, N이 10이라면 다음 총 2가지가 있다.
1) 10
2) 1+2+3+4
예제: N=10인 경우
다음과 같이 1부터 10까지의 자연수를 값으로 가진 배열을 생성한다.
이때, 첫 번째 포인터(START)와 두 번째 포인터(END)는 모두 첫 번째 인덱스를 가리킨다.
END 포인터를 오른쪽으로 한 칸씩 옮기면서(인덱스+1) 합을 구한다.
START 포인터와 END 포인터 사이의 값들의 합이 10이 된다면, Count를 1 올린다.
- 1 + 2 + 3 + 4 = 10
END 포인터를 한 칸 다시 옮겼을 때, 합이 N(여기서는 10)을 넘어서면 START 포인터를 한 칸 앞으로 옮긴다.
이렇게 다음 동작을 반복하다가 END 포인터가 배열 끝에 도달하면 루프를 끝낸다.
- START 포인터와 END 포인터 사이의 합을 sum 이라고 할 때,
1) sum이 10보다 작으면 END 포인터를 이동 (범위 증가)
2) sum이 10보다 크면 START 포인터를 이동 (범위 감소)
3) sum이 10이라면 Count를 증가시키고 END 포인터를 이동 (범위 증가)
정리
이렇게 두 개의 포인터를 지정하고, 각 포인터를 이동해가면서 값을 구하는 알고리즘을 투 포인터라고 한다.
슬라이딩 윈도우
- 2개의 포인터로 범위를 지정한 다음 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결한다.
- 투 포인터 알고리즘과 매우 비슷하지만, 범위를 유지한다는 점에서 차이가 있다.
- 배열의 길이만큼만 탐색을 진행하면 되므로 의 시간 복잡도로 문제를 해결할 수 있다.
원리
다음과 같이 범위를 지정했다고 가정하자.
START와 END 포인터를 동시에 1씩 증가시켜서 범위를 유지한 채로 이동시킨다.
- 창문을 옆으로 미는 것과 유사한 동작이라고 생각하면 된다.
이렇게 END 포인터가 배열의 끝에 다다를 때까지 옆으로 미는 것을 반복한다.
Reference
