알고리즘 및 코테 복습 - 구간합, 투포인터, 스택과 큐

⬛ 03. 자료 구조

⬛ 03-2. 구간 합

• S[i] = S[i-1] + A[i]
• i ~ j까지의 구간 합 구하기 : S[j] - S[i-1]

---

🟦 백준 11659번. 구간 합 구하기

• S[i] 는 1~i까지의 합 : 먼저 구해놓고,
• M개의 입력받은 구간 a,b 사잇 구간합을 구해서 출력

import java.util.ArrayList;
import java.util.Scanner;

//11659번. 구간 합 구하기 4
public class Main {
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int N = kb.nextInt();
		int M = kb.nextInt();
		int[] A = new int[N+1];
		int[] S = new int[N+1];
		
		for(int i=1; i<=N; i++) {
			A[i] = kb.nextInt();
		}
		
		S[1] = A[1];
		for(int i=2; i<=N; i++) {
			S[i] = S[i-1] + A[i];// 구간 합 구해두고 
		}
		
		ArrayList<Integer > answer = new ArrayList<>();
		for(int i=0; i<M; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			answer.add(S[b] - S[a-1]);
		}
		//정답 출력 
		for(int x : answer ) System.out.println(x);
	}
}

---

🟦 백준 11660번. 구간 합 구하기 2

• 점화식 정의도 해야 한다.

1) DP[X][Y] = 0,0 ~ x,y 까지의 구간 합을 미리 구해두는 것

2) 1행과 1열에 대한 초기화 필요

D[i][1] = D[i-1][1] + A[i][1];
//즉, 1행 쪽은 (왼쪽값 + 현재값)

D[1][j] = D[1][j-1] + A[1][j];
//즉, 1열 쪽은 (윗쪽값 + 현재값)

3) 이제 D[i][j] 의 값을 채우는 구간 합 공식 필요

왼쪽값 + 위쪽값 - (왼쪽대각선 겹치는 부분 제외) + 현재값

D[i][j] = D[i-1][j] + D[i][j-1] + D[i-1][j-1] + A[i][j];

4) 질의 구간합 구하는 공식 필요

(X1, Y1) (X2, Y2) 들어오면 

D[X2][Y2] - D[X1-1][Y2] - D[X2][Y2-1] + D[x1-1][y1-1] 

코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int N = kb.nextInt();
		int M = kb.nextInt();
		
		int[][] A = new int[N+1][N+1];
		//입력 데이터 세팅 
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				A[i][j] = kb.nextInt();
			}
		}
		
		//구간 합 구해놓기 1행 1열 초기화 
		int[][] D = new int[N+1][N+1];
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				//구간 합 초기화 
				//왼쪽 + 위쪽 - 대각선쪽 + 현재값
				D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][j-1] + A[i][j];
			}
		}
		
		//이제 각 구간별 질의 대답 정하기 
		ArrayList<Integer> answer = new ArrayList<>();
		
		for(int i=0; i<M; i++) {
			int x1 = kb.nextInt();
			int y1 = kb.nextInt();
			int x2 = kb.nextInt();
			int y2 = kb.nextInt();
			
			int tmp = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1];
			answer.add(tmp);
		}
		//정답 출력 
		for(int x : answer) System.out.println(x);
	}
}

---

⬛ 03-3. 투 포인터

• while(i<j) 문 돌면서, 찾고자 하는 값 타나나기 전까지 i와 j를 움직이는 방식

🟦 백준 2018번. 연속된 자연수 합 구하기

• [주의] 여기서 cnt=1로 초기화 하는 이유 : 15 자기 자신을 뽑는 1가지 경우를 미리 세팅한 것.

import java.util.Scanner;

/*2018번 수들의 합 */
public class Main {
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int N = kb.nextInt();
		
		int st =1, ed =1;
		int sum =1;
		int cnt = 1;
		while(ed != N) {
			if(sum == N) {
				cnt++;
				ed++;
				sum += ed;
			}else if(sum <N) {
				ed++;
				sum += ed;
			}else if(sum > N) {
				sum -= st;
				st++;
			}
		}
		System.out.println(cnt);
	}
}

---

🟦 백준 1940번. 주몽의 명령

import java.util.Arrays;
import java.util.Scanner;

/*1940번. 주몽의 명령 */
public class Main {
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int N = kb.nextInt(); //재료개수 
		int M = kb.nextInt(); //타겟값 
		
		int[] A = new int[N];
		
		for(int i=0; i<N; i++) {
			A[i] = kb.nextInt();
		}
		//1) 정렬 시킴 오름차순 
		Arrays.sort(A);
		
		//2) 왼, 오 포인터로 찍으면서 답찾기 
		int cnt = 0;
		int st = 0, ed = N-1;
		int sum = 0;
		while(st<ed) {
			sum = A[st] + A[ed];//두 재료의 합 
			if(sum == M) { //정답 찾으면 
				cnt++;
				st++;
				ed--;
			}else if(sum < M) { //값이 작으면 
				st++;
			}else if(sum > M) { //값이 더 크면 
				ed--;
			}
		}	
		System.out.println(cnt);//출력 
	}
}

---

🟦 백준 1253번. 좋은 수 구하기

package to_0717_5;

import java.util.Arrays;
import java.util.Scanner;

/*1253번. 좋은 수 구하기 */
public class Main {
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int N = kb.nextInt();
		long[] A = new long[N];
		for(int i=0; i<N; i++) A[i] = kb.nextLong();
		
		Arrays.sort(A);//오름차순 정렬 시켜놓고 
		
		int cnt=0;
		for(int k=0; k<N; k++) {
			long find = A[k];
			int st = 0;
			int ed = N-1;
			while(st < ed) {
				if(A[st] + A[ed] == find) {
					if(st != k && ed !=k ) {
						cnt++;
						break;
					}else if(st == k) { //자기 자신 제외
						st++;
					}else {//자기 자신 제외
						ed--;
					}
				}else if(A[st]+A[ed] < find) {
					st++;
				}else {
					ed--;
				}
			}
		}
		//정답 출력 
		System.out.println(cnt);
	}
}

---

⬛ 03-5. 스택과 큐

• 스택 : 후입선출
• 큐 : 선입선출

🟦 백준 2164번. 카드 게임

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/*2164번. 카드2 */
public class Main {
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int N = kb.nextInt();
		Queue<Integer> Q = new LinkedList<>();
		//값 넣기 
		for(int i=1; i<=N; i++) Q.add(i);
		
		while(Q.size() > 1) {
			//1) 첫장은 버리기 
			Q.poll();
			//2) 그 다음 장은 맨 뒤에 담기 
			Q.add(Q.poll());
		}		
		if(Q.size() == 1) {
			int tmp = Q.poll();
			System.out.println(tmp);//가장 마지막에 남은 카드 출력 
		}
	}
}