[Java 풀스택 과정 강의] 3월 11일

※ TIL와는 별개로 적는 개인 개발 일지라서 말은 좀 편하게하는 페이지입니다.
일지이기 때문에 일기의 성격이 더 강합니다.

 

 

마지막 알고리즘 시간. 각 방법론에 대해서는 정리해둔 포스팅이 있으므로 여기를 참조.

https://bbbbabbbababababa.tistory.com/115

[Java 풀스택 개발자] 알고리즘 편#2: 알고리즘 방법론

 

여기서는 이론이 아니라 코드 관련한 내용만 다룬다.

 

DFS

DFS는 거의 재귀와 함께한다고 보면 좋은데, 재귀 문제에 대해서는 이미 몇 차례 다룬 적이 있다.

대표적인 것이 바로 블록 제거 게임.그리고 등산로이다.

 

https://bbbbabbbababababa.tistory.com/112

[코딩 테스트 RUN] SWEA 수업 : 25052. 등산로

 

 

https://bbbbabbbababababa.tistory.com/104

[코딩 테스트 RUN] SWEA RUN : 26071. 블록 제거 게임

 

DFS 및 재귀에 대해서는 많이 했는데, 말한 것처럼 순열에 대한 코드와 재귀 코드만 정리하겠다.

실제로 순열 자체는 자주 사용되지는 않는다. DFS 기본 베이스에 가까운 존재라고 생각하면 좋다.

 

반복 O 순열

  //반복 O 순열
  static int[] arr = {1,2,3}; // 사용할 숫자
  static int[] result = new int[2]; // 뽑을 개수
  static void perm(int depth) {
  // 종료 조건
    if (depth == result.length) {
      for(int x : result) {
        System.out.print(x + " ");
      } return;
    }
// 반복문 + 재귀
      for(int i = 0; i < arr.length; i++) {
      result[depth] = arr[i];
      perm(depth + 1); // 다음 자리
    }
  }
  public static void main(String[] args) {
    perm(0);
  }

 

반복 X 순열

  //반복 X 순열
  static int[] arr = {1,2,3};
  static int[] result = new int[2];
  static boolean[] visited = new boolean[3]; // 방문체크
  static void perm(int depth) {
  // 종료조건
    if(depth == result.length) {
      for(int x : result) {
        System.out.print(x + " ");
      } return;
    }
  // 반복문 + 재귀
    for(int i = 0; i < arr.length; i++) {
      if(visited[i]) continue; // 이미 사용한 숫자
      visited[i] = true;
      result[depth] = arr[i];
      perm(depth + 1);
      visited[i] = false; // 백트래킹
    }
  }
  public static void main(String[] args) {
    perm(0);
  }

 

 

 

DFS 재귀

  static boolean[] visited = new boolean[5];
  static int[][] adj = {
    {}, // 0번 노드
    {2, 3}, // 1번과 연결된 노드
    {1, 4}, // 2번
    {1, 4}, // 3번
    {2, 3} // 4번
  };
  public static void dfs(int u) {
    // 1. 현재 노드 방문 처리
    visited[u] = true;
    System.out.print(u + " ");
    // 2. 인접 노드 탐색
    for (int v : adj[u]) {
      if (!visited[v]) {
        dfs(v); // 재귀 호출
      }
    }
  }

 

 

BFS

BFS는 주로 큐를 이용한다. 최단거리 찾기에 사용함에 유의.

 

  static int[] dist = new int[5];
  static int[][] adj = {
    {}, // 0번 노드
    {2, 3}, // 1번과 연결된 노드
    {1, 4}, // 2번
    {1, 4}, // 3번
    {2, 3} // 4번
  };
  public static void bfs(int s) {
    Queue<Integer> q = new ArrayDeque<>();
    q.offer(s); // 시작 정점을 큐에 삽입
    dist[s] = 0; // 시작 정점의 거리는 0
    while (!q.isEmpty()) {
      int u = q.poll(); // 큐의 맨 앞 정점 꺼내기
      for (int v : adj[u]) {
        if (dist[v] == -1) { // 미방문
          dist[v] = dist[u] + 1;
          q.offer(v); // 큐에 삽입하여 이후 탐색
        }
      }
    }
  }

 

 

 

MST

모든 정점을 가장 적은 비용으로 이용하는 방법이다.(Greedy라고 생각하면 편하다)

소개 받은건 크루스칼과 프림이 있다. 그런데 추가로 다익스트라라는 존재도 있으니(이건 MST는 아니고 그리디의 한 종류이다.) 그 부분에 대해서도 이야기한다.

 

프림Prim 알고리즘

모든 정점을 잇는 최소 총합을 찾는 방법론이다. 모든 정점을 어떻게든 다 잇되, 사용한 간선들의 총합이 최소가 되게 하는 게 목적. 우선순위 큐를 자주 사용한다하는데… 나는 우선순위 큐와 친하지 않다. 큰일남…

 

핵심이 되는 한줄 로직은 이러하다. dist[v] = min(dist[v], weight)

 

  public static void prim(int start) {
    pq.offer(new Edge(start, 0));
    while (!pq.isEmpty()) {
      Edge cur = pq.poll(); // 최소 가중치 선택
      int u = cur.node;
      if (visited[u]) continue; // 중복 방문 방지
      visited[u] = true;
      total += cur.weight;
      for (Edge next : adj[u]) {
        if (!visited[next.node]) {
          pq.offer(next);
        }
      }
    }
  }

 

 

KRUSKAL

간선 중심의 그리디 전략을 사용한다. 정점 중심인 프림과는 기준이 다르다고 할 수 있다. 정렬과 서로소 집합을 사용한다.

중요한 부분은 간선을 미리 오름차순 정렬을 해둔다는 것.

 

핵심이 되는 한줄 로직은 이러하다. if (find(u) != find(v)) union(u, v)

 

//1. 간선 정렬 (가중치 기준 오름차순)
  Arrays.sort(edges);
for (Edge e : edges) {
// 2. 부모 확인 (Cycle 감지)
    if (find(e.u) != find(e.v)) {
      union(e.u, e.v); // 3. 집합 합치기
      cost += e.weight;
    }
  }
  //경로 압축 (Path Compression) 최적화
  int find(int x) {
    if (parent[x] == x) {
      return x;
    }
    return parent[x] = find(parent[x]);
  }

 

 

다익스트라Dijkstra

프림처럼 정점 중시이지만, 우선순위 큐가 필수이다. 시작점에서 각 정점까지의 최단 경로 찾는 것이 다익스트라의 중심이라고 할 수 있다.

 

핵심이 되는 한줄 로직은 이러하다.  dist[v] = min(dist[v], dist[u] + weight) 

 

// 1. 거리 장부 초기화
Arrays.fill(dist, INF);
dist[start] = 0;

// 2. 가방(PQ)에 시작점 넣기 {현재노드, 누적거리}
pq.offer(new int[]{start, 0});

while (!pq.isEmpty()) {
    // 3. 가장 싼(가까운) 녀석 꺼내기
    int[] curr = pq.poll();
    int u = curr[0];
    int d = curr[1];

    // 4. [중요] 이미 더 짧은 길을 알면 무시 (방문체크 대신)
    if (d > dist[u]) continue;

    // 5. 이웃집 찔러보기 (Relaxation)
    for (Edge next : adj[u]) {
        // [핵심 로직] 지금까지 온 거리(d) + 다음 칸 비용 < 기존 기록
        if (dist[next.v] > d + next.weight) {
            dist[next.v] = d + next.weight; // 장부 갱신
            pq.offer(new int[]{next.v, dist[next.v]}); // 다시 가방에 넣기
        }
    }
}