DFS, BFS 활용 섹션 - (2)

DFS, BFS 활용 섹션 - (2)

8-5. 동전교환 | DFS

• DFS(L, sum) : 0개부터 시작해서 L개의 동전을 사용했을 때 sum이 문제의 m과 같아지는 경우, 더 작은 min(answer, L); 로 변경하면 된다.
• 동전의 종류는 arr[i]로 받을 건데, 각각의 DFS() 호출은 for문으로 arr[] 내부를 돌면서 각각의 L개 동전을 arr[i]의 동전 종류 사용한 후 sum 값을 보면서 뻗어나가면 된다.

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

/* 8-5. 동전교환 
다음과 같이 여러 단위의 동전들이 주어져 있을때 
거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?
각 단위의 동전은 무한정 쓸 수 있다.
*/
public class Main1 {
    static int n, m, answer = Integer.MAX_VALUE;
    //DFS
    public void DFS(int L, int sum, Integer[]arr) {
        if(sum > m) return;
        if(sum == m) {
            answer = Math.min(answer, L);
        }else {
            for(int i=0; i<n; i++) {
                DFS(L+1, sum+arr[i], arr); //재귀 호출 
            }
        }
    }
    //실행 메인
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        //Arrays.sort 사용할 대상은 Integer 객체로 생성한다.
        Integer [] arr =new Integer[n];
        for(int i=0; i<n; i++) arr[i] = kb.nextInt();
        //내림차순 정렬 (큰 수부터 해야 더 효율적)
        Arrays.sort(arr, Collections.reverseOrder());

        m = kb.nextInt();

        T.DFS(0, 0, arr);

        System.out.println(answer);
    }
}

---

8-6. 순열 구하기 | DFS

• 이 문제는 전체 n개 중에 m개를 (중복없이) 뽑아야 한다.
• 중복이 없어야 하므로 뽑는 값에 대한 체크용 배열 ch[]가 필요하며
• 각각 m개씩 뽑은 값을 띄울 pm[] 도 필요하다.
• DFS(L) => pm[L]의 L번째 위치에 뽑을 숫자를 for(i~n)까지 하나씩 맞춰가면서 뽑고,
• L이 m이 되면 pm[] 자리에 담을 숫자를 다 뽑은 거다.

import java.util.Scanner;

/* 8-6. 순열 구하기*/
public class Main2 {
    static int n, m;
    static int[] ch, pm, arr; 
    //중복 없게 ch[]로 선택값 방문 체크하고, 
    //뽑은 값은 pm[]에 담는다.

    //DFS 
    public void DFS(int L) {
        if(L == m) {
            for(int i=0; i<m; i++) System.out.print(pm[i]+ " ");
            System.out.println();
        }else {
            for(int i=0; i<n; i++) {
                //중복 없이 뽑아야 하므로 방문 전인 i 에 대하여 
                if(ch[i] == 0) {
                    pm[L] = arr[i];//뽑은 수 pm의 L번째 칸에 담고 
                    ch[i] = 1;//i번쨰 수 뽑았음 방문 체크
                    DFS(L+1); // 재귀 호출
                    //복귀주소
                    ch[i]=0;//다음 가지로도 가야하니 이번 가지에ㅔ서 Back
                }
            }
        }
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main2 T = new Main2();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();
        arr=new int[n];

        for(int i=0; i<n; i++) arr[i] = kb.nextInt();
        ch = new int[n];
        pm = new int[m]; //각각 m개의 숫자 뽑으니까

        T.DFS(0);
    }
}

---

8-7. 조합의 경우의 수 (메모이제이션)

⬛ 메모이제이션 (Memoization) 이란?

• 동일한 계싼을 반복해야 할 때 이전에 계산했던 값들을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 할 수 있는 방법이다.
• 동적 계획법의 핵심이 되술

---

import java.util.Scanner;
/* 8-7. 조합의 경우수 (메모이제이션) */
public class Main3 {
    //메모이제이션 사용 
    int[][]dy = new int[35][35];
    //DFS
    public int DFS(int n, int r) {
        if(dy[n][r] > 0) return dy[n][r];
        if(n==r || r==0) return 1;
        else {
            return dy[n][r] = DFS(n-1, r-1) + DFS(n-1, r);
        }
    }
    //실행 메인  
    public static void main(String[] args) {
        // TODO Auto-generated method stub
         Main3 T = new Main3();
         Scanner kb =new Scanner(System.in);
         int n = kb.nextInt();
         int r = kb.nextInt();
         System.out.println(T.DFS(n, r));
    }
}

---