투포인터 알고리즘 개념
1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작한다. 이때문에 투포인터 알고리즘이라 부른다.
알고리즘 설명 및 특징
완전탐색으로 해결하면 시간 초과가 나는 문제를 투포인터 알고리즘으로 시간복잡도를 줄여 문제를 해결할 수 있다.
(완전탐색의 경우 for 문을 중첩해서 2개 이상 형성해야하는 반면, 투포인터는 반복문 1개로도 가능하게 된다)
1차원 배열의 완전탐색에서 n제곱 꼴의 시간복잡도를 n 의 1제곱 으로 줄일 수 있다.
알고리즘 대표 유형문제 - 2003 수들의 합
N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소의 합이 M이 되는 경우의 수를 구하는 것이다. 모든 경우의 수를 다 테스트 해보면 구간 합을 구간 배열로 O(1)만에 구한다고 해도 경우의 수는 O(N^2)이 된다. 따라서 문제를 풀 수 없다. N의 최대 범위가 너무 크기 때문이다.
아주 잘 설명된 글이 있다. 1차원 배열에서 연속한 수의 합이 M일경우의 개수를 구하는 것.
참고링크 1:
참고링크 2:
https://butter-shower.tistory.com/226
추천 문제(백준 기준)
- 2003 : 수들의 합
- 1644 : 소수의 연속합
- 1806 : 부분합
- 2230 : 수 고르기
- 1484 : 다이어트
- 2038 : 골룽 수열
- 2531 : 회전 초밥
- 2096 : 내려가기
- 2293 : 동전1
비슷하거나, 관련된 유형의 개념: 슬라이딩 윈도우, 누적 합
누적합 알고리즘 개념 및 설명
prefix sum이라고도 불린다.
1차원 배열에서 i에서부터 j까지의 합을 구할 때, 최대 O(N)이 나오지만, 미리 sum 을 1차원 배열로 구해놓으면 O(1)로 연산이 줄어든다.
2차원 배열의 경우 arr[0][0]에서부터 arr[i][j]까지의 i, j 원소의 합을 저장해두는 2차원 sum 배열을 만들어두면 구간 합을 상수시간 안에 계산할 수 있다(링크 참고. 전체 사각형 - 원하지 않는 부분 + 중복되는 부분)
참고로, 누적합 배열의 생성은 dp배열 생성하듯이,업데이트 하듯히 하면 된다.
sum_arr[i][j] = arr[i-1][j-1] + sum_arr[i-1][j] + sum_arr[i][j-1] - sum_arr[i-1][j-1]
참고
누적합을 구해야 하는데, 구간의 요소가 자꾸 변하는 상황에서는 누적합보다는 누적합 세그먼트 트리를 구성하여 O(NlogN)으로 처리하는 것이 성능 개선에 중요한 역할을 한다.
유형문제
https://school.programmers.co.kr/learn/courses/30/lessons/92344
https://www.acmicpc.net/problemset?sort=ac_desc&algo=139
참고링크:
https://yiyj1030.tistory.com/489
https://ojt90902.tistory.com/574
슬라이딩 윈도우 개념 및 설명
참고
유형문제
https://www.acmicpc.net/problemset?sort=ac_desc&algo=68