배열의 특정 연속된 구간을 처리하는 경우
예시
아래의 기법들을 활용하면 O(N) 시간에 처리가 가능하다
시작 인덱스, 종료 인덱스를 지정해 접근할 데이터의 범위를 표현
- 2개의 포인터 변수 시작점이 배열의 시작점인 경우
- 정렬된 배열 안에서 2개의 포인터 변수가 각각 시작점과 끝점(arr.length-1)에 위치한 경우
투 포인터를 활용한, 특정한 합을 가지는 부분 연속 수열 개수 찾기
- 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.
- 현재 부분 합이 M과 같다면, 카운트 한다.
- 현재 부분 합이 M보다 작다면, end를 1 증가시킨다.
- 현재 부분 합이 M보다 크거나 같다면, start를 1 증가시킨다.
- 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.
예시
무작위로 두 개의 데이터를 골라 찾는 값인지 확인하는 문제
⇒ 연속성을 만들어줘야 함
1. 데이터 정렬
2. end(오른쪽 인덱스)를 처음(0
)에서부터가 아닌, 마지막(len(arr)-1
)에서 시작
예시
start < end일 동안
- 합 > 원하는 값 :
end -= 1
- 합 < 원하는 값 :
start += 1
- 합 == 원하는 값 : (
start += 1
end -= 1
)count++
백준 2018번 연속된 자연수의 합 구하기
코드
-> 다시 풀고 벨로그 글로 수정하기
백준 1940번 주몽
코드
-> 다시 풀고 벨로그 글로 수정하기
백준 1253번 좋다⭐
두 개의 포인터로 window 지정, window 유지한 채로 이동하며 문제 해결
⇒ 찾는 범위 크기 고정일 때
오른쪽으로 한 칸 이동해도 옮기기 전과 후에 겹치는 부분 존재
→ 기존 검사 결과에서 새로 들어오는 값, 빠지는 값만 반영
오른쪽으로 한 번 슬라이딩할 때, 빠지게 되는 왼쪽 첫 번째 값과 추가되는 오른쪽의 값을 반영하도록 코딩
슬라이딩 윈도우를 덱으로 구현하면 빠른 정렬 효과 볼 수 있음
백준 12891번 DNA 비밀번호
코드
-> 다시 풀고 벨로그 글로 수정하기
백준 11003번 최솟값 찾기 1⭐
코드
-> 다시 풀고 벨로그 글로 수정하기
위의 두 알고리즘과 비슷하게 배열의 특정 연속된 구간에 대한 처리를 목적으로 하는 알고리즘
합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
합 배열 말고 접두사 합이라고 많이 하는 것 같음
배열 A에 대한 합 배열 S 정의
S[i] = A[0] + A[1] + ... + A[i-1] + A[i]
⇒ S[i] = S[i-1] + A[i]
1. L번째 원소부터 R번째 원소까지 구간의 합 구하기
S[R] - S[L-1]
2. (X1, Y1) 부터 (X2, Y2) 까지 구간의 합 구하기
D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1][Y1-1]
백준 11659번 구간 합 구하기 4 ⭐
코드
-> 다시 풀고 벨로그 글로 수정하기
백준 11660번 구간 합 구하기 5
코드
-> 풀고 벨로그 글로 수정하기
백준 10986번 나머지 합
코드
-> 다시 풀고 벨로그 글로 수정하기