codejcd 기술 블로그

문제

https://www.acmicpc.net/problem/1012

분석/설계

맵을 탐색하는 DFS/BFS 유형의 문제이고 보통 2차원 배열 형태의 맵을 주고 조건을 달리하면서

탐색하는 형태 유형으로 많이 출제되는 것 같습니다.

구현 코드

package backjoon;

import java.util.Scanner;

public class Main {
	static int T; // 테스트 케이스 횟수
	static int M; // 배추 심어진 가로 길이
	static int N; // 배추 심어진 세로 개수
	static int K; // 배추가 심어진 위치의 개수
	static int[][] map; // 배추밭
	static boolean[][] visited; //
	static int cnt; // 필요한 지렁이 
	static int[] dx = {0, -1, 0, 1}; // 상하좌우 탐색을 위한 값들
	static int[] dy = {1, 0, -1, 0};
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt(); // 테스트 케이스 개수
		
		for(int i=0; i<T; i++) {	// 입력 초기화
			cnt = 0;
			M = scanner.nextInt();
			N = scanner.nextInt();
			K = scanner.nextInt();
			
			map = new int[M][N];
			visited = new boolean[M][N];
			
			for(int j=0; j<K; j++) {
				int x = scanner.nextInt();
				int y = scanner.nextInt();	
				map[x][y] = 1;
			}
			
			for(int v=0; v<M; v++) {
				for(int w=0; w<N; w++) {
					if (map[v][w] == 1 && !visited[v][w]) {
						dfs(v, w);
						cnt++;
					}
				}
			}
			System.out.println(cnt);

		}
		scanner.close();
	}
	
	public static void dfs(int x, int y) {
		visited[x][y] = true;
		
		for(int i=0; i<4; i++) {
			int mx = x + dx[i];
			int my = y + dy[i];
			
			if (mx >= 0 && my >= 0 && mx < M && my < N) { // 0 보다 크고 맵 크기보다는 작아야한다.
				if(!visited[mx][my] && map[mx][my] == 1) { // 방문 여부와 배추가 심어진 곳을 체크
					dfs(mx, my);
				}
			}
		}
	}
}

정리

입력받는 변수가 여러 개이므로 놓치지 않고 어떤 변수에 저장할지 정리하여

DFS 구현에 필요한 변수와 함께 정의합니다.

그 외에 상하좌우 탐색을 위한 값들도 정의해주고 이를 DFS 구현 시 적용하는 게 핵심입니다.

구현이 끝나면  간단하지만 어떻게 상하좌우를 탐색하고 카운트할지 고민하고 구현에 들어가야 합니다.

참고

https://www.acmicpc.net/problem/1012

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

public class TestDemo {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();

        int[] arr = new int[N+1];
        int[] dp = new int[N+1];
        
        for (int i=0; i<N; i++) {
        	arr[i] = scanner.nextInt();
        }
        
        // 10, 20, 10, 30, 20, 50 
        // 10, 20, 10, 25, 20, 43
        
        dp[0] = 1;
        for (int i=1; i<N; i++) {
        	dp[i] = 1;
        	for (int j=0; j<i; j++) {
        		if(arr[i] > arr[j] && dp[j]+1 > dp[i]) {
        			dp[i] = dp[j] + 1;
        		}
        	}
        }
        Arrays.sort(dp);
        System.out.println(dp[N]);

       // OptionalInt ans = Arrays.stream(dp).max();
       // System.out.println(ans.getAsInt());
        
        scanner.close();
    }
}

문제

https://www.acmicpc.net/problem/2579

분석/설계

다이나믹 프로그래밍으로 풀어봤습니다.

점화식을 아래와 같이 만들어봤습니다. 

dp[n] = Math.max(dp[n-3] + arr[n-1], dp[n-2]) + arr[n]

dp[1], dp[2], dp[3] 같은 예외 사항들은 직접 식을 정의해주고 처리했습니다.

구현 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();

        int[] arr = new int[301];
        int[] dp = new int[301];
        for (int i = 1; i <= N; i++) {
        	arr[i] = scanner.nextInt();
        }
        	
        dp[1] = arr[1];
        dp[2] = arr[1] + arr[2];
        dp[3] = Math.max(arr[1], arr[2]) + arr[3];

        for (int n = 4; n <= N; n++) {
            dp[n] = Math.max(dp[n - 3] + arr[n - 1], dp[n - 2]) + arr[n];
        }

        System.out.println(dp[N]);
        scanner.close();
    }
}

정리

바텀업이 익숙해서인지 탑다운으로는 풀이를 잘 안하게됩니다.

탑다운으로 푸는 방식들이 많이 있으니 혹시 안풀릴 경우 검색해보시거나 아래 링크를 참고하면 도움이됩니다.

다이나믹은 바텀업의 경우 예시를 들어놓고 점화식으로 정리할경우 매우 빠르게 풀수있습니다.

익숙해지려면 많이 문제 유형을 만나보고 점화식을 정의할수 있게 고민해야 봐야할 것 같습니다.

참고

https://www.acmicpc.net/problem/2579

https://st-lab.tistory.com/132

문제

https://www.acmicpc.net/problem/1149

분석/설계

입력 숫자의 범위가 2~1000 이므로 다이나믹 프로그래밍으로 풀어봤습니다.

점화식을 아래와 같이 만들어봤습니다. 

dp[N][0] = min( dp[N-1][1], dp[N-1][2] ) + dp[N][0]

dp[N][1] = min( dp[N-1][0], dp[N-1][2] ) + dp[N][1]

dp[N][2] = min( dp[N-1][0], dp[N-1][1] ) + dp[N][2]

구현 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int arr[][] = new int[N+1][3];
        int dp[][] = new int[N+1][3];

        for (int i=1; i<=N; i++) {
            for (int j=0; j<3; j++) {
                arr[i][j] = scanner.nextInt(); 
            }
        }

        for (int i=1; i<=N; i++) {
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + arr[i][0];
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + arr[i][1];
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + arr[i][2];
        }

        System.out.println(Math.min(Math.min(dp[N][0], dp[N][1]), dp[N][2]));
        scanner.close();
    }
}

정리

다이나믹 프로그램은 탑다운과 바텀업 방식이 있습니다.

이 문제는 점화식을 만들고 바텀업 방식으로 풀었고, 문제만 보고 점화식이 잘 정의가 안되면

예시를 여러 개 만들고 패턴을 찾아내어 점화식을 만들고 알고리즘을 적용하여 코드를 작성하면 

수월합니다.

참고

https://www.acmicpc.net/problem/1149

문제

https://www.acmicpc.net/problem/9095

분석/설계

입력 숫자의 범위가 1~11이지만 다이나믹 프로그래밍으로 풀어봤습니다.

점화식을 아래와 같이 만들어봤습니다. 

N이 1, 2, 3 의 경우 점화식 적용할 경우 index가 음수 값이거나 0이기 때문에

따로 정의 해줬습니다.

dp[i] = d[i-1] + d[i-2] + d[i-3]

구현 코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int T = scanner.nextInt();
		int N[] = new int[T];
		int dp[] = new int[11];
		
		for(int i=0; i<T; i++) {
			N[i] = scanner.nextInt();
		}
		
		dp[0] = 1;
		dp[1] = 1;
		dp[2] = 2;
		
		for(int i=0; i<N.length; i++) {
			for(int j=3; j<N[i]+1; j++) {
				dp[j] = dp[j-1] + dp[j-2] + dp[j-3];
			}	
		}
		
		for(int i=0; i<N.length; i++) {
			System.out.println(dp[N[i]]);
		}

		scanner.close();
	}
}

정리

다이나믹 프로그램은 탑다운과 바텀업 방식이 있습니다.

이 문제는 점화식을 만들고 바텀업 방식으로 풀었고, 문제만 보고 점화식이 잘 정의가 안되면

예시를 여러 개 만들고 패턴을 찾아내어 점화식을 만들고 알고리즘을 적용하여 코드를 작성하면 

수월합니다.

참고

https://www.acmicpc.net/problem/9095

문제

https://www.acmicpc.net/problem/2839

분석/설계

입력 숫자의 범위가 3~5000 이기때문에 다이나믹 프로그래밍으로 풀지 않고

그리디 알고리즘으로 푸는 방법도 있을 것 같습니다.

하지만 다이나믹을 프로그래밍 사용하여 풀어봤습니다.

점화식을 아래와 같이 만들어봤습니다. 

4, 7 같은 경우 3이나 5로 정확히 나눠서 떨어지지 않기때문에 문제의 조건대로 -1을 출력해야 하므로

이에 대한 예외 처리를 주의해야합니다.

dp[i] = min(d[i-3], d[i-5]) + 1 

구현 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int dp[] = new int[N+1];

        dp[3] = 1;
        if(N == 4) {
            System.out.println(-1); 
            return;
        }
        if(N>4) dp[5] = 1;	

        for(int i=6; i<dp.length; i++) {
            if (i % 5 == 0) {
                dp[i] = dp[i-5] + 1;
            } else if (i % 3 == 0) {
                dp[i] = dp[i-3] + 1;
            } else {
                if (dp[i-3] != 0 && dp[i-5] != 0) {
                    dp[i] = Math.min(dp[i-3], dp[i-5]) + 1;
                } else {
                    dp[i] = -1;
                }
            }
        }

       System.out.println(dp[N]);
       sc.close();
    }
}

정리

다이나믹 프로그램은 탑다운과 바텀업 방식이 있습니다.

이 문제는 점화식을 만들고 바텀업 방식으로 풀었고

편한 풀이 방식을 적용하면 될 것 같습니다.

참고

https://www.acmicpc.net/problem/2839