'Do it! 알고리즘 코딩테스트 자바 편' 교재로 공부한 내용을 정리했습니다
투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화 시키는 알고리즘이다.
알고리즘이 매우 간단하여 문제를 풀면서 이해를 해봅시다.
백준 2018 번
https://www.acmicpc.net/problem/2018
2018번: 수들의 합 5
어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한
www.acmicpc.net
1. 문제분석
먼저 시간 복잡도 분석으로 사용할 알고리즘의 범위부터 줄여야 한다.
주어진 N 의 최대값은 10,000,000 이다. 만약 이 문제를 O(nlogn) 으로 푼다면 제한시간이 초과될 것이다. 아래와 같은 연산으로 연산 시간을 예측할 수 있다.
연산회수 = 알고리즘 시간 복잡도 ✕ 데이터의 크기
이 문제에서는 10⁷ ✕ log₂10⁷ = 약 230,000,000 (2억 3천만).
연산 회수 1억번에 1초로 계산하므로 2초를 초과한다.
그러므로 O(n) 시간 복잡도 알고리즘을 사용해야 한다.
이 경우 자주 사용하는 방법이 투 포인터이다. 연속된 자연수의 합을 구하는 문제에서는 시작 Index 와 종료 index 을 지정하여 연속된 수를 표현한다. 시작 인덱스와 종료 인덱스는 투 포인터로 지정한다.
2. 손으로 풀기
1. 먼저 N 에 입력한 값을 저장한다. 그리고 sum과 count 변수, index 변수를 초기화해준다.
만약 N = 15 이면 아래 그림처럼 될 것이다.
2. 그리고 아래 설명하는 투 포인터 이동 원칙을 사용하여 배열의 끝까지 탐색하여 합이 N 이 되는 경우의 수를 count 한다.
start_index 을 오른쪽으로 한 칸 이동한다는 것은 연속된 자연 수에서 왼쪽 값(가장 작은 수)을 삭제하는 것이고
end_index 을 오른쪽으로 한 칸 이동한다는 것은 연속된 자연수의 범위를 한 칸 더 확장한다는 것이다.
이렇게 index 을 옮겨가면서 sum 을 계산하고 이를 N 과 비교한다.
투 포인터 이동 원칙
if (sum > N ){
sum = sum - start_index;
start_index ++
}
if (sum < N ){
end_index++;
sum = sum + end_index;
}
if (sum == N ){
end_index++;
sum = sum + end_index;
count++;
}
3. 2단계를 end_index 가 N 이 될 때까지 반복한다. 포인터가 이동할 때마다 현재의 총합 sum 과 N 을 비교하면 된다.
3. 슈도코드
/*
N 변수 저장
사용 변수 초기화 (count = 1, start_index = 1, end_index = 1, sum = 1)
while (end_index != N){
if(sum == N) -> count++, end_index++, sum 누적
else if(sum >N) sum 변경, start_index 증가
else if(sum <N) end_index 증가 sum 변경,
}
count 출력
*/
4. 구현
public class BaekJoon2018 {
public static void main(String[] args) {
// N 입력받고 저장
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int count = 1; // 처음 count 는 N 자신 그대로인 경우 고려하여 1로 설정.
int start_index = 1;
int end_index = 1;
int sum = 1;
while (end_index != N) {
if (sum == N) {
count++;
end_index++;
sum += end_index;
} else if (sum > N) {
sum -= start_index;
start_index++;
} else {
end_index++;
sum += end_index;
}
}
System.out.println(count);
}
}
백준 1940 번
https://www.acmicpc.net/problem/1940
1940번: 주몽
첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고
www.acmicpc.net
1. 문제분석
먼저 시간복잡도를 고려해 봅시다. 두 재료의 합(크기)를 비교하므로 입력되는 재료의 고유번호들 값을 정렬한다면 더 쉽게 풀 수 있을 것이다. 일반적으로 정렬 알고리즘의 시간 복잡도는 O(n logn) 이다.
N의 최대는 15,000 이다. 이 값은 O(n logn) 시간 복잡도 알고리즘을 사용할 수 있다. 즉, 정렬을 사용할 수 있다.
15,000 ✕ (log₂15000) = 207,000 (20만).
입력받은 N 개의 재료값을 정렬한 다음 양쪽의 끝을 투 포인터로 지정해서 문제에 접근합니다.
2. 손으로 풀기
1. 재료를 A[N] 에 저장한 후 정렬한다.
2. 투 포인터 i, j 을 위치시키고 이 문제에 맞는 투 포인터 원칙을 생각해봅시다.
투 포인터 원칙
A[i] + A[j] > M 일 때 j--;
A[i] + A[j] < M 일 때 i++;
A[i] + A[j] == M 일 때 count++; i++; j--;
3. 2단계를 i == j 가 될 때까지 반복한다.
반복이 종료되면 count 을 출력합니다.
3. 슈도코드
N(재료의 개수) 을, M (갑옷이 되는 재료 고유번호의 합) 을 입력받고 저장한다.
for (N 만큼 반복){
재료 배열 저장
}
재료 배열을 오름차순으로 정렬
while(i < j){
if (재료 합 < M) 작은 번호 재료를 한 칸 위로 변경.
else if ( 쟈료 합 > M) 큰 번호 재료를 한 칸 아래로 변경.
else (재료 합 == M) count++; 작은 번호, 큰 번호 모두 변경.
}
count 출력.
4. 구현
public class BaekJoon1940 {
public static void main(String[] args) throws IOException {
BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(rd.readLine()); // 재료 개수
int M = Integer.parseInt(rd.readLine()); // 갑옷의 번호가되는 재료 2개의 합.
StringTokenizer st = new StringTokenizer(rd.readLine());
int arr[] = new int[N];
for (int index = 0; index < N; index++) {
arr[index] = Integer.parseInt(st.nextToken());
}
// 오름차순 정렬
Arrays.sort(arr);
int i = 0;
int j = N - 1;
int count = 0;
while (i < j) {
if ( (arr[i] + arr[j]) < M) {
i++;
} else if ((arr[i] + arr[j]) > M) {
j--;
} else { // (arr[i] + arr[j]) = M
count++;
i++;
j--;
}
}
System.out.println(count);
}
}
백준 1253 번
https://www.acmicpc.net/problem/1253
1253번: 좋다
첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)
www.acmicpc.net
1. 문제분석
역시 시간 복잡도부터 계산해봅시다. N 이 2,000 이어도 사용 알고리즘은 N² 보다 작아야 합니다. 왜냐하면 N 은 탐색 대상이 되는 수이고 각 수마다 반복을 한번 더 돌려야 하기 때문입니다.
만약 알고리즘의 시간 복잡도가 N² 이라면 최종 시간 복잡도는 O(N³) 가 되어서 2,000³ = 80,000,000,000 가 됩니다.
그러므로 nlogn 시간 복잡도 알고리즘, 즉 정렬과 투 포인터 알고리즘을 사용하면 됩니다.
(2,000)² ✕ ㏒₂(2000) = 44,000,000 (4천만)
단 정렬된 데이터에서 좋은 수인지 판단하는 수가 K 일 때 자기 자신 K 을 좋은 수 만들기에 포함하면 안됩니다!
2. 손으로 풀기
1. N 을 입력받고 배열에 저장한 후 정렬한다.
2. 투 포인터 i, j 을 배열 양 끝에 위치시킨다.
투 포인터 이동원칙을 고안하고 그에 따라 i, j 가 변하도록 하여 탐색한다. 탐색 대상 수를 K 라고 하면
투 포인터 이동 원칙
A[i] + A[j] > K 이면 j--;
A[i] + A[j] < K 이면 i++;
A[i] + A[j] == K 이면 count++; i++; j--
3. 2단계를 배열의 모든 수에 대해 반복한다. 즉, K = 배열[N-1] 이 될 때까지 반복한다.
3. 슈도코드
수의 개수 N 입력받기
count 선언
수 데이터 저장 배열 A
for (N 만큼){
A 배열에 데이터 저장
}
A 배열 정렬
for (배열 A 의 크기만큼 반복){
변수 초기화. 찾을 값, 투 포인터
while(i < j){
if (A[i] + A[j] == 찾고자 하는 값){
두 포인터 i, j가 k 가 아니면 결과 값에 반영, while 문 종료
두 포인터 i, j가 k 가 맞을 때 포인터 변경 및 계속 수행.
}
else if(A[i] + A[j] < 찾고자 하는 값) {
i++;
}
else (A[i] + A[j] > 찾고자 하는 값) j--;
}
}
count 출력4. 구현
public class BaekJoon1253 {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bufferedReader.readLine());
int count = 0;
long A[] = new long[N];
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for (int i = 0; i < N; i++) {
A[i] = Long.parseLong(stringTokenizer.nextToken());
}
Arrays.sort(A);
for (int index = 0; index < A.length; index++) {
long find = A[index];
int i = 0;
int j = N - 1;
while (i < j) {
if (A[i] + A[j] == find) {
if (i != index && j != index) {
count++;
break;
} else if (i == index) {
i++;
} else if (j == index) {
j--;
}
} else if (A[i] + A[j] < find) {
i++;
} else { // A[i] + A[j] > find
j--;
}
}
}
System.out.println(count);
}
}
여기까지 투 포인터 알고리즘을 활용한 알고리즘 문제 3 개를 풀어보았다.
바로 다음 글에서는 슬라이딩 윈도우 알고리즘 관련 문제 두 개를 더 풀어볼 것인데.... 이게 하루에 금방 할 수 있다고 생각했는데 생각보다 시간이 오래걸리네요.... ㅎ
'Java > 코딩테스트' 카테고리의 다른 글
| [Java] 코딩테스트 BufferedReader, BufferedWriter 을 쓰는 이유 (0) | 2023.05.21 |
|---|---|
| 스택 & 큐 - 자바 백준 스택수열: 1874 오큰수: 17298 (0) | 2023.05.21 |
| 자바 코딩 테스트 - 슬라이딩 윈도우. 백준 12891, 11003 문제 (1) | 2023.01.05 |
| 자바 코딩 테스트 - 구간 합. 백준 11659 , 11660, 10986 문제 (0) | 2023.01.02 |
| 자바 코딩 테스트 - 배열과 리스트, 백준 11720, 1546 문제 (0) | 2023.01.02 |