BLOG :||

import java.util.*;
public class main {
    public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(Arrays.toString(s.Chap09DijkstraGuide(6, 11, 1
            , new int[][]{{1,2,2}
                         ,{1,3,5}
                         ,{1,4,1}
                         ,{2,3,3}
                         ,{2,4,2}
                         ,{3,2,3}
                         ,{3,6,5}
                         ,{4,3,3}
                         ,{4,5,1}
                         ,{5,3,1}
                         ,{5,6,2}})));
    System.out.println(Arrays.deepToString(s.Chap09FloydWarshallGuide(4,7, new int[][]{{1,2,4}
                                                                                             ,{1,4,6}
                                                                                             , {2,1,3},{2,3,7},{3,1,5},{3,4,4},{4,3,2}})));
    }
}
class Solution {

    public int[] Chap09DijkstraGuide(int n, int m, int start, int[][] costs) {
        int[] answer = new int[n];
        Arrays.fill(answer, Integer.MAX_VALUE);

        boolean[] visited = new boolean[n];

        List<Edge>[] list = new ArrayList[m];//꼭 기억해두자.
        for(int i = 0; i<n;++i)
            list[i] = new ArrayList<>();

        for(int i = 0; i<m;++i) {
            list[costs[i][0]-1].add(new Edge(costs[i][1]-1, costs[i][2]));
        }

        Queue<Edge> queue = new PriorityQueue<Edge>();
        queue.add(new Edge(start-1, 0));

        while(!queue.isEmpty()) {
            Edge q = queue.poll();

            if(answer[q.node] > q.cost) {
                answer[q.node] = q.cost;
                visited[q.node] = true;
            }
            for(Edge edge : list[q.node]) {
                if(!visited[edge.node]) {
                    if(answer[edge.node] > edge.cost + q.cost) {
                        queue.add(new Edge(edge.node, edge.cost+q.cost));
                    }
                }
            }
        }
        return answer;
    }
    public int[][] Chap09FloydWarshallGuide(int n, int m,int[][] costs) {
        int[][] answer = new int[n][n];
        for(int[] a : answer)
            Arrays.fill(a, Integer.MAX_VALUE); //값 초기화

        for(int i = 0; i<n;++i)
            answer[i][i] = 0;//자기 자신으로는 0

        for(int i = 0; i<m;++i) {
            answer[costs[i][0]-1][costs[i][1]-1] = costs[i][2]; //기본 costs 추가
        }
        for(int i  = 0; i<n;++i) {
            for(int j = 0; j<n;++j) {
                for(int k = 0; k<n;++k) {
                    int tmpMin = answer[j][i] + answer[i][k];// 이 부분은 까먹지 말자
                    if(tmpMin < 0)
                        tmpMin = Integer.MAX_VALUE; //MAX_VALUE 이상의 값이 되면 음수가 되므로 음수인 경우 MAX_VALUE로 초기화
                    answer[j][k] = (answer[j][k] < tmpMin) ? answer[j][k] : tmpMin;
                }
            }
        }

        return answer;
    }
}
class Edge implements Comparable<Edge> {
    int node;
    int cost;

    public Edge(int node, int cost) {
        this.node = node;
        this.cost = cost;
    }
    public int compareTo(Edge n) {
        if(cost < n.cost) {
            return -1;
        }
        else if(cost > n.cost) {
            return 1;
        }
        else if(node < n.node) {
            return -1;
        }
        else if(node > n.node) {
            return 1;
        }
        else
            return 0;
    }
}

다익스트라 알고리즘은 start node에서 각 노드 별로 갈 수 있는 최소 거리를 찾는 과정이다.

플루이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 할 때 사용하는 알고리즘이다.

다익스트라 알고리즘은 Greedy, 플루이드 워셜 알고리즘은 DP

import java.util.*;
public class main {
    public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.Chap09Example01(5,7,new int[][]{{1,2},{1,3}, {1,4}, {2,4}, {3,4},{3,5}, {4,5}},4,5));
    System.out.println(s.Chap09Example01(4,2, new int[][]{{1,3},{2,4}},3,4));
    System.out.println(Arrays.toString(s.Chap09Example02(3,2,1, new int[][]{{1,2,4}, {1,3,2}})));
    }
}
class Solution {
    public int Chap09Example01(int n, int m, int[][] lines, int x, int k) {
        int answer = 0;

        int[][] distance = new int[n][n];
        for(int[] d : distance)
            Arrays.fill(d, Integer.MAX_VALUE);

        for(int i = 0; i<n;++i) {
            distance[i][i] = 0;
        }
        for(int i = 0; i<m;++i) {
            distance[lines[i][0]-1][lines[i][1]-1] = 1;
            distance[lines[i][1]-1][lines[i][0]-1] = 1;
        }
        for(int h = 0; h<n;++h) {
            for(int i = 0; i<n;++i) {
                for(int j = 0; j<n;++j) {
                    int tmpMin = distance[i][h] + distance[h][j];
                    if(tmpMin < 0)
                        tmpMin = Integer.MAX_VALUE;
                    distance[i][j] = (distance[i][j] < tmpMin) ? distance[i][j] : tmpMin;
                }
            }
        }
        if(distance[0][k-1] == Integer.MAX_VALUE)
            return -1;
        if(distance[k-1][x-1] == Integer.MAX_VALUE)
            return -1;
        answer = distance[0][k-1] + distance[k-1][x-1];
        return answer;
    }
    public int[] Chap09Example02(int n, int m, int c, int[][] costs) {
        int[] answer = new int[2];
        int[] distance = new int[n];
        boolean[] visited = new boolean[n];
        Queue<Edge> queue = new PriorityQueue<>();
        List<Edge>[] list = new ArrayList[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        for(int i = 0; i<n;++i)
            list[i] = new ArrayList<>();

        for(int i = 0; i<m;++i) {
            list[costs[i][0]-1].add(new Edge(costs[i][1]-1, costs[i][2]));
        }
        //c->start
        distance[c-1] = 0;

        queue.add(new Edge(c-1,0));

        while(!queue.isEmpty()) {
            Edge q = queue.poll();
            if(distance[q.node] > q.cost) {
                distance[q.node] = q.cost;
                visited[q.node] = true;
            }
            for(Edge edge : list[q.node]) {
                if(!visited[edge.node]) {
                    if(distance[edge.node] > edge.cost + q.cost) {
                        queue.add(new Edge(edge.node, edge.cost+q.cost));
                    }
                }
            }
        }

        for(int i = 0; i<n;++i) {
            if(visited[i]) {
                System.out.println("c");
                answer[0]++;
                answer[1] = (distance[i] > answer[1]) ? distance[i] : answer[1];
            }

        }
        return answer;
    }
}
class Edge implements Comparable<Edge> {
    int node;
    int cost;

    public Edge(int node, int cost) {
        this.node = node;
        this.cost = cost;
    }
    public int compareTo(Edge n) {
        if(cost < n.cost) {
            return -1;
        }
        else if(cost > n.cost) {
            return 1;
        }
        else if(node < n.node) {
            return -1;
        }
        else if(node > n.node) {
            return 1;
        }
        else
            return 0;
    }
}

오랜만에 보니까 엄청 어렵다. 책은 파이썬으로 되어 있어서 자바에 맞춰 이해하려고 고민 좀 했다.

import java.util.*;
public class main {
    public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.Chap08Example01TopDown(26));
    System.out.println(s.Chap08Example01BottomUp(26));
    System.out.println(s.Chap08Example02BottomUp(4, new int[]{1,3,1,5}));
    System.out.println(s.Chap08Example02TopDown(4, new int[]{1,3,1,5}));
    System.out.println(s.Chap08Example03BottomUp(3));
    System.out.println(s.Chap08Example03TopDown(3));
    System.out.println(s.Chap08Example04TopDown(2,15,new int[] {2,3}));
    System.out.println(s.Chap08Example04TopDown(3,4,new int[] {3,5,7}));
    System.out.println(s.Chap08Example04BottomUp_Guide(2,15,new int[] {2,3}));
    System.out.println(s.Chap08Example04BottomUp_Guide(3,4,new int[] {3,5,7}));
    }
}
class Solution {

    public int Chap08Example01TopDown(int n) {
        int[] memory = new int[n+1];

        return Example01TopDown(n, memory);
    }
    public int Chap08Example01BottomUp(int n) {
        int[] memory = new int[n+1];
        for(int i = 2; i<=n;++i) {
            int d5 = 300001;
            if(i % 5 == 0) {
                d5 = memory[i/5]+1;
            }
            int d3 = 300001;
            if(i % 3 == 0) {
                d3 = memory[i/3]+1;
            }
            int d2 = 300001;
            if(i % 2 == 0) {
                d2 = memory[i/2]+1;
            }
            int m1 = memory[i-1]+1;
            int min = (d5 < d3) ? d5 : d3;
            min = (min < d2) ? min : d2;
            min = (min < m1) ? min : m1;
            memory[i] = min;
        }
        return memory[n];
    }
    public int Example01TopDown(int n, int[] memory) {
        if(n == 1) {
            return 0;
        }
        if(memory[n] != 0) {
            return memory[n];
        }
        else {
            int d5 = 300001;
            if( n % 5 == 0) {
                d5 = Example01TopDown(n /5 , memory)+1;
            }
            int d3 = 300001;
            if(n % 3 == 0) {
                d3 = Example01TopDown(n/3, memory)+1;
            }
            int d2 = 300001;
            if(n % 2 == 0) {
                d2 = Example01TopDown(n/2, memory)+1;
            }
            int m1 = Example01TopDown(n-1, memory)+1;

            int min = (d5 < d3) ? d5 : d3;
            min = (min < d2) ? min : d2;
            min = (min < m1) ? min : m1;
            memory[n] = min;
            return memory[n];
        }
    }
    public int Chap08Example02BottomUp(int n, int[] foods) {
        int[] maxFoods = new int[n];

        maxFoods[0] = foods[0];
        maxFoods[1] = (foods[0] > foods[1]) ? foods[0] : foods[1];
        for(int i = 2; i<n;++i) {
            maxFoods[i] = (maxFoods[i-1] > maxFoods[i-2]+foods[i]) ? maxFoods[i-1] : maxFoods[i-2]+foods[i];
        }
        return maxFoods[n-1];
    }
    public int Chap08Example02TopDown(int n, int[] foods) {
        int[] memory = new int[n];
        memory[0] = foods[0];
        memory[1] = (foods[1] > foods[0]) ? foods[1] : foods[0];
        Example02TopDown(n-1, memory, foods);
        return memory[n-1];
    }
    public int Example02TopDown(int n, int[] memory, int[] foods) {
        if(memory[n] != 0) {
            return memory[n];
        }
        int n1 = Example02TopDown(n-1, memory, foods);
        int n2 = Example02TopDown(n-2, memory, foods)+foods[n];
        memory[n] = (n1 > n2) ? n1 : n2;
        return memory[n];
    }
    public int Chap08Example03BottomUp(int n) {
        int[] memory = new int[n+1];
        memory[1] = 1;
        if(n == 1)
            return memory[1];
        memory[2] = 3;
        if(n == 2)
            return memory[2];
        for(int i = 3; i<=n;++i) {
            memory[i] = memory[i-1]+ memory[i-2]*2;
        }
        return memory[n]%796796;
    }
    public int Chap08Example03TopDown(int n) {
        int[] memory = new int[n+1];
        if(n>=1) {
            memory[1] = 1;
        }
        if(n>=2) {
            memory[2] = 3;
        }
        Example03TopDown(n, memory);
        return memory[n];
    }
    public int Example03TopDown(int n, int[] memory) {
        if(memory[n] != 0)
            return memory[n];
        memory[n] = Example03TopDown(n-2, memory) *2 + Example03TopDown(n-1,memory);
        return memory[n];
    }
    public int Chap08Example04TopDown(int n, int m, int[] coins) {
        int[] memory = new int[m+1];
        for(int c : coins) {
            if(c <= m)
                memory[c] = 1;
        }
        Example04TopDown(m,coins,memory);
        if(memory[m] == 10001) {
            return -1;
        }
        return memory[m];
    }
    public int Example04TopDown(int m, int[] coins, int[] memory) {
        if(m == 0)
            return 0;
        if(memory[m] != 0) {
            return memory[m];
        }
        int min = 10001;
        int tmp = 0;
        for(int c : coins) {
            if(m-c >= 0) {
                tmp = Example04TopDown(m-c, coins, memory)+1;
                min = (min < tmp) ? min : tmp;
            }
        }
        memory[m] = min;
        return memory[m];
    }
    public int Chap08Example04BottomUp_Guide(int n, int m, int[] coins) {
        int[] memory = new int[10001];
        Arrays.fill(memory,10001);//기억해두자. for문 반복 돌리지 말고..
        memory[0] = 0;
        for(int i = 0; i < n;++i) {
            for(int j = coins[i]; j<=m;++j) {
                if(memory[j-coins[i]] != 10001) {
                    memory[j] = (memory[j] < memory[j-coins[i]] +1) ?  memory[j] : memory[j-coins[i]] + 1;
                }
            }
        }
        if(memory[m] == 10001)
            return -1;
        return memory[m];
    }
}

---

다른 챕터와 DP는 언제나 사람 머리 아프게 하는 파트다. Top-Down, Bottom-Up이 어려운 것은 아니지만 이 문제가 DP로 풀어야 하는지를 빠르게 인지를 하는 것이 중요하다. 그리고 DP로 풀었다 하더라도 정확한 공식을 찾아야 한다.

Example03 바닥 공사 문제에서 경우의 수가 어떻게 되는지 문제만 보고서는 이해가 안가서 그림을 그려보았는데도 아리까리했다.

평소에는 항상 재귀로 문제를 푸는게 습관처럼 되어있어서 Bottom-Up을 사용하는 연습을 들이고자 Top-Down, Bottom-Up을 같이 써봤다.

Example04는 Bottom-Up으로 될거라고 생각도 안했는데..

징글맞게 어렵다 진짜..

import java.util.*;
public class main {
    public static void main(String[] args) {

        Solution s = new Solution();

        boolean[] a = s.Chap07Example01(5, new int[]{8,3,7,9,2}, 3, new int[]{5,7,9});//이진탐색
        for(boolean aa : a)
            System.out.print(aa + " ");
        System.out.println();
        boolean[] b = s.Chap07Example01_Guide01(5, new int[]{8,3,7,9,2}, 3, new int[]{5,7,9});//계수정렬
        for(boolean aa : b)
            System.out.print(aa + " ");
        System.out.println();
        boolean[] c = s.Chap07Example01_Guide02(5, new int[]{8,3,7,9,2}, 3, new int[]{5,7,9});//집합자료형
        for(boolean aa : c)
            System.out.print(aa + " ");
        System.out.println();
        System.out.println(s.Chap07Exmaple02(4,6,new int[]{19,15,10,17}));
    }
}
class Solution {


    public boolean[] Chap07Example01(int n, int[] stock, int m, int[] find) {
        boolean[] answer = new boolean[m];

        Arrays.sort(stock);

        for(int i = 0; i<m;++i) {
            int start = 0;
            int mid = stock.length/2;
            int end = stock.length-1;
            while(start <= end) {
                if(stock[mid] < find[i]) {
                    start = mid+1;
                    mid = (end+start)/2;
                }
                else if(stock[mid] > find[i]) {
                    end = mid-1;
                    mid = (end+start)/2;
                }
                else {
                    answer[i] = true;
                    break;
                }
            }
        }
        return answer;
    }
    public boolean[] Chap07Example01_Guide01(int n, int[] stock, int m, int[] find) {
        boolean[] answer= new boolean[m];

        int[] stocks = new int[1000001];
        for(int s : stock)
            stocks[s] = 1;
        for(int i = 0; i<m;++i) {
            if(stocks[find[i]] == 1)
                answer[i] = true;
        }

        return answer;
    }
    public boolean[] Chap07Example01_Guide02(int n, int[] stock, int m, int[] find) {
        boolean[] answer= new boolean[m];
        Set<Integer> set = new HashSet<>();
        for(int s: stock)
            set.add(s);
        for(int i = 0; i<m;++i) {
            if(set.contains(find[i]))
                answer[i] = true;
        }
        return answer;
    }
    public int Chap07Exmaple02(int n, int m, int[] ddeok) {
        int answer = 0;

        Arrays.sort(ddeok);
        int start = 0;
        int end = ddeok[ddeok.length - 1];
        int mid = (start + end) / 2;
        while(true) {
            int tmp = 0;
            for(int d: ddeok) {
                if(d > mid) {
                    tmp += d-mid;
                }
            }
            if(tmp == m) {
                answer = mid;
                break;
            }
            else if(tmp < m) {
                end = mid-1;
                mid = (start+end)/2;
            }
            else if(tmp > m) {
                start = mid+1;
                mid = (start+end)/2;
            }
        }
        return answer;
    }
}

개념은 쉽지만 자칫 실수하면 찾기 힘들다. 개념을 맞게 다 써놨음에도 뭔가 오류가 생겼어서 뭐가 문제였지 하고 쳐다보고 있었다.