[알고리즘 정리] - DP, Divide&Conquer, BinarySearch, Dijkstra, Greedy, Kruskal, Prim, Backtracking

[동적 계획법, 분할과 정복]

-> 이진 탐색

-> 최단 경로([다익스트라 알고리즘] -> [벨만-포드 알고리즘] )

-> [탐욕 알고리즘 (Greedy) -> 냅색 알고리즘]

-> 최소신장트리 ([크루스칼 알고리즘] -> [프림 알고리즘])

-> 백트래킹

 

---

[동적 계획법, 분할과 정복]

---

-> 이진 탐색

---

-> 최단 경로([다익스트라 알고리즘] -> [벨만-포드 알고리즘] )

---

-> [탐욕 알고리즘 (Greedy)] -> 냅색 알고리즘

 

package org.algorithms.dp.greedyAndKnapsack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CoinExchange {
    //탐욕 알고리즘(그리디) - 근사치 추정
    //: 최적의 해에 가까운 값을 구하기 위해 사용되며,
    //여러 경우의 수 중 하나를 선택하는 경우, 매순간 최적이라고 생각되는 (현재 시점의 최고의 선택)으로 진행해 최종 결과 반환
    //한계 : 여러 조합의 경우의 수가 존재한다면, 최적이 아닌 경우의 수도 존재

    //동전 교환
    public void coinFunc(Integer price, List<Integer> coinList){
        Integer totalCoinCount=0;
        Integer coinNum=0;

        List<Integer> details =new ArrayList<>();

        for(int i : coinList){
            coinNum=price/i;
            totalCoinCount+=coinNum;
            price-=coinNum*i;
            details.add(coinNum);
            System.out.println(i+"원: "+coinNum+"개");
        }
        System.out.println("총 동전 개수 : "+totalCoinCount);

    }

    public static void main(String[] args) {
        CoinExchange gObject = new CoinExchange();
        List<Integer> coinList = new ArrayList<Integer>(Arrays.asList(500, 100, 50, 1));
        gObject.coinFunc(4720, coinList);
    }
}

 

package org.algorithms.dp.greedyAndKnapsack;

import java.util.Arrays;
import java.util.Comparator;

public class FractionalKnapsack {
    //부분 배낭 알고리즘
    //:무게 제한이 k인 배낭에 최대 가치를 가지는 물건을 넣는 문제
    //각 물건은 무게 w와 가치 v로 표현한다.
    //물건을 쪼개서 일부분을 배낭에 넣을 수도 있다.
    //: 무게 대비 가치가 높은 물건을 넣는다. ->  가치/무게의 비율이 높은 물건순
    //현재 시점에 가장 가치가 높은 물건 선택
    public void fknapsack(Integer[][] objectList, double capacity){
        double totalValue = 0.0;
        double fraction = 0.0;

        //가치/무게 순으로 정렬하기 위해 재정의
        Arrays.sort(objectList, new Comparator<Integer[]>() {
            @Override
            public int compare(Integer[] o1, Integer[] o2) {
                return o2[1]/o2[0]-o1[1]/o1[0];
            }
        });

        for(Integer[] arr:objectList){
            if(capacity-(double) arr[0]>0){
                capacity-=(double) arr[0];
                totalValue+=(double) arr[1];
                System.out.println("무게: "+arr[0]+" , 가치: "+ arr[1]);
            }else{
               fraction=capacity/(double) arr[0];
               totalValue+=(double) arr[1]*fraction;
                System.out.println("무게: "+arr[0]+" , 가치: "+arr[1]+" ,  비율: "+fraction);
                //나머지 비율까지 모두 채웠으므로 중단
                break;
            }
        }
        System.out.println("총 담을 수 있는 가치: "+totalValue);

    }

    public static void main(String[] args) {
        FractionalKnapsack fractionalKnapsack=new FractionalKnapsack();
        Integer[][] objectList = {{10,10}, {15,12},{20,10},{25,8},{30,5}};
        fractionalKnapsack.fknapsack(objectList,30.0);

    }
}

---

-> 최소신장트리 ([크루스칼 알고리즘] -> [프림 알고리즘])

---

-> 백트래킹