1. Recursive, Tree, Graph(DFS, BFS 기초)

---

1) 향상된 피보나치 재귀(메모리제이션)

class Main {
  static int[] fibo;
  public int DFS(int n) {
    if (fibo[n] > 0) return fibo[n];
    if (n == 1) return fibo[n] = 1;
    else if (n == 2) return fibo[n] = 1;
    else return fibo[n] = DFS(n - 2) + DFS(n - 1);
  } 
  
  public static void main(String[] args) {
    Main T = new Main();
    int n = 45;
    fibo = new int[n + 1];
    T.DFS(n);
    for (int i = 1; i < n; i++) {
      System.out.print(fibo[i] + " ");
    }
  }
}

• 스택을 계속 호출하는 재귀함수보다 for문의 성능이 더 좋다.

2) 부분집합 구하기(DFS)

static int n;
static int[] ch;
public void DFS(int L) {
  if(L == n + 1) {
    String tmp = " ";
    for (int i = 1; i <= n; i++) {
      if (ch[i] == 1) tmp += (i + " ");
    }
    if (tmp.length() > 0) System.out.println(tmp);
  }
  else {
    ch[L] = 1;
    DFS(L + 1);
    ch[L] = 0;
    DFS(L + 1);
  }
}

  public static void main(String[] args) {
    Main T = new Main();
    n = 3;
    ch = new int[n + 1];
    T.DFS(1);
  }

• n의 공집합을 제외한 모든 부분집합을 출력하는 문제이다.

2. greedy

---

1) PriorityQueue

• 선언

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 

PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

• 기본적으로 오름차순이며 Collections.reverseOrder()를 넣어줄 경우 내림차순으로 변경
• 참고자료 : https://coding-factory.tistory.com/603

2) 다익스트라 알고리즘

class Edge implements Comparable<Edge> {
  int vex;
  int cost;

  public Edge(int vex, int cost) {
    this.vex = vex;
    this.cost = cost;
  }

  @Override
  public int compareTo(Edge o) {
    return this.cost - o.cost;
  }

}


public class Main {
  static int n, m;
  static ArrayList<ArrayList<Edge>> graph;
  static int[] dis;

  public void solution(int v) {
    PriorityQueue<Edge> pQ = new PriorityQueue<>();
    pQ.offer(new Edge(v, 0));
    dis[v] = 0;
    while (!pQ.isEmpty()) {
      Edge tmp = pQ.poll();
      int now = tmp.vex;
      int nowCost = tmp.cost;
      if (nowCost > dis[now]) continue;
      for (Edge ob : graph.get(now)) {
        if (dis[ob.vex] > nowCost + ob.cost) {
          dis[ob.vex] = nowCost + ob.cost;
          pQ.offer(new Edge(ob.vex, nowCost + ob.cost));
        }
      }
    }
  }

  public static void main(String[] args) {
    Main T = new Main();
    Scanner stdIn = new Scanner(System.in);
    n = stdIn.nextInt();
    m = stdIn.nextInt();
    graph = new ArrayList<ArrayList<Edge>>();
    for (int i = 0; i < n; i++) {
      graph.add(new ArrayList<Edge>());
    }
    dis = new int[n + 1];
    Arrays.fill(dis, Integer.MAX_VALUE);
    for (int i = 0; i < m; i++) {
      int a = stdIn.nextInt();
      int b = stdIn.nextInt();
      int c = stdIn.nextInt();
      graph.get(a).add(new Edge(b, c));
    }
    T.solution(1);
    for (int i = 2; i <= n; i++) {
      if (dis[i] != Integer.MAX_VALUE)
        System.out.println(i + " : " + dis[i]);
      else
        System.out.println(i + " : impossible");
    }
  }
}