투 포인터
리스트에서 원하는 값을 얻기 위해 두 개의 포인터를 이용해 각 위치를 기록하면서 처리하는 알고리즘이다.
반복문을 사용해 리스트를 단순 탐색하는 것보다 투 포인터를 사용하면 시간 복잡도를 낮출 수 있다.
리스트의 크기가 N일 때, Worst Case일 경우 시간복잡도를 알아보자.
전자의 경우에는 반복문을 N번씩 두번 돌려서 시간복잡도는 \(O(N \times N) = O(N^2)\) 이 된다.
후자의 경우에는 두 포인터가 모두 N번 탐색하여 시간복잡도는 \(O(2N) = O(N)\) 이 된다.
투 포인터는 위의 그림처럼 두 가지 방식으로 쓰인다.
- 앞에서부터 시작하는 포인터와 끝에서부터 시작하는 포인터가 중간에서 만나는 방식
- 둘 다 앞에서 시작해서 하나의 포인터가 다른 포인터보다 앞서면서 끝에 도달하는 방식
슬라이딩 윈도우
고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘이다.
위의 투 포인터 알고리즘과 공통적으로 시간복잡도를 부분 배열을 활용하여 \(O(N)\) 으로 줄일 수 있다.
그러나, 투 포인터 알고리즘은 구간의 크기가 가변적인 반면에 슬라이딩 윈도우 알고리즘은 구간의 크기가 고정적이다.
또 다른 차이점으로는 슬라이딩 윈도우 알고리즘은 구간의 크기가 항상 같기 때문에 포인터 변수가 1개만 있어도 충분하다.
728x90
반응형
'알고리즘 > 이분 탐색' 카테고리의 다른 글
| [백준] 2143번 두 배열의 합 (JAVA) (0) | 2023.02.22 |
|---|---|
| [백준] 2096번 내려가기 (JAVA) (0) | 2023.02.22 |
| [백준] 2003번 수들의 합 2 (JAVA) (0) | 2023.02.22 |
| [백준] 1806번 부분합 (JAVA) (0) | 2023.02.21 |
| [백준] 1072번 게임 (JAVA) (0) | 2023.02.20 |
