3rd Meet - 코독하구만

Daily Object

    - 동적계획법 개념을 정리하고, 예제를 풀며 응용한다.

 

    - 웹 크롤링한 데이터를 리스트로 정리한다.

Review

    - 동적 계획법을 사용할 때 점화식을 세우는 것이 중요하다고 생각되어 N과 N+1의 상관관계를 파악하도록 노력했다.

 

    - 크롤링한 데이터를 단어 단위로 분류해봤는데 다음 시간엔 목적에 맞는 단위로 분류해봐야겠다.

 

 

Dynamic Programming

     작은 문제를 풀며 나아간다 -> 앞 전 시간에 했던 분할 정복법과 비슷해보인다.

     But 작은 문제들의 솔루션이 중복되어 사용된다는 점이 다르다.

 

 

 

이번 시간에 풀어본 예제

 

1149번: RGB거리

처음 생각한 풀이방법 

 

  1 ) 첫 집이 R,G,B인 경우를 따로따로 생각해야한다.

  2 ) 다음 집은 첫 집과 다른 색 중 최소 비용인 색으로 칠한다.

  3 ) 마지막 집까지 칠해지면 비용을 더해 출력한다.

 

  -> 잘못됨 . Greedy 알고리즘의 방식으로 생각했다.

    Solution

        이전 집의 최소비용을 통해 접근하지말고 n번째 집이 R,G,B인 경우를 생각한다.

다시 생각한 풀이방법

 

  1 ) 첫 집이 R,G,B인 경우를 따로따로 생각한다.

  2 ) 다음 집이 R,G,B인 경우로 생각한다.

          R : 이전 집의 G,B 중 최소비용을 선택해서 합산

          G : 이전 집의 R,B 중 최소비용을 선택해서 합산

          B : 이전 집의 R,G 중 최소비용을 선택해서 합산

 

백준 1194 - RGB거리 코드

import java.util.Scanner;

public class Main {

	private static Scanner sc;

	public static void main(String[] args) {
		sc = new Scanner(System.in);
		int N = sc.nextInt();
		sc.nextLine(); // 버퍼 초기화
		int House[][] = new int[N][3]; // 집 별 RGB 비용
		int dp[][] = new int[N][3];  // dp 테이블
		for ( int i = 0 ; i < N ; i ++){
			String line  = sc.nextLine();
			String txt[] = line.split("\\s");
			for( int j = 0 ; j < 3 ; j ++){
				House[i][j] = Integer.parseInt(txt[j]);
			}
		}
		dp[0][0] = House[0][0];
		dp[0][1] = House[0][1];
		dp[0][2] = House[0][2];
		// 1번집 테이블 초기화
		
		for ( int i = 1 ; i < N ; i ++ ){
			dp[i][0] = Min(dp[i-1][1],dp[i-1][2]) + House[i][0];
			dp[i][1] = Min(dp[i-1][0],dp[i-1][2]) + House[i][1];
			dp[i][2] = Min(dp[i-1][0],dp[i-1][1]) + House[i][2];
		} // dp를 통한 테이블 계산
		System.out.println(Min(Min(dp[N-1][0],dp[N-1][1]),dp[N-1][2])); 
						// 0,1,2 3개의 값을 비교해 결과 출력
	}

	private static int Min(int i, int j) {
		return (i < j ? i : j);
	}
	
}

 

 

 

 

 

10844번: 쉬운 계단 수

처음 생각한 풀이방법 

 

  1 ) 10^n자리의 계단 수 경우를 세기위한 기준으로 제일 앞에 위치한 10^n의 자리 수를 선택했다.

  2 ) 0으로 시작할 수 없으므로 N=1일 때 [0] = 0, [1]~[9] = 1 로 초기화

  3 ) n=0 ( 1의 자리 ) 과 n=1 ( 10의 자리 )테이블을 작성했을 때 n=2 a = i 일 때

           table[2][i] = table[1][i-1]+table[1][i+1]과 같았다.

           ! 계단 수이므로 전 단계의 앞 뒤 경우의 수를 참조한다.

           

        < n = k 일 때 계단 수 점화식 >

            i = 0.         :   dp[ k ][ i ] = dp[ k - 1 ][ i ]           

:               ㄴ 0으로 시작하는 계단 수가 아닌 1로 시작될 때 가능한 계단 수를 의미

            0 < i < 9    :   dp[ k ][ i ] = dp[ k - 1 ][ i - 1 ] + dp[ k - 1 ][ i + 1 ] 

            i = 9.         :   dp[ k ][ i ] = dp[ k - 1 ][ i - 1 ] 

                ㄴ 0 ~ 9 이므로 9는 이웃한 숫자가 8밖에 없음

 

  4 ) n=N-1까지 모두 채워지면 N-1번 째의 [0] ~ [9] 까지 더한다.

 

  -> 입력 값이 커지면서 결과 값이 다르게 나옴

      Why?

          % 처리를 마지막에만 하여 오버플로우가 발생함.

      Solution

          dp값을 저장할 때 , 마지막 sum에 가산할 때마다 %를 해주어 오버플로우를 막았음. 

 

 

백준 10844 - 쉬운 계단 수 코드

import java.util.Scanner;

public class Main {

	private static Scanner sc;

	public static void main(String[] args) {
		sc = new Scanner(System.in);
		int N = sc.nextInt();
		sc.nextLine(); // 버퍼 초기화
		long sum = 0;

		long dp[][] = new long[N][10]; // dp 테이블
		
		for (int i = 1; i < 10; i++) {
			dp[0][i] = 1; // N = 1 의 1 ~ 9 인덱스 1로 초기화 
		}
		
		for (int i = 1; i < N; i++) { // dp 테이블 작성
			dp[i][0] = dp[i - 1][1] % 1000000000; // 0은 1번 값 참조
			for (int j = 1; j < 9; j++) { // 나머지는 앞 뒤 참조
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000; 
			}
			dp[i][9] = dp[i - 1][8] % 1000000000; // 9는 8번 값 참조
		}
		for (int i = 0; i < 10; i++) {
			sum += dp[N - 1][i] ; 
			sum = sum % 1000000000;
		}

		System.out.println(sum);

	}
}

 

 

웹 크롤링 

  웹 크롤링 코드를 직접 쳐보며 크롤링한 텍스트 데이터를 원하는 단어가 포함되면 출력하게끔 하였다.

 

크롤링한 텍스트 데이터 중 원하는 단어를 포함한 텍스트를 출력