투 포인터 알고리즘
투 포인터 알고리즘은 두 개의 포인터를 이동해가며 배열, 리스트, 문자열 등에서 원하는 값을 찾는 알고리즘이다. 여기서 포인터(Pointer)는 영어 뜻 그대로 특정 지점(index)를 가리키는 역할을 한다.
아래 문제를 통해 어떻게 동작하는지 이해해보자.
백준 #2018 : 수들의 합 5
문제
어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.
예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.
N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.
입력
첫 줄에 정수 N이 주어진다.
출력
입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오
예제 입력 1
15
예제 출력 1
4
방향 설정
이 문제는 자연수 N을 연속된 자연수의 합으로 나타내는 가지수를 구하는 문제이다.
문제 조건에서 N의 범위가 1 ≤ N ≤ 10,000,000으로 완전 탐색(Brute Force) 알고리즘을 사용하면 시간 복잡도가 O(N^2)이 되므로, O(N)의 시간복잡도를 가진 알고리즘을 사용해야 할 필요가 있다.
이때 투 포인터 알고리즘의 사용을 생각해볼 수 있다.
여기서는 N이 5일때를 예로 들어보겠다.
먼저 1부터 입력받은 자연수 5까지의 자연수가 담긴 배열을 생성한 후, 시작 포인터와 종료 포인터를 만들고 초기값을 1로 설정해보자.
이때 선택된 구간은 [1]이고, 구간합은 1이다.
우리가 만족해야 하는 구간합의 값은 5이므로, 현재 구간합 1은 목표값 5보다 작다.
따라서 종료 포인터(e)를 오른쪽으로 한칸 이동시켜 보자.
이제 선택된 구간은 [1, 2]이고, 구간합은 1+2=3이다.
이때 구간합을 갱신하기 위해서 다시 구간안에서 반복문을 돌릴 필요가 없다. 기존의 구간합 1에 새롭게 추가된 종료 포인터의 위치 2만 더해주면 되는 것이다.
아직 구간합 3이 목표값인 5보다 작으므로, 위와 같은 과정으로 종료 포인터를 오른쪽으로 한 칸 더 옮겨준다.
이제 선택된 구간은 [1, 2, 3]이고 구간합은 기존 구간합 3에 새롭게 추가된 3을 더한 6이다.
구간합 6이 목표값인 5보다 커졌다. 따라서 이번엔 시작 포인터를 오른쪽으로 한 칸 옮겨보자.
이제 선택된 구간은 [2, 3]이고, 구간합은 기존 구간합 6에서 왼쪽에 삭제된 값 1을 뺀 5이다.
구간합 5가 목표값 5와 같아졌다.
조건에 부합하는 경우를 발견했으므로, 경우의 수 하나를 카운트하면 된다.
그 다음 다시 종료 포인터를 오른쪽으로 한 칸 옮긴다.
이러한 과정을 종료 포인터가 끝점인 5에 도달할 때까지 반복하면 문제 조건에 부합하는 경우의 수를 모두 카운트할 수 있게 된다.
이것이 투 포인터 알고리즘의 로직이다.
정리하자면 아래와 같다.
- 현재값>목표값 →
sum = sum - 시작포인터 값;,시작포인터++;
- 현재값<목표값 →
종료포인터++; sum = sum,종료포인터 값;
- 현재값==목표값 →
종료포인터++; sum = sum,종료포인터 값; 경우의수++;
이를 코드로 구현하면 아래와 같다.
import java.util.Scanner; public class Main { public static void main(String[] args) { int N; Scanner sc = new Scanner(System.in); N = sc.nextInt(); int sPt=1, ePt = 1, sum=1, count = 1; while(ePt != N) { if(sum>N) { sum-=sPt; sPt++;} else if(sum<N) { ePt++; sum+=ePt; } else if(sum==N) { count++; ePt++; sum+=ePt; } } System.out.println(count); } }
여기서는 배열을 만들 필요 없이 포인터의 위치가 곧 배열의 값이므로 시작포인터(sPt)와 종료포인터(ePt)를 직접 구간합 계산에 사용해주었다. 또한 시작과 동시에 선택된 구간이 [1]이므로 sum을 1로 초기화해주었다.
또 while문이 ePt가 N과 일치하지 않을때 반복되므로 마지막에 있는 목표값 자기 자신을 미리 카운트하기 위해 count 값을 1로 초기화하였다. (while 탈출 조건에 따라서 0으로 지정할 수도 있겠다)
결과 | 메모리 | 시간 |
맞았습니다!! | 17712 KB | 244 ms |
이와 매우 유사한 다음 문제를 풀어보자.
백준 #2003 : 수들의 합 2
문제
N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.
출력
첫째 줄에 경우의 수를 출력한다.
예제 입력 1
4 2 1 1 1 1
예제 출력 1
3
예제 입력 2
10 5 1 2 3 4 2 5 3 1 1 2
예제 출력 2
3
풀이 방향은 위와 동일하다. 차이점이라면 위의 문제에서는 포인터의 위치(index)가 곧 구간합을 구해야하는 배열의 값이었지만, 이 문제의 경우 직접 입력받은 배열의 값을 이용해 합을 더하고 비교해야 한다는 것이다.
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.nio.Buffer; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { int N, M; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); int A[] = new int[N]; st = new StringTokenizer(br.readLine()); for(int i=0; i<N; i++) { A[i] = Integer.parseInt(st.nextToken()); } //여기까지 입력 로직 int i = 0, j = 0, sum=A[0], count = 0; //투 포인터 while(j != N) { if(sum>M) { sum-=A[i]; i++;} else if(sum<M) { j++; if(j < N) sum+=A[j]; } else if(sum==M) { count++; j++; if(j < N) sum+=A[j]; } } System.out.println(count); } }
시작 포인터(i)와 종료 포인터(j)를 모두 0으로 초기화하고(배열 index값이 0부터 시작하므로) sum값을 처음 구간인 입력받은 배열의 0번째 값 A[0]으로 설정해준다.
아래는 위의 문제와 동일한 방식으로 구간합에 포인터 위치가 아닌 실제 배열의 값을 더하고 빼주면 된다.
결과 | 메모리 | 시간 |
맞았습니다!! | 14960 KB | 156 ms |
이번엔 구간의 합이 아닌 포인터가 있는 양 끝 값의 합을 비교해아하는 문제를 풀어보자.
백준 #1940 : 주몽
문제
주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.
갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.
예제 입력 1
6 9 2 7 4 1 5 3
예제 출력 1
2
역시 위의 문제들과 풀이 방향은 동일하다.
바로 코드를 작성해보자.
import java.io.IOException; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { int N, M; Scanner sc = new Scanner(System.in); N = sc.nextInt(); M = sc. nextInt(); int nums[] = new int[N]; for(int i=0; i<N; i++) { nums[i] = sc.nextInt(); } Arrays.sort(nums); //오름차순 정렬 int count = 0; int sPt=0, ePt = N-1; while(sPt < ePt) { int sum = nums[sPt] + nums[ePt]; if(sum>M) { ePt--; } else if(sum<M) { sPt++; } else if(sum==M) { count++; sPt++; ePt--; } } System.out.println(count); } }
양 끝 값(nums[sPt] + nums[ePt])을 더한 값과 목표값을 비교해가며 투 포인터 알고리즘을 수행하면 된다.
코드를 보면 위의 문제들과 차이점이 있는데, 위의 문제들은 모두 0번에서 시작 포인터와 종료 포인터를 모두 출발시키며 탐색했다면 이 문제에서는 시작 포인터는 0, 끝 포인터는 끝점에 두고 양쪽에서 좁혀오는 방식으로 구현해보겠다.
- 현재값>목표값 → 종료 포인터를 왼쪽으로 한 칸 이동
- 현재값<목표값 → 시작 포인터를 오른쪽으로 한 칸 이동
- 현재값==목표값 → 발견! 시작 포인터는 오른쪽으로 한 칸, 종료 포인터는 왼쪽으로 한 칸 이동
결과 | 메모리 | 시간 |
맞았습니다!! | 34356 KB | 472 ms |
끝으로 투 포인터 알고리즘과 매우 유사한 슬라이딩 윈도우 알고리즘에 대해 알아보자.
슬라이딩 윈도우
슬라이딩 윈도우 알고리즘은 투 포인터 알고리즘과 달리 탐색구간의 길이가 고정되어 있다. 말 그대로 같은 길이의 윈도우를 그대로 이동시키며 결과값을 구하는 방식이다.
역시 문제를 하나 풀어보자.
백준 #12891 : DNA 비밀번호
문제
평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다.
하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에 취약한 비밀번호가 만들어 질 수 있기 때문이다. 그래서 민호는 부분문자열에서 등장하는 문자의 개수가 특정 개수 이상이여야 비밀번호로 사용할 수 있다는 규칙을 만들었다.
임의의 DNA문자열이 “AAACCTGCCAA” 이고 민호가 뽑을 부분문자열의 길이를 4라고 하자. 그리고 부분문자열에 ‘A’ 는 1개 이상, ‘C’는 1개 이상, ‘G’는 1개 이상, ‘T’는 0개 이상이 등장해야 비밀번호로 사용할 수 있다고 하자. 이때 “ACCT” 는 ‘G’ 가 1 개 이상 등장해야 한다는 조건을 만족하지 못해 비밀번호로 사용하지 못한다. 하지만 “GCCA” 은 모든 조건을 만족하기 때문에 비밀번호로 사용할 수 있다.
민호가 만든 임의의 DNA 문자열과 비밀번호로 사용할 부분분자열의 길이, 그리고 {‘A’, ‘C’, ‘G’, ‘T’} 가 각각 몇번 이상 등장해야 비밀번호로 사용할 수 있는지 순서대로 주어졌을 때 민호가 만들 수 있는 비밀번호의 종류의 수를 구하는 프로그램을 작성하자. 단 부분문자열이 등장하는 위치가 다르다면 부분문자열이 같다고 하더라도 다른 문자열로 취급한다.
입력
첫 번째 줄에 민호가 임의로 만든 DNA 문자열 길이 |S|와 비밀번호로 사용할 부분문자열의 길이 |P| 가 주어진다. (1 ≤ |P| ≤ |S| ≤ 1,000,000)
두번 째 줄에는 민호가 임의로 만든 DNA 문자열이 주어진다.
세번 째 줄에는 부분문자열에 포함되어야 할 {‘A’, ‘C’, ‘G’, ‘T’} 의 최소 개수가 공백을 구분으로 주어진다. 각각의 수는 |S| 보다 작거나 같은 음이 아닌 정수이며 총 합은 |S| 보다 작거나 같음이 보장된다.
출력
첫 번째 줄에 민호가 만들 수 있는 비밀번호의 종류의 수를 출력해라.
예제 입력 1
9 8 CCTGGATTG 2 0 1 1
예제 출력 1
0
예제 입력 2
4 2 GATA 1 0 0 1
예제 출력 2
2
방향 설정
- 입력
우선 이 문제는 DNA 문자열을 ‘문자열’ 형태로 입력받아야 한다. 입력 받은 문자열을 한 글자씩 배열에 넣기 위해서 String 형태로 문자열을 받아온 후(띄어쓰기 없으므로) 이를
toCharArray() 메서드를 사용해 한 글자씩 담긴 char 배열로 변환하여 저장한다.그 다음 먼저 이 DNA 배열의 index를 하나씩 증가시키며 Add() 함수를 호출한다.
이후 슬라이딩 윈도우를 하나씩 오른쪽으로 이동시키며 왼쪽에 제거되는 값은 Remove하고, 오른쪽에 추가되는 값을 Add한다.
이때 각 각 Add와 Remove 함수에서는 해당 문자열이 A, C, G, T인지 확인하고 현재 구간에서의 A, C, G, T의 개수를 저장해두는 배열에 해당 문자열 개수를 하나씩 증가시키거나 감소시킨다.
윈도우를 이동시킬 때 마다 Check를 수행하는데, Check 함수에서는 입력에서 받아온 문자 별 개수 조건과 현재 구간에서 카운트된 문자 별 개수가 일치하는 지를 체크한다.
코드는 다음과 같다.
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Scanner; import java.util.StringTokenizer; public class Main { static int[] currentCheckArr = new int[4]; static int[] checkArr = new int[4]; //A C G T static int cnt = 0; public static void main(String[] args) throws IOException { int S, P; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); S = Integer.parseInt(st.nextToken()); P = Integer.parseInt(st.nextToken()); char[] DNA = br.readLine().toCharArray(); st = new StringTokenizer(br.readLine()); checkArr[0] = Integer.parseInt(st.nextToken()); checkArr[1] = Integer.parseInt(st.nextToken()); checkArr[2] = Integer.parseInt(st.nextToken()); checkArr[3] = Integer.parseInt(st.nextToken()); // 여기까지 입력 // 첫번째 세트 카운트 for(int i=0; i<P; i++) { Add(DNA[i]); } Check(); // 슬라이딩 윈도우 구현 (s: 시작점, e: 끝점) for(int e=P; e<S; e++) { int s = e-P; Remove(DNA[s]); //시작점 제거 Add(DNA[e]); //끝점 추가 Check(); } System.out.println(cnt); } private static void Check() { if(currentCheckArr[0] >= checkArr[0] && currentCheckArr[1] >= checkArr[1] && currentCheckArr[2] >= checkArr[2] && currentCheckArr[3] >= checkArr[3] ) { //조건 만족 cnt++; } } private static void Add(char c) { switch(c) { case 'A': currentCheckArr[0]++; break; case 'C': currentCheckArr[1]++; break; case 'G': currentCheckArr[2]++; break; case 'T': currentCheckArr[3]++; break; } } private static void Remove(char c) { switch(c) { case 'A': currentCheckArr[0]--; break; case 'C': currentCheckArr[1]--; break; case 'G': currentCheckArr[2]--; break; case 'T': currentCheckArr[3]--; break; } } }
결과 | 메모리 | 시간 |
맞았습니다!! | 21948 KB | 316 ms |
문제 조건에 따라 포인터 알고리즘과 슬라이딩 윈도우 알고리즘은 중복 연산을 줄일 수 있는 효과적인 방법이 될 수 있다.
댓글