5주차
1차원 배열이나 리스트를 다룰 때 두 개의 포인터(인덱스)를 조작하며 원하는 조건을 만족하는 결과를 찾는 알고리즘입니다.
- 두 개의 포인터(인덱스)를 조작하여 원하는 조건을 만족하는 결과를 탐색합니다.
- 완전 탐색(이중 for문)으로
O(N^2)의 시간이 걸리는 작업을O(N)으로 단축시킬 수 있다는 것이 가장 큰 핵심입니다. - 정렬된 배열에서의 탐색, 연속된 부분 배열(수열)의 처리와 깊게 연결되어 있습니다.
이름 그대로 두 개의 포인터(시작점과 끝점, 혹은 두 개의 이동점)를 사용하여 배열을 탐색하는 방식입니다.
- 보통 1차원 배열에서 두 개의 포인터를 조작합니다.
- 반복문 내에서 두 포인터가 각자의 조건에 따라 이동 방향과 속도를 결정합니다.
- 한 번 이동한 포인터는 뒤로 돌아가지 않으므로(역방향 이동 불가), 전체 배열을 한 번만 순회하게 되어 시간 복잡도
O(N)을 보장합니다. - 슬라이딩 윈도우와 자주 비교되며, 문제에 따라 혼용되어 쓰이기도 합니다.
1. 양방향 포인터
- 하나의 포인터는 배열의 처음(
Left), 다른 하나는 배열의 끝(Right)에서 시작합니다. - 주로 정렬된 배열에서 두 수의 합이나 차를 구할 때 사용됩니다.
- 조건에 따라
Left를 증가시키거나,Right를 감소시키며 서로 만날 때까지 가운데로 좁혀옵니다.
2. 동방향 포인터
- 두 포인터 모두 배열의 처음(
Start,End)에서 같은 방향으로 출발합니다. - 주로 연속된 부분 수열의 합이나 길이를 구할 때 사용됩니다.
- 조건에 따라
End를 전진시켜 구간을 넓히거나,Start를 전진시켜 구간을 좁히며 탐색합니다.
- 배열 안에서 두 요소의 합 또는 차를 구해야 하는데 입력 크기(N)가 100,000 이상이라서
O(N)또는O(N log N)으로 풀어야 한다면? ➡ 투 포인터 (양방향)
💡 참고: 양방향 투 포인터를 사용할 때, 배열이 정렬되어 있지 않다면 먼저 정렬
O(N log N)을 수행해야 합니다. 정렬 시간을 포함하더라도O(N^2)보다 훨씬 빠릅니다.
- 연속된 부분 배열이나 수열의 합이 특정 값이 되는 구간을 찾아야 한다면? ➡ 투 포인터 (동방향)
투 포인터 문제는 대부분 포인터의 이동 조건을 묻는 경우가 많으며, 다음과 같은 패턴이 등장하면 투 포인터 문제일 가능성이 높습니다.
1. 자주 나오는 문제 형태
- 정렬된 배열에서 두 수의 합이 Target이 되는 쌍 찾기
- 세 수의 합이 0이 되는 조합 찾기
- 가장 두 물의 양이 많은 용기 찾기 (수조 문제)
2. 접근 방법
- 배열을 오름차순으로 정렬합니다.
-
Left = 0,Right = 배열의 길이 - 1로 초기화합니다. - 두 값의 합이 Target보다 크면
Right를 왼쪽으로 이동시킵니다. (값을 줄임) - 두 값의 합이 Target보다 작으면
Left를 오른쪽으로 이동시킵니다. (값을 키움)
1. 자주 나오는 문제 형태
- 연속된 부분 수열의 합이 Target이 되는 경우의 수 찾기
- 합이 Target 이상이 되는 가장 짧은 연속 구간 길이 구하기
2. 접근 방법
-
Start = 0,End = 0으로 초기화합니다. - 현재 구간의 합이 Target보다 작거나 같으면
End를 오른쪽으로 이동하여 합을 증가시킵니다. - 현재 구간의 합이 Target보다 크거나 같으면 (또는 조건 만족 시)
Start를 오른쪽으로 이동하여 구간을 좁히고 합을 감소시킵니다.
자연수
n이 매개변수로 주어질 때, 연속된 자연수들로n을 표현하는 방법의 수를 반환하라! (예: 15는 1+2+3+4+5, 4+5+6, 7+8, 15로 총 4가지 방법으로 표현할 수 있다.)
연속된 수열의 합을 구하는 문제이므로, 두 포인터가 같은 방향으로 전진하는 동방향 투 포인터(또는 슬라이딩 윈도우)를 사용합니다.
- 두 포인터
start와end를 모두 1로 초기화합니다. -
start부터end까지의 합을sum이라고 할 때,sum과 목표값n을 비교하며 포인터를 이동시킵니다.-
sum == n: 조건을 만족하므로 경우의 수(정답)를 1 증가시킵니다. 새로운 구간을 탐색하기 위해sum에서start값을 빼고,start를 오른쪽으로 한 칸 이동시킵니다. (구간 축소) -
sum < n: 현재 합이 부족하므로 구간을 넓혀야 합니다. ➡end를 오른쪽으로 한 칸 이동시키고, 새로운end값을sum에 더합니다. -
sum > n: 현재 합이 넘치므로 구간을 좁혀야 합니다. ➡sum에서 현재start값을 빼고,start를 오른쪽으로 한 칸 이동시킵니다.
-
-
start가n이하일 때까지 위 과정을 반복합니다.
1. 초기화 투 포인터 알고리즘의 시작 단계입니다. 탐색을 시작하기 위해 두 포인터를 모두 가장 작은 자연수인 1에 위치시킵니다.
-
상태:
start = 1,end = 1 - 현재 합 (Current Sum): 1
구간은 [1]이며, 합은 1입니다. 목표값 15보다 작으므로(sum < n), 합을 늘리기 위해 end 포인터를 오른쪽으로 한 칸 이동시켜야 합니다. 정답 개수(Count)는 0에서 시작합니다.
2. 구간 확장 (Sum < Target)
현재 구간의 합이 목표값 15보다 작을 때, 구간을 확장하여 합을 키우는 과정입니다. end 포인터가 앞장서서 전진합니다.
-
상태:
start = 1,end = 4(1단계에서end++를 수차례 반복) - 현재 합 (Current Sum): 10 (1+2+3+4)
구간은 [1, 2, 3, 4]이며 합은 10입니다. 여전히 15보다 작으므로(sum < n), 이 상태에서 end를 한 칸 더 오른쪽으로 이동(end++)시켜 구간 [1...5]를 탐색해야 합니다. 포인터가 같은 방향(오른쪽)으로만 전진하는 것을 알 수 있습니다.
3. 조건 만족 (Sum == Target)
구간의 합이 정확히 목표값 n = 15가 된 순간입니다. 연속된 수열을 하나 찾았으므로 정답 개수를 증가시킵니다.
-
상태:
start = 1,end = 5 - 현재 합 (Current Sum): 15 (1+2+3+4+5)
구간 [1, 2, 3, 4, 5]의 합은 15로 목표값과 일치합니다(sum == n). 첫 번째 방법을 찾았으므로 Count를 1로 증가시킵니다.
조건을 만족했으므로, 새로운 구간을 탐색하기 위해 구간을 축소합니다. 현재 start 값(1)을 합에서 빼고, start 포인터를 한 칸 오른쪽으로 이동(start++)시킵니다. (이후 구간은 [2, 3, 4, 5]가 되고 합은 14가 됩니다.)
4. 구간 축소 (Sum > Target)
구간의 합이 목표값 15를 초과한 경우입니다. 합을 줄이기 위해 start 포인터를 전진시켜 구간의 왼쪽을 잘라냅니다.
-
상태:
start = 2,end = 6(3단계의 동작 이후,sum < n이 되어end++를 수행한 상태) - 현재 합 (Current Sum): 20 (2+3+4+5+6)
[2...6]의 합은 20으로 15를 초과했습니다(sum > n). 합을 줄여야 하므로, 현재 start 값인 2를 합에서 빼고 start 포인터를 오른쪽으로 한 칸 이동(start++)시켜야 합니다. (이후 구간은 [3...6]이 되고 합은 18이 되어, 여전히 sum > n이므로 start가 한 칸 더 전진하게 됩니다.)
5. 순환 반복 ... 이런 식으로 꼬리를 물며 이동합니다!
이 네 가지 상태를 start 포인터가 n(15)에 도달할 때까지 반복하면, 최종적으로 문제 예시에 나온 총 4가지 방법(1...5, 4...6, 7...8, 15)을 모두 찾고 Count = 4를 반환하며 알고리즘이 종료됩니다.
⏱️ 시간 복잡도 :
O(N)! 이중 for문으로O(N^2)탐색을 하면 시간 초과가 날 수 있으나, 투 포인터는 각 포인터가 최대n번만 이동하므로 훨씬 빠릅니다.
function solution(n) {
let answer = 0;
let start = 1;
let end = 1;
let sum = 1; // start부터 end까지의 합
while (start <= n) {
if (sum === n) {
answer++; // 정답 카운트
sum -= start; // 현재 start 값을 빼고
start++; // start를 오른쪽으로 이동
} else if (sum < n) {
end++; // end를 오른쪽으로 이동하고
sum += end; // 새로운 end 값을 더함
} else { // sum > n
sum -= start; // 현재 start 값을 빼고
start++; // start를 오른쪽으로 이동
}
}
return answer;
}코드 해설:
- 시작점
start와 끝점end를 1로 두고, 초기 합(sum)도 1로 설정합니다. - 매번 반복문을 돌면서 1부터
n까지 일일이 합을 다시 구하지 않고, 포인터가 이동할 때마다 양 끝 값만 더하거나 빼주어 연산을 최소화합니다.
def solution(n):
answer = 0
start = 1
end = 1
total_sum = 1 # start부터 end까지의 합
# 시작점이 n 이하일 때까지 반복
while start <= n:
if total_sum == n:
answer += 1 # 정답 카운트
total_sum -= start # 현재 start 값을 빼고
start += 1 # start를 오른쪽으로 이동
elif total_sum < n:
end += 1 # end를 오른쪽으로 이동하고
total_sum += end # 새로운 end 값을 더함
else: # total_sum > n
total_sum -= start # 현재 start 값을 빼고
start += 1 # start를 오른쪽으로 이동
return answerclass Solution {
public int solution(int n) {
int answer = 0;
int start = 1;
int end = 1;
int sum = 1; // start부터 end까지의 합
// 시작점이 n 이하일 때까지 반복
while (start <= n) {
if (sum == n) {
answer++; // 정답 카운트
sum -= start; // 현재 start 값을 빼고
start++; // start를 오른쪽으로 이동
} else if (sum < n) {
end++; // end를 오른쪽으로 이동하고
sum += end; // 새로운 end 값을 더함
} else { // sum > n
sum -= start; // 현재 start 값을 빼고
start++; // start를 오른쪽으로 이동
}
}
return answer;
}
}양끝에서 좁혀오는 투 포인터 로직은 '배열이 오름차순으로 정렬되어 있다는 가정' 하에 성립합니다. 정렬되지 않은 배열에서 크기 비교를 통해 포인터를 이동시키면 전혀 엉뚱한 결과를 낳게 됩니다. 입력된 배열이 정렬되어 있는지 반드시 확인하고, 안 되어 있다면 먼저 정렬(sort())을 수행해야 합니다.
while (left <= right)를 써야 할지, while (left < right)를 써야 할지 헷갈려 하는 경우가 많습니다.
- 서로 다른 두 원소를 골라야 하는 문제에서는
left < right가 맞습니다. (<=를 쓰면 같은 원소를 두 번 더하는 꼴이 될 수 있음) - 문제의 요구사항에 따라 하나의 원소를 중복해서 선택해도 되는 상황이라면 범위를 다르게 설정해야 하므로 주의가 필요합니다.
start와 end가 같은 방향으로 이동하는 문제에서, end가 배열의 끝을 넘어갔음에도 계속 인덱스에 접근하려고 하면 에러(Index Out Of Bounds)가 발생합니다. 반복문 안에서 포인터가 배열의 길이(N)를 초과하지 않도록 안전하게 예외 처리를 해두는 습관이 필요합니다.
마치 창문(Window)을 옆으로 한 칸씩 미는(Sliding) 것처럼, 1차원 배열이나 리스트에서 고정된 크기의 구간을 이동시키면서 원하는 조건을 만족하는 결과를 찾는 알고리즘입니다.
- 탐색하는 구간(윈도우)의 길이가 고정되어 있는 경우가 대부분입니다.
- 매번 구간의 합이나 특정 값을 새로 계산하지 않고, 빠져나가는 원소는 빼고 새로 들어오는 원소는 더하는 방식으로 연산을 최소화합니다.
- 중복된 연산을 제거하여, 완전 탐색 시 O(N * K)가 걸리는 작업을 O(N)으로 단축시킵니다.
이름 그대로 일정한 너비를 가진 '창문'을 배열의 처음부터 끝까지 스르륵 밀고 가면서 창문 너머로 보이는 데이터만 확인하는 방식입니다.
- 두 포인터(시작점과 끝점) 간의 간격이 일정하게 유지됩니다.
- 윈도우가 한 칸 이동할 때, 윈도우의 가운데 겹치는 부분은 변하지 않으므로 계산에서 제외합니다.
- 오직 기존 윈도우에서 벗어난 맨 앞의 값과 새롭게 윈도우에 포함된 맨 뒤의 값만 업데이트합니다.
- 정렬 여부와 상관없이 연속된 데이터 그룹을 처리할 때 매우 유용합니다.
투 포인터와 슬라이딩 윈도우는 모두 1차원 배열을 O(N)에 탐색하는 훌륭한 기법이지만, '구간의 길이' 에서 차이를 보입니다.
-
배열이나 문자열에서 "연속된 K개의 요소", "길이가 K인 부분 배열" 이라는 키워드가 등장한다면? ➡ 슬라이딩 윈도우
-
연속된 구간의 데이터를 처리하는데, 매번 처음부터 다시 계산하면 시간 초과(Time Limit Exceeded)가 날 것 같다면? ➡ 슬라이딩 윈도우
슬라이딩 윈도우는 고정된 길이를 다루기 때문에 패턴이 비교적 명확합니다.
1. 자주 나오는 문제 형태
- 길이가 K인 연속된 부분 배열 중 원소들의 합이 가장 큰 값(또는 가장 작은 값) 구하기
- K일 동안의 매출 기록 중 최대 매출액 구하기
2. 접근 방법
- 처음 0번 인덱스부터 K-1번 인덱스까지의 합(초기 윈도우의 합)을 구합니다.
- 윈도우를 한 칸씩 오른쪽으로 이동시킵니다. (인덱스 i를 K부터 배열 끝까지 반복)
- 새로운 합 = 이전 합 - 빠져나가는 맨 앞 원소(arr[i-K]) + 새로 들어오는 원소(arr[i])
- 매 이동마다 최대/최솟값을 갱신합니다.
1. 자주 나오는 문제 형태
- 특정 문자열 안에서 길이가 K인 부분 문자열 중 모음이 가장 많이 포함된 경우 찾기
- 부분 문자열이 특정 단어의 아나그램(문자 순서를 바꾼 것)인지 판별하기
마트에서 매일 하나씩 할인하는 제품 목록(discount)이 주어집니다. 내가 원하는 제품 목록(want)과 수량(number)이 총 10개일 때, 연속된 10일 동안의 할인 목록이 내가 원하는 목록과 정확히 일치하는 날짜가 총 며칠인지 반환하라!
문제에서 '연속된 10일' 이라는 명확한 구간을 주었으므로, 윈도우(창문)의 크기가 K = 10으로 고정된 전형적인 슬라이딩 윈도우 문제입니다.
- 목표 상태 기록: 먼저 내가 원하는 제품(want)과 수량(number)을 해시맵(딕셔너리/객체) 형태로 기록해 둡니다.
- 첫 윈도우 생성: 0일 차부터 9일 차까지(총 10일)의 할인 품목을 읽어 첫 번째 윈도우의 상태를 해시맵에 기록하고, 목표 상태와 일치하는지 확인합니다.
- 윈도우 슬라이딩 (창문 밀기): 10일 차부터는 배열 끝까지 창문을 하루씩 옆으로 밉니다.
- 윈도우를 처음부터 다시 10일 치를 세는 것이 아닙니다!
- 창문에서 빠져나가는 어제 날짜(맨 앞)의 제품 개수를 1개 빼고, 창문에 새로 들어오는 오늘 날짜(맨 뒤)의 제품 개수를 1개 더해줍니다.
- 매번 슬라이딩할 때마다 현재 윈도우의 해시맵이 목표 상태와 똑같은지 비교하여 정답 카운트를 올립니다.
1. 초기 윈도우 설정 (Day 0 ~ 9) - 처음 10일간의 할인 품목을 확인하여 바구니(현재 윈도우 상태)에 담습니다. - 원하는 품목/수량과 일치하는지 비교합니다. 일치한다면 정답(Count)을 1 증가시킵니다.
2. 윈도우 이동 1단계 (Day 1 ~ 10) - 창문이 오른쪽으로 하루 밀렸습니다. - Day 0의 품목은 창문 밖으로 벗어났으므로 바구니에서 1개 뺍니다. - Day 10의 품목이 창문 안으로 들어왔으므로 바구니에 1개 더합니다. - 중간에 겹치는 Day 1 ~ 9의 품목은 전혀 건드릴 필요가 없습니다! 연산이 획기적으로 줄어듭니다. - 다시 목표 상태와 비교합니다.
3. 순환 반복 - 배열의 끝에 도달할 때까지 매일 하루치 품목만 빼고 더하며 비교를 반복합니다.
⏱️ 시간 복잡도 :
O(N)! 매번 10일 치를 새로 탐색하면 문자열 비교 비용까지 더해져 O(N * 10) 이상의 시간이 걸리지만, 슬라이딩 윈도우를 사용하면 빠지고 들어오는 2개의 원소만 업데이트하므로 사실상 O(N)의 속도로 처리가 가능합니다.
def solution(want, number, discount):
answer = 0
# 1. 목표 상태 딕셔너리
target = dict(zip(want, number))
window = {}
# 2. 첫 10일(초기 윈도우) 세팅
for i in range(10):
window[discount[i]] = window.get(discount[i], 0) + 1
def is_match():
for k, v in target.items():
if window.get(k, 0) != v:
return False
return True
if is_match():
answer += 1
# 3. 슬라이딩 윈도우 진행
for i in range(10, len(discount)):
out_item = discount[i - 10] # 빠져나가는 항목
in_item = discount[i] # 새로 들어오는 항목
window[out_item] -= 1
window[in_item] = window.get(in_item, 0) + 1
if is_match():
answer += 1
return answerfunction solution(want, number, discount) {
let answer = 0;
// 1. 목표 상태 맵핑
const target = {};
for (let i = 0; i < want.length; i++) {
target[want[i]] = number[i];
}
// 2. 현재 윈도우 상태 체크 함수
const isMatch = (window) => {
for (let key in target) {
if (window[key] !== target[key]) return false;
}
return true;
};
const window = {};
// 3. 첫 10일(초기 윈도우) 세팅
for (let i = 0; i < 10; i++) {
window[discount[i]] = (window[discount[i]] || 0) + 1;
}
if (isMatch(window)) answer++;
// 4. 슬라이딩 윈도우 진행
for (let i = 10; i < discount.length; i++) {
const outItem = discount[i - 10]; // 빠져나가는 항목
const inItem = discount[i]; // 새로 들어오는 항목
window[outItem] -= 1;
window[inItem] = (window[inItem] || 0) + 1;
if (isMatch(window)) answer++;
}
return answer;
}import java.util.HashMap;
class Solution {
public int solution(String[] want, int[] number, String[] discount) {
int answer = 0;
HashMap<String, Integer> target = new HashMap<>();
for (int i = 0; i < want.length; i++) {
target.put(want[i], number[i]);
}
HashMap<String, Integer> window = new HashMap<>();
// 첫 10일(초기 윈도우) 세팅
for (int i = 0; i < 10; i++) {
window.put(discount[i], window.getOrDefault(discount[i], 0) + 1);
}
if (isMatch(target, window)) answer++;
// 슬라이딩 윈도우 진행
for (int i = 10; i < discount.length; i++) {
String outItem = discount[i - 10]; // 빠져나가는 항목
String inItem = discount[i]; // 새로 들어오는 항목
window.put(outItem, window.get(outItem) - 1);
window.put(inItem, window.getOrDefault(inItem, 0) + 1);
if (isMatch(target, window)) answer++;
}
return answer;
}
private boolean isMatch(HashMap<String, Integer> target, HashMap<String, Integer> window) {
for (String key : target.keySet()) {
if (!window.containsKey(key) || !window.get(key).equals(target.get(key))) {
return false;
}
}
return true;
}
}반복문을 무작정 돌리기 전에, 먼저 첫 번째 창문(인덱스 0부터 K-1까지)의 상태를 세팅해두어야 합니다. 이 초기 작업 없이 바로 i - k 인덱스에 접근하려고 하면 에러가 발생하거나 엉뚱한 값이 나옵니다.
루프 안에서 빠져나가는 원소를 뺄 때 인덱스를 헷갈리기 쉽습니다. 현재 새로 들어오는 원소의 인덱스가 i이고 윈도우 크기가 k라면, 이번 턴에 창문 밖으로 밀려나는 원소의 인덱스는 정확히 i - k 입니다. (i - k + 1이나 i - k - 1로 잘못 계산하지 않도록 주의하세요.)
주어진 배열의 전체 길이가 요구하는 윈도우의 크기 K보다 작을 수 있습니다. 창문을 만들 수조차 없는 상황이므로, 로직 시작 전에 if (arr.length < k) 와 같은 방어 코드(예외 처리)를 넣어두는 것이 안전합니다.