투 포인터
굳이 정답을 찾기 위해 모든 부분을 봐야하는가?
-
화살표 두 개에 의미를 부여해서 탐색 범위를 압축하는 방법
1. 1차원 배열 위에 2개의 포인터를 만드는 경우
1. 2개의 포인터가 모두 왼쪽에서 시작해 같은 방향으로 이동R이 3칸 가면, L이 1칸 , 그럼 또 R이 또 감, L이 쫓아감 2. 2개의 포인터가 양 끝에서 서로를 향해 이동 2. 관찰을 통해서 문제에 등장하는 변수 2개의 값을 두 포인터로 표현하는 경우-
꿀 팁 키워드
- 1차원 배열에서의 “연속 부분 수열”
- “순서를 지키며 차례대로”
- 곱의 최소
- A가 커지면 B가 작아지니까, 하나가 늘면 하나가 줄어드니까
BOJ_1806
연속된 수들의 부분합중에 그 합이 S 이상이 되는 것 중 가장 짧은 것의 길이
- 원소의 개수 N, 기준합 S,
- 정답의 최대치
- N = 100,000
S = 10^8- 정답이 N이하, 100,000이하 → Intger 범위
모든 원소의 총합도 10^9(10^5*10^4) → Intger 범위
- 왼쪽 시작 L결정 > 오른쪽 끝을 R을 L부터 시작해서 이동 하며 S 넘는지 확인 → O(N^2)
- 왼쪽 시작 L의 이동 > 오른쪽 끝 R을 이전의 R부터 시작해서 이동 → O(N)
- 정답이 N이하, 100,000이하 → Intger 범위
- 구현
static void pro(){ int R = 0, sum = 0, ans = n + 1; //ans=s를 넘는 값들 중 가장 짧은거 기록 for(int L = 1;L <= n;L++){ // L - 1 을 구간에서 제외하기 sum -= a[L - 1]; // R을 옮길 수 있을 때까지 옮기기 (합이 S보다 커지는 순간 멈춤) while(R + 1 <= n && sum < S) { R++; sum += a[R]; } //[L...R]의 합, 즉 sum이 조건을 만족하면 정답 갱신 if(sum >= S){ ans = Math.min(ans, R - L + 1); } } //ans값 보고 불가능 판단하기 if(ans == n + 1){//min이 갱신이 안됐다면 ans = 0; } System.out.println(ans); }
- N = 100,000
BOJ_2470
-
알고리즘
가장 작은수(-99) 랑 가장 큰 수(98) 랑 더해도 음수인데, 그보다 덜 작은수(-1,-2), 덜 큰수랑 더하면 안더해도 음수다. -99 + 98은 이미 좋은 애랑 했다. - 최소 + 최대 < 0 → 최소 입장에서는 최선책을 만난 상태, 짝을 찾았으니 최소(-99) 삭제  다음으로, 98이랑 -2랑 더하면 합이 양수 최대 입장에서, 굳이 덜 작은 수(-1)이랑 덜 큰수(4)를 더해야할까? - 최소 + 최대 > 0 → 최대 입장에서는, 최선택을 만난 상태, 짝을 찾았으니 최대(98) 삭제 - 이건 O(N^2) .
시발정렬하면 더 빨리 됨
- 이건 O(N^2) .
-
-
정렬 > L,R 계산 후에 이동 > O(N log N)
static void pro(){ Arrays.sort(A,1,N+1); int best_sum = Intger.MAX_VALUE; int v1 = 0, v2 = 0, L = 1, R = N; while(L < R){ int sum = A[L] + A[R]; if(Math.abs(sum) < best_sum){ best_sum = Math.abs(sum); v1 = A[L]; v2 = A[R]; } if( sum > 0 ){ R--; }else L++; sb.append(v1).append(' ').append(v2); System.out.println(sb); }BOJ_13144
수열에서 연속한 1개 이상의 수 뽑을 때 같은수가 여러번 등장하지 않는 경우의 수
-
정답의 최대치
- N + (N-1) + (N-2) … = 50억 → Long- O(N^3)의 방법
- 1️⃣ 왼쪽 시작 L > 2️⃣ 오른쪽 끝 R을 L부터 시작 > 3️⃣ R을 이동하여 추가된 원소가 기존 구간 [L,R-1]안에 있는지 확인
- O(N^2)의 방법
- 위의 “R을 이동하여 추가된 원소가 기존 구간 [L,R-1]안에 있는지 확인” 에서 숫자마다 [L,R] 안에 몇 개나 있는지를 세자 > 최대 숫자 알기에 count 배열 생성 가능
- 1️⃣ 왼쪽 시작 L > 2️⃣ 오른쪽 끝 R을 L부터 시작해서 이동 > 3️⃣ R을 이동해 추가된 원소가 [L,R-1] 안에 있는지 확인 O(1) << count 배열 사용 >>
- O(N)의 방법
- 또한, 1~3 중복된게 없다면 1~2,2~3에도 중복된게 없음 :: 경우의 수 셀 때 참고
- [L…R] 중에 L기준 R까지 가는 경우의 수 ex) [1,L2,3,R1,2] 에서, L=2일때, R=2,R=3,R=1 → 경우의 수 3 …
- 1️⃣ 왼쪽 시작 L > 2️⃣ 오른쪽 끝 R을 이전 R부터 시작 > 3️⃣ L,R이 각자 최대 N번 이동
- 구현
static void input(){ N = sc.nextInt(); A = new int[N + 1]; for(int i=1;i<=N;i++){ A[i] = sc.nextInt(); } cnt = new int[100000 + 1]; } static void pro(){ long ans = 0; for(int L=1,R=0; L<=N;L++){ // TODO : R을 옮길 수 있을 만큼 옮긴다 while( R+1<=N && cnt[A[R+1]] == 0){ // R을 옮겨도 N을 넘어가면 안되며, // 옮긴 위치 숫자가 L~R사이에 있으면 안됨 R++; cnt[A[R]]++; } // TODO : 정답을 갱신한다 ans += R - L + 1; // TODO : L을 옮겨주면서 A[L]의 개수를 감소시킨다. cnt[A[L]]--; } System.out.println(ans); - O(N^3)의 방법
BOJ_1253
N개의 수 중에서 어떤수가 다른 수 두개의 합으로 나타낼 수 있을 때, 그 갯수
- O(N^3) 의 방법
1️⃣ 타겟을 정한다 O(N) > 2️⃣ 나머지에서 2개 결정해서 만들어지나 확인 O(N^2) - O(N^2) 의 방법
1️⃣ 정렬을 한다 > 2️⃣ 타겟을 정한다 > 3️⃣ 나머지에서 다른수 2개로 (두 용액문제 풀이와 같음) - 구현
```java static boolean func(int tartget_idx){ // target_idx 번쨰 원소가 서로 다른 두 수의 합으로 표현 되는가 int L = 1, R = N; int target = A[target_idx]; while( L < R){ // TODO : if(L == target_idx) L++; else if(R == target_idx) R--; else{ if(A[L] + A[R] == target) return true; if(A[L] + A[R] > target) R--;//warning else L++; } } return false; } static void pro(){ // TODO : 최소, 최대를 빠르게 알기 위한 정렬 Arrays.sort(A,1,N+1); int ans = 0; for(int i=1;i<=N;i++){ // TOOD : i번쨰 원소가 서로 다른 두 수의 합으로 표현이 되는가 if(func(A[i])) ans++; } System.out.println(ans); } ```
BOJ_16472
최대 N개 종류의 알파벳을 가진 연속된 최대 문자열의 길이
- 정답의 최대치
- N = 26일 때, 문자열 전체 인식하므로 최대 길이인 10만이 정답 → int- 투 포인터 접근의 변형
- L = 인식 가능한 가장 왼쪽 위치
- R = 인식하고 싶은 구간의 오른쪽 끝
- cnt = 알파벳 갯수 배열
- kind = [L,R] 사이의 알파벳 종류 = cnt 배열에서 0이 아닌 것의 갯수 → R을 이동하며 [L,R] 사이의 알파벳 종류 갯수 → kind와 N을 비교하며 L의 위치 변경
- 시간 복잡도
- R을 하나씩 이동하면서 L을 조절하기 O(N)
- kind를 O(26)→O(1) 가능
- 구현
static void add(char x){ cnt[x-'a']++; if(cnt[x-'a'] == 1){ //처음 들어온거니까 kind++ kind++; } } static void erase(char x){ cnt[x-'a']--; if(cnt[x-'a'] == 0){ //방금 나간거니까 kind-- kind--; } } static void pro(){ int len = A.length(), ans = 0; for(int R=0,L=0;R<len;R++){ // TODO : R번째 문자를 오른쪽에 추가 add(A.charAt(R)); // TODO : 불가능하면, 가능할 때까지 L을 이동 while(kind > N){ erase(A.charAt(L++)); // TODO : 정답 갱신 ans = Math.max(ans,R - L + 1); } System.out.println(ans); }
- 투 포인터 접근의 변형
-
