모든 사진 자료에 관한 출처는 아래 알튜비튜 - 튜터링에 있음을 밝힙니다.
https://github.com/Altu-Bitu/Notice
이런 문제가 있다고 해봅시다!
더할때마다 시간 복잡도 O(n)
만약 배열의 크기가 10,000 이라면 구하고자하는 구간이 1,000,000개만 돼도 총 연산횟수 100억!
💎부분합
A[i] ~ A[j]까지의 합 = sum[j] -sum[i-1]
➡슬라이딩 윈도우
그렇다면 j-i가 고정된 상태, 즉 구해야하는 구간이 일정한 상태에서
누적합을 사용하지 않고 구간합을 빠르게 구하는 방법은?
🔀투포인터
- 2개의 포인터로 배열을 탐색하며 빠르게 답을 찾는 알고리즘
- 주로 반복문(while)으로 구현
- 일반적으로 시간 복잡도 O(n2)의 문제를 시간복잡도 O(n)으로 풀 수 있음
- 투 포인터 탐색방법은 크게 두가지
- 2개의 포인터가 다른위치에서 시작하여 서로에게 다가가는 방향으로 탐색
- 2개의 포인터가 같은 위치에서 시작하여 같은방향으로 이동하며 탐색
- 1번 방식은 일반적으로 배열이 정렬됐을때에만 성립하는 경우가 많음
- 슬라이딩 윈도우는 2개의 포인터 사이의 거리를 고정하고, 2번방식으로 탐색한것과 같음.
📝대표문제
BOJ 2470)두 용액
정렬이 됐다고 가정하면 맨 왼쪽에는 가장 작은 값이 존재, 맨 오른쪽에는 가장 큰 값이 존재한다. 오른쪽으로 갈 수 록 값이 커지고, 왼쪽으로 갈 수록 값이 작아진다.
종료조건 : left < right
(left는 항상 right의 왼쪽에 있어야 함 -> left right가 같아지면 하나의 용액을 사용하게 되기 때문)
BOJ 1644)소수의 연속합
-> 에라토스테네스의 체를 이용해 연속된 소수를 연속된 배열의 원소로 넣자! 그리고 같은방향으로 탐색하는 두개의 포인터 활용!
Q. 둘다 한칸씩 옮기는 이유?
A. Left만 오른쪽으로 옮기면 목표값(41)보다 작아져서 Right를 옮기게됨. Right만 오른쪽으로 옮기면 목표값(41)보다 커져서 Left를 옮기게 됨.
즉. left ->right, right->left 과정이 필연적으로 뒤따르므로 한꺼번에 처리하는것.
종료 조건 :left <= right && right < size
(left는 항상 right의 왼쪽 또는 같은 위치에 있어야 함)
PRO Level3 )보석쇼핑
같은 방향으로 탐색하는 두개의 포인터를 활용하자!
종료 조건 :left <= right && right < size
(left는 항상 right의 왼쪽 또는 같은 위치에 있어야 함)
✨마무리
- 다양한 경우에서 배열의 탐색 효율을 높이기 위해 사용되는 투 포인터 알고리즘!
- 두개의 포인터 사이의 거리가 고정된다면 슬라이딩 윈도우!
- 포인터가 가까워지는 방법(left<right) 와 멀어지는 방법(left<=right)이 있음
- 가까워지는 방법은 보통 중복이 없고 정렬된 배열에만 사용 가능함. 두개의 포인터가 가리키는 값만 고려할때.
- 멀어지는 방법은 두개의 포인터가 가리키는 값 사이의 모든 값을 고려할때
- 효율성 테스트 문제로 아주 많이 출제됨
