[코드트리 조별과제] 3주차 - DP / 백트래킹 학습

3주차에는 INTERMEDIATE LOW 부분 중 백트래킹과 DP I에 대해 학습했다.

---

DP I - 배낭 채우기

유형	문제 경험치	난이도
Intermediate Low / DP I / 아이템을 적절히 고르는 문제	90xp

[문제링크]에서 문제를 참고하자.

배낭 문제는 백준에서 한두번 풀어본 이후에 접해본 적 없는데, 오랜만에 다시 접하니 머릿속이 백지가 되서 생각을 많이 했던 문제이다.

내가 푼 배낭 문제 풀이 방식은 무게와 가치를 가진 2차원 DP배열을 만들어서 해결할 수 있었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	//dp - 배낭문제
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int[][] dp = new int[n+1][m+1];
		int[][] item = new int[n+1][2];
		
		for(int i=1; i<=n; i++) {
			st = new StringTokenizer(br.readLine());
			item[i][0]=Integer.parseInt(st.nextToken());
			item[i][1]=Integer.parseInt(st.nextToken());
		}
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=m; j++) {
				if(item[i][0] > j) {
					dp[i][j]=dp[i-1][j];
				}
				else {
					dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-item[i][0]]+item[i][1]);
				}
			}
		}
		System.out.println(dp[n][m]);
	}
}

---

DP I - 부분 수열의 합

유형	문제 경험치	난이도
Intermediate Low / DP I / 아이템을 적절히 고르는 문제	60xp

[문제링크]에서 문제를 참고하자.

DP I에서 아이템을 적절히 고르는 문제 부분에 해당하는 문제들이 주로 for문을 많이 사용하는데, 각각의 문제를 접할 때마다 어떤 for문 방식을 써야할 지 생각하는 것이 특징인 것 같다.

위 문제에서는 2중 for문 방식에서 합이 m이 되는 경우를 찾기 위해 for문을 역순으로 줄여가면서 해결했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	//dp문제
	static int n;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int[] arr = new int[n+1];
		int[] dp = new int[m+1];
		
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=n; i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		dp[0]=1;
		for(int i=1; i<=n; i++) {
			for(int j=m; j>=0; j--) {
				if(dp[j]==1 && arr[i]+j<=m) {
					dp[j+arr[i]]=1;
				}
			}
		}
        if(dp[m]==0){
            System.out.println("No");
        }
        else if(dp[m]==1){
            System.out.println("Yes");
        }
	}
}

---

DP I - 최대 점프 횟수

유형	문제 경험치	난이도
Intermediate Low / DP I / 조건에 맞게 선택적으로 전진하는 DP	60xp

[문제링크]에서 문제를 참고하자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	//dp문제
	static int n; //배열 크기
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		
		int[] arr = new int[n+1];
		int[] dp = new int[n+1];
		
		st = new StringTokenizer(br.readLine());
		
		for(int i=1; i<=n; i++) { //값 입력
			arr[i]=Integer.parseInt(st.nextToken());
			dp[i]=Integer.MIN_VALUE;
		}
        
		dp[1]=0;
		
		for(int i=2; i<=n; i++) {
			for(int j=1; j<i; j++) {
				if(dp[j]==Integer.MIN_VALUE) {
					continue;
				}
				
				if(j+arr[j]>=i) {//만약 j 인덱스에서 j칸을 이동할 수 있다면
					dp[i]=Math.max(dp[i], dp[j]+1);
				}
			}
		}
		
		Arrays.sort(dp); //오름차순 정렬
		System.out.println(dp[n]);
	}
}

최대인 경우엔 dp 배열을 최솟값으로 초기화해주고, 최소인 경우엔 dp 배열을 최댓값으로 초기화해준다는 점을 기억하면 좋을 거 같다.

---

백트래킹 - 아름다운 수

유형	문제 경험치	난이도
Intermediate Low / Backtracking / K개 중 하나를 N번 선택하기(Simple)	60xp

[문제링크]에서 문제를 참고하자.

재귀함수와 2중 for문을 사용했는데, 사실 처음엔 고민을 조금 많이 했다. 너무 어렵게까지 생각했던 문제인 것 같기도 하다.

for(int j=0; j<i; j++) { //해당 숫자만큼 같은 수 연달아나오게 하기
	temp+=Integer.toString(i);
}

위 부분을 통해 해당 숫자만큼 같은 수가 연달아 나오게 하는 방식이 핵심인 거 같다.

이런 간단하다면 간단하면서도 창의적인 생각을 통해 사고 능력을 키우는 것이 아마 알고리즘 공부에서 얻어갈 수 있는 능력 중 하나이지 않을까 싶다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	//백트래킹 문제
	static int n;
	static int ans=0;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		
		repeat("",0);
        
		System.out.println(ans);

	}

	public static void repeat(String str, int length) {
		if(length==n) {
			ans++;
			return;
		}
		
		String temp="";
		for(int i=1; i<=4; i++) {
			if(length+i<=n) {
				for(int j=0; j<i; j++) { //해당 숫자만큼 같은 수 연달아나오게 하기
					temp+=Integer.toString(i);
				}
				repeat(str+temp,length+i);
			}
		}
	}
}

---