인프런 JAVA 알고리즘 정리(DFS, BFS 활용 1~7번)

1. 합이 같은 부분집합(DFS : 아마존 인터뷰)

// 배열 {1, 3, 5, 6, 7, 10}이 입력되된다면 2 집합으로 나누었을 때 같은 합이 있냐?

// { 1, 3, 5, 7 } == { 6, 10 }이 나올 수 있으므로 같은 합이 있다 -> YES 출력

// DFS를 알고리즘을 사용해서 각각의 숫자를 사용할때와 안할때를 비교해서 최종 합이 같은지 비교

 

public String DFS(int L, int[] arr){
    if(L == n){
        int sum=0;
        for(int x : result) sum+=x;
        int total_t = total-sum;
        System.out.println(sum);
        // *현재까지 사용한 값과 사용하지 않은 값의 합이 같으면 YES 리턴*
        if(sum==total_t) answer = "YES";

    }else {
        if(answer.equals("YES")) return answer; //YES가 나오면 이제 재귀 그만
        result[L] = arr[L]; // 값을 사용한다.
        DFS(L + 1, arr);
        result[L] = 0;  // 값을 사용하지 않는다.
        DFS(L + 1, arr);
    }
    return answer;
}

 

 

 

 

2. 바둑이 승차(DFS)

259 5
81
58
42
33
61
// 259의 최대값이 있고 5개의 숫자의 합중 259에 가장 근접한 숫자를 출력

 

public void DFS(int L,int sum){
    if(L==n){
        if(sum<=max && sum>result) {
            result = sum;
        }
    }else{
        if(sum>max) return ;
        DFS(L+1, sum+arr[L]);
        DFS(L+1, sum);
    }

}

 

 

 

3. 최대점수 구하기

20초 안에 최대 점수를 5초, 12초, 3초의 문제를 풀면 총 41점으로 가장 높은 점수를 획득 할 수 있다.

public class Main {
    static ArrayList<Problem> arrayList;
    static int n;
    static int max = 259;
    static int result = 0;
    public void DFS(int L,int sum, int time){
        if(time>max) return ;
        if(L==n){
            if(sum>result) {
                result = sum;
            }
        }else{
            DFS(L+1, sum+arrayList.get(L).score, time+arrayList.get(L).time);
            DFS(L+1, sum, time);
        }

    }
    public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        arrayList = new ArrayList<>();

        n=kb.nextInt();
        max=kb.nextInt();

        for(int i=0; i<n; i++){
            int a = kb.nextInt();
            int b = kb.nextInt();
            arrayList.add(new Problem(a,b));
        }
        T.DFS(0,0, 0);
        System.out.println(result);
    }

    static class Problem{
        int score;
        int time;
        public Problem(int score, int time){
            this.score = score;
            this.time = time;
        }
    }
}

// Problem 이라는 클래스를 만들어서 시간이랑 점수 묶기

// ArrayList에 넣어서 재귀함수 투입

 

 

 

4. 중복 순열

//  여러가닥으로 재귀 함수가 뻗어 나간다.

 

 

 

5. 동전 교환

// 1원 2원 5원의 거스름돈이 있다면 15원을 받았을 때 최소 동전 개수를 구해라.

// 큰거 부터 while 반복을 돌면 될 것 같았지만 

// ex ) 5 5 5 

// ex ) 18 -> 5 5 5 2 1 

// 중간에 돈을 건너 뛰어야지만 최소 값이 나오는 경우가 존재

// ex )  1 8 20 25 50 - 129원을 받으면 50 50 20 8 1 로 5개를 나눠줘야 되며 25원을 건너 뛰어야 최소 값이 나온다.

-> 이 문제도 for 재귀 호출을 하여 높은 동전부터 사용한다 안한다로 나누어서 재귀함수 처리

 

 

 

6. 순열 구하기 // 중복 순열과 다르게 중복되는걸 빼고 출력 

 

 

 

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

// 메모이제이션 =  2차원 배열을 설정하여 n과 r을 담아라, 2차원 배열의 값이 0이 아니면 메모이이션 발동

 

static int[][] arr = new int[50][50]; // 적정한 값 설정
public int DFS(int n , int r){
    if(arr[n][r]!=0) return arr[n][r];
    int result=0;
    // nCr의 규칙 적용
    if(r==1 || n-r==1){
        return n;
    }else{
        result = DFS(n-1, r-1) + DFS(n-1, r);
    }
    arr[n][r] = result;
    return result;
}
public static void main(String[] args){
    Main T = new Main();
    Scanner kb = new Scanner(System.in);

    int n=kb.nextInt();
    int r=kb.nextInt();

    System.out.println(T.DFS(n, r));
}