241227 TIL (DFS를 이용한 중복 순열, 순열, 조합구하기)

 

 

코드카타

• 프로그래머스 삼총사

https://school.programmers.co.kr/learn/courses/30/lessons/131705

프로그래머스

 

• 해당 문제는 조합을 구하는 문제로 이 기회에 DFS를 이용해 중복 순열, 순열 조합을 구하는 방법을 정리해두려고 한다

 

• 중복 순열
  • 3개의 원소 중에 2개를 뽑아 중복 순열을 만든다면 
  • 1,2,3 을 뽑아 만들 수 있는 값은 (1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3)  총 9가지이다.
  • arr[n] : 전체 원소가 담긴 배열
  • ans[m] : 정답이 담길 배열

void dfs(int l){
	if(l==m){
    	//정답을 구하는 배열에 꽉 차면 출력
    }
    else{
    	for(int i=0;i<n;i++){
        	ans[l] = arr[i];
            dfs(l+1);
        }
    }
}

 

 

• 순열
  • 3개의 원소 중에 2개를 뽑아 중복 순열을 만든다면 
  • 1,2,3 을 뽑아 만들 수 있는 값은 (1,2) (1,3) (2,1)  (2,3) (3,1) (3,2)  총 6가지이다.
  • arr[n] : 전체 원소가 담긴 배열
  • ans[m] : 정답이 담길 배열
  • visited[n] : 방문 여부를 확인하는 배열순열

void dfs(int l){
	if(l==m){
    	//정답을 구하는 배열에 꽉 차면 출력
    }
    else{
    	for(int i=0;i<n;i++){
        	ans[l] = arr[i];
            dfs(l+1);
        }
    }
}

 

• 순열과 중복 순열의 차이는 visited 배열의 사용 여부

• 조합
  • 3개의 원소 중에 2개를 뽑아 조합을 만든다면 
  • 1,2,3 을 뽑아 만들 수 있는 값은 (1,2) (1,3) (2,3) 총 3가지이다.
  • arr[n] : 전체 원소가 담긴 배열
  • ans[m] : 정답이 담길 배열
  • visited[n] : 방문 여부를 확인하는 배열순열조합

void dfs(int L,int start){
        if(L==m){
            //출력
        }
        else{
            for(int i=start;i<=n;i++){
                aws[L] = arr[i];
                dfs(L+1,i+1);
            }
       }
}

 

 

백준 알고리즘 문제

 

• 백준 12865번 평범한 배낭
  • 시간 제한 : 2초
  • 입력 : 첫째 줄에 물품의 수 N (1~100), 준서가 버틸 수 있는 무게 K (1~100000)                                                                  둘째 줄부터 N개의 줄에 물건의 무게 W (1~100000), 물건의 가치 (0~1000)
  • 배낭에 넣을 수 있는 물건들의 가치합의 최댓값 출력
  • 정말 유명한 배낭 문제라고 하는데 처음 풀어보는데 정말 어려웠다
  • dp[i][j] = Math.max(dp[i-1][j] , arr[i][1] + dp[i-1][j-arr[i][0]]) 이 매우 핵심 문장으로
  • 남은 무게가 0보다 크거나 같으면 이전 값과 현재 가치 값 + 남은 무게의 가치 값을 비교

for(int i = 1 ; i <= N ; i++) {
			for(int j = 1 ; j <= weight ; j++) {
				if(j - arr[i][0] >= 0)
					dp[i][j] = Math.max( dp[i-1][j], arr[i][1]+dp[i-1][j-arr[i][0]]);
				else 
					dp[i][j] = dp[i-1][j];
			}
		}

 

 

 

 

• 백준 1003번 피보나치 함수
  • 시간 제한 : 0.25초
  • 입력 : 첫째 줄에 테스트 케이스의 수 T , 각 테스트 N (0~40)
  • 출력 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분하여 출력

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

• 해당 함수를 활용하여 풀면 dp로 dp[n] = dp[n-1] + dp[n-2] 로 풀면서 0과 1이 나오는 값을 더해가면 될거 같다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(bf.readLine());
        int [][] dp = new int[41][2];
        dp[0][0] = dp[1][1] = 1;
        dp[0][1] = dp[1][0] = 0;     
        for(int i=2;i<41;i++) {
        	dp[i][0] = dp[i-1][0] + dp[i-2][0];
        	dp[i][1] = dp[i-1][1] + dp[i-2][1];
        }
        for(int i=0;i<t;i++) {
        	int n = Integer.parseInt(bf.readLine());
        	System.out.println(dp[n][0]+" "+dp[n][1]);
        }
    }
}

 

 

• 11053번 가장 긴 증가하는 부분 수열
  • 전형적인 LIS (Longest Increasing Subsequence) 문제다.
  • 입력 : 수열의 크기 N (1~1000), 수열을 이루고 있는 수 Ai (1~1000)
  • 출력 : 수열 A의 가장 긴 증가하는 부분의 수열의 길이를 출력
  • LIS 문제를 푸는 방식은 dp 값에 미리 1을 넣어두고 이전 값들 중 작은 값이 있다면 해당 dp 값에 +1 을 하여 타켓 dp의 값과 비교하여 큰 값을 넣는 방식으로 진행하면 된다!

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int [] arr = new int[n];
        int [] dp = new int[n];
        StringTokenizer st = new StringTokenizer(bf.readLine());
        for(int i=0;i<n;i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        	dp[i] = 1;
        }
        int max = dp[0];
        for(int i=1;i<n;i++) {
        	for(int j=0;j<i;j++) {
        		if(arr[i] > arr[j]) {
        			dp[i] = Math.max(dp[i], dp[j]+1);
        		}
        	}
        	max = Math.max(max, dp[i]);
        }
       System.out.println(max);
    }
}