투 포인터
투 포인터(Two Pointers)는 두 개의 포인터를 이용해 문제를 효율적으로 해결하는 알고리즘 기법입니다.
이 기법은 주로 정렬된 배열이나 연속적인 구간에서 조건을 만족하는 값을 찾을 때 사용됩니다.
투 포인터 사용 이유 🤔
투 포인터는 O(N) 또는 O(N log N)의 시간복잡도로 문제를 해결할 수 있으며, 특히 정렬된 배열에서 최적화된 탐색이 가능하다는 점이 큰 장점 입니다.
투 포인터의 기본 동작 방식 🎯
포인터 초기화
보통 시작점 left 와, 끝점 right 를 배열의 양 끝에 둡니다.
조건 확인
두 포인터가 가리키는 값이 조건을 만족하는지 확인합니다.
포인터 이동
조건에 따라 왼쪽 포인터 또는 오른쪽 포인터를 이동시킵니다.
포인터가 서로 교차할 때까지 반복
두 포인터가 교차하면 탐색을 종료합니다.
문제로 보는 투 포인터
연속된 자연수의 합 구하기 (백준 2018)
문제

출력

풀이
투 포인터 이동 원칙
sum > N 일 때,
sum = sum - start_index; / start_index++;
sum < N 일 때,
end_index++; / sum = sum + end_index;
sum == N 일 때,
end_index++; / sum = sum + end_index; / count++;

count를 1로 초기화 하는 이유는 N = 15 일 때, 숫자를 15만 뽑는 경우의 수를 미리 넣고 초기화 했기 때문입니다.

sum < N 일 때,
end_index++; / sum = sum + end_index;
10 < 15 일 때,
end_index ++; / sum = 10 + 5 를 실행

sum == N 일 때,
end_index++; / sum = sum + end_index; / count++;
15 == 15 일 때,
end_index++; / sum = 15 + 6 / count ++;
( N과 sum을 비교하여 값이 같으므로 count++ 을 해줍니다. )

sum > N 일 때,
sum = sum - start_index; / start_index++;
21 > 15 일 때,
sum = 21 - 1 / start_index ++;

코드
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()); // 15
int N = Integer.parseInt(st.nextToken());
// 시작 값 초기화
int start_index = 1;
int end_index = 1;
int sum = 1;
int count = 1;
while (end_index != N) { // end_index가 N에 도착하면 종료
if (sum == N) {
count++;
end_index++;
sum += end_index;
} else if (sum < N) {
end_index++;
sum += end_index;
} else { // sum > N
sum -= start_index;
start_index++;
}
}
System.out.print(count);
}
}
투 포인터, 문제를 통해 배우다 ✍️
투 포인터는 개념적으로 설명하기보다 문제를 풀어보며 배우는 것이 가장 효과적입니다.
그래서 간단한 문제를 풀어보며 투 포인터의 작동 방식을 학습해 보았습니다! 😊
'해피 코딩 > 알고리즘' 카테고리의 다른 글
[백준 1929] 문제로 이해하는 에라토스테니스의 체 JAVA (0) | 2024.12.16 |
---|---|
[이론] 병합 정렬 알고가기 (0) | 2024.12.12 |
[이론] 버블 정렬 알고가기 (3) | 2024.12.05 |
[이론] 구간 합, 합 배열 구하기 (2) | 2024.12.05 |
[알고리즘] 시간 복잡도 최대한 쉽게 이해하기 (36) | 2024.11.27 |