2025-11-13

오늘 배운 것

• 정렬
  1. Merge Sort

    void mergeSort(int[] arr, int l, int r) {
    	if (l < r) {
    		int m = (l+r) / 2;
    		mergeSort(arr, l, m);
    		mergeSort(arr, m+1, r);
    		merge(arr, l, m, r);
    	}
    }
      
    void merge(int[] arr, int l, int m, int r) {
    	int[] left = Arrays.copyOfRange(arr, l, m+1);
    	int[] right = Arrays.copyOfRange(arr, m+1, r+1);
    	int i = 0, j = 0, k = l;
    	while (i < left.length && j < right.length)
    		arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
    	while (i < left.length) arr[k++] = left[i++];
    	while (j < right.length) arr[k++] = right[j++];
    }
  

  • 배열을 절반으로 나누어 각각 정렬한 뒤 병합(merge)하는 분할정복 정렬이다.
  • 시간 복잡도
    • 최선 : O(n log n)
    • 평균 : O(n log n)
    • 최악 : O(n log n)
  • stable : O
  • In-place: X
  • 특징 : 항상 O(n log n) , 안정적
    1. Quick Sort

      void quickSort(int[] arr, int low, int high) {
          if (low < high) {
              int pivot = partition(arr, low, high);
              quickSort(arr, low, pivot - 1);
              quickSort(arr, pivot + 1, high);
          }
      }
            
      int partition(int[] arr, int low, int high) {
          int pivot = arr[high];
          int i = low - 1;
          for (int j = low; j < high; j++) {
              if (arr[j] <= pivot) {
                  i++;
                  int tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
              }
          }
          int tmp = arr[i+1];
          arr[i+1] = arr[high];
          arr[high] = tmp;
          return i+1;
      }
    

    • 피벗을 기준으로 작은 값과 큰 값으로 나누고 재귀적으로 정렬하는 분할정복 정렬이다.
    • 시간 복잡도
      • 최선 : O(n log n)
      • 평균 : O(n log n)
      • 최악 : O(n²)
        • 이미 정렬(또는 역순)되어 있는 배열을 고정 피봇으로 사용할 때
        • 모든 값이 동일 할 때
    • 특징 : 평균 O(n log n), 피봇 선택 잘못되면 O(n²) 6. Heap Sort

      void heapSort(int[] arr) {
          int n = arr.length;
          for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // n/2 이후에는 부모 노드가 없음
          for (int i = n - 1; i > 0; i--) {
              int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp;
              heapify(arr, i, 0);
          }
      }
            
      void heapify(int[] arr, int n, int i) {
          int largest = i, left = 2 * i + 1, right = 2 * i + 2;
          if (left < n && arr[left] > arr[largest]) largest = left;
          if (right < n && arr[right] > arr[largest]) largest = right;
          if (largest != i) {
              int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp;
              heapify(arr, n, largest);
          }
      }
    

    • 최대(또는 최소) 힙을 구성한 뒤, 루트를 꺼내며 정렬한다.
    • 시간 복잡도
      • 최선 : O(n log n)
      • 평균 : O(n log n)
      • 최악 : O(n log n)
    • stable : X
      • 힙 정렬은 부모·자식 노드 간에 큰 값이 밑으로, 작은 값이 위로 이동하면서 동일한 key를 가진 원소들의 ‘상대적 순서’를 보존할 방법이 없다.
    • In-place : O
    • 특징: 항상 O(n log n), 안정성보다 속도 우선 7. Counting Sort

      void countingSort(int[] arr, int maxValue) {
          int[] count = new int[maxValue+1];
          for (int num : arr) count[num]++;
          int idx = 0;
          for (int i = 0; i <= maxValue; i++)
              while (count[i]-- > 0) arr[idx++] = i;
      }
    

    • 각 값의 등장 횟수를 세어 누적 합으로 위치를 계산해 정렬한다. (비교 정렬 아님)
    • 시간 복잡도 (k = maxValue)
      • 최선 : O(n + k)
      • 평균 : O(n + k)
      • 최악 : O(n + k)
    • 공간 복잡도 : O(n + k)
    • stable: O
      • 단 구현시 누적 count 사용해야 함
    • In-place : X
    • 특징 : 값의 범위가 작을 때 O(n + k)
      • Counting Sort는 k가 입력 크기n와 비슷하거나 더 작을 때 O(n + k)로 매우 효율적이다.
      • 하지만 k가 n보다 훨씬 커지면 비효율적이다.
        1. Radix Sort

      void radixSort(int[] arr) {
          int max = Arrays.stream(arr).max.getAsInt();
          for (int exp = 1; max / exp > 0; exp *= 10)
              countingSortByDigit(arr, exp);
      }
            
      void countingSortByDigit(int[] arr, int exp) {
          int n = arr.length;
          int[] output = new int[n]; // 최종 저장
          int[] count = new int[10]; // 0 ~ 9 자릿수 빈도
          for (int num : arr) count[(num / exp) % 10]++;
          for (int i = 1; i < 10; i++) count[i] += count[i-1]; // 누적합을 해서 끝나는 위치에 넣을 수 있게 함
          for (int i = n - 1; i >= 0; i--) {
              int idx = (arr[i] / exp) % 10;
              output[--count[idx]] = arr[i];
          }
          System.arraycopy(output, 0, arr, 0, n);
      }
    

    • 자릿수(1의 자리 → 10의 자리 등)별로 Counting Sort를 반복해 정렬한다.
    • 시간 복잡도 (d : 자릿수, k: 값의 범위)
      • 최선 : O(d·(n + k))
      • 평균 : O(d·(n + k))
      • 최악 : O(d·(n + k))
    • stable : O
    • In-place: X
    • 특징: 자리수 기반, Counting Sort 응용
      • 숫자 범위가 크고 자릿수가 일정하며, Stable한 선형 알고리즘을 반복할 수 있을 때
      • n이 매우 클 때 유리
      • 실수가 있거나 자릿수가 불규칙하면 사용 불가
        1. Tim Sort
    • Insertion Sort와 Merge Sort를 결합한 하이브리드 정렬로,작은 부분(run)은 삽입 정렬로 빠르게 처리하고, 큰 부분은 병합 정렬로 안정적으로 병합한다.Java와 Python의 기본 정렬로 사용된다
      • Java의 Arrays.sort() (객체 타입)는 Tim Sort
    • 시간 복잡도

      • 최선: O(n)

        → 데이터가 이미 거의 정렬된 경우(run이 많음)

      • 평균: O(n log n)
      • 최악: O(n log n)
    • stable : O
    • In-place : X
    • 특징 : 실제 서비스 코드에서 가장 많이 사용됨.

• 자바 정렬

  | 구분 | 메서드 | 알고리즘 | Stable | In-place | 설명 | | — | — | — | — | — | — | | 기본 타입 배열 | Arrays.sort(int[]) | Dual-Pivot QuickSort | ❌ | ✅ | 성능 최우선 평균 O(n log n) 최악 O(n²) <매우 희귀=""> | | 객체 배열 | Arrays.sort(T[]) | **Tim Sort** | ✅ | ❌ | Java 기본 객체 정렬 평균/최악 O(n log n) | | List 정렬 | Collections.sort(List) | **Tim Sort** | ✅ | ❌ | 내부적으로 배열 변환 후 Tim Sort 평균/최악 O(n log n) | | 병렬 정렬 | Arrays.parallelSort() | **Parallel Merge Sort** | 객체는 Stable | ❌ | Fork/Join 기반 병렬 처리 최악 O(n log n) |

  • 이중 피벗 퀵 정렬
    • 피벗을 2개 사용하고, 배열을 3구간으로 나눠서 정렬하는 퀵정렬 변형
    • 분할 효율이 좋아지고 캐시 활용성이 증가해 기존 퀵 정렬보다 더 빠르다
  • Parallel Merge Sort + Fork/Join
    • 병합 정렬을 병렬 처리로 확장한 것
    • CPU의 여러 코어를 동시에 활용해서 매우 큰 배열을 빠르게 정렬한다.
    • 작은 배열에는 오히려 느리므로 큰 배열일 때 사용

• 최단 경로

  | 알고리즘 | 가중치 | 음수 | 음수 사이클 | 목적 | 시간복잡도 | | — | — | — | — | — | — | | BFS | X(=1) | X | X | 단일 시작 | O(V+E) | | Dijkstra | 양수 | X | X | 단일 시작 | O(E log V) | | Bellman-Ford | 가능 | O | O | 단일 시작 | O(VE) | | Floyd-Warshall | 가능 | 부분 | X | 모든 쌍 | O(V³) | | SPFA | 가능 | O | △ | 단일 시작 | 평균 빠름, 최악 O(VE) |

  1. BFS
     • 설명
       • 가중치가 모두 동일(=1)일 때 사용하는 최단 경로 알고리즘
       • 가중치 없을 때 가장 빠르고 명확
     • 장점
       • 빠름 : O(V+E)
       • 구현 단순
       • 최단 경로 100% 보장
     • 단점
       • 가중치가 있을 경우 사용불가
     • 시간복잡도
       • O(V + E)
  2. Dijkstra
     • 설명
       • 가중치가 양수일 때 최단 경로 찾는 표준 알고리즘
       • 우선순위 큐(min-heap)를 이용해 현재까지 비용이 가장 작은 노드부터 탐색
       • 그리디 + DP
     • 장점
       • 빠르고 정확
       • 양수 가중치 그래프 최단 경로 최적
     • 단점
       • 음수 간선이 있으면 사용 불가
       • 힙 없는 구현은 느림
     • 시간복잡도(우선순위 큐 사용 시)
       • O(E log V)

     • 코드

         int[] dijkstra(int start, List<List<Node>> graph) {
             int n = graph.size();
             int[] dist = new int[n];
             Arrays.fill(dist, Integer.MAX_VALUE);
             dist[start] = 0;
                   
             PriorityQueue<Node> pq = new PriorityQueue<>((a,b) -> a.cost - b.cost);
             pq.add(new Node(start, 0));
                   
             while (!pq.isEmpty()) {
                 Node cur = pq.poll();
                 if (cur.cost > dist[cur.id]) continue;
                   
                 for (Node next : graph.get(cur.id)) {
                     int newCost = cur.cost + next.cost;
                     if (newCost < dist[next.id]) {
                         dist[next.id] = newCost;
                         pq.add(new Node(next.id, newCost));
                     }
                 }
             }
             return dist;
         }
                   
         class Node {
             int id, cost;
             Node(int id, int cost) { this.id=id; this.cost=cost; }
         }
                   
       

  3. Bellman-Ford
     • 설명
       • 음수 간선이 있어도 최단 경로를 찾을 수 있는 알고리즘
       • 모든 간선을 V-1번 반복하며 검사
       • 음수 사이클도 탐지 가능
     • 장점
       • 음수 가중치 그래프 가능
       • 음수 사이클 검출 가능
     • 단점
       • 느림 O(VE)
       • 노드 수 많으면 비효율적
     • 시간복잡도
       • O(VE)

     • 코드

         int[] bellmanFord(int n, int start, List<Edge> edges) {
             int[] dist = new int[n];
             Arrays.fill(dist, Integer.MAX_VALUE);
             dist[start] = 0;
                   
             for (int i = 0; i < n - 1; i++) {
                 for (Edge e : edges) {
                     if (dist[e.from] != Integer.MAX_VALUE && // 방문 했었고
                          dist[e.from] + e.cost < dist[e.to]) { // 기존 방문 한것보다 더 작으면
                         dist[e.to] = dist[e.from] + e.cost;
                     }
                 }
             }
                   
             // 음수 사이클 검출
             for (Edge e : edges) {
                 if (dist[e.from] != Integer.MAX_VALUE &&
                     dist[e.from] + e.cost < dist[e.to]) { // 또 줄어들 수 있다면 음수 사이클!
                     throw new RuntimeException("Negative Cycle Detected");
                 }
             }
                   
             return dist;
         }
                   
         class Edge {
             int from, to, cost;
             Edge(int f, int t, int c) { from=f; to=t; cost=c; }
         }
                   
       

  4. Floyd-Warshall
     • 설명
       • 그래프 모든 쌍(u → v)의 최단 거리를 구함
       • DP 기반
       • dist[i][j] 를 중간 노드 k를 거쳐 갱신
       • 모든 쌍 최단 거리 문제에 가장 표준
     • 장점
       • 모든 노드쌍 최단 경로 구할 수 있음
       • 구현이 간단함
       • 음수 간선 가능(단, 음수 사이클은 안됨)
     • 단점
       • O(n³) → 노드가 500개 넘어가면 사실상 불가
       • 메모리 O(n²)
     • 시간복잡도
       • O(n³)

     • 코드

         void floydWarshall(int[][] dist, int n) {
             for (int k = 0; k < n; k++) {
                 for (int i = 0; i < n; i++) {
                     for (int j = 0; j < n; j++) {
                         if (dist[i][k] + dist[k][j] < dist[j][j]) // k를 경유해서 간게 더 작으면
                             dist[i][j] = dist[i][k] + dist[k][j];
                     }
                 }
             }
         }
       

  5. SPFA
     • 설명
       • 벨만 포드를 큐로 최적화한 알고리즘
       • 실제로는 매우 빠르게 동작할 때도 많음
       • 하지만 최악은 벨만 포드랑 동일
     • 장점
       • 현실 데이터에서는 빠르게 작동
       • 음수 가중치 가능
     • 단점
       • 최악은 벨만 포드랑 동일
       • 음수 사이클이 있으면 무한 루프 위험
     • 시간복잡도
       • 평균 : 매우 빠름
       • 최악 : O(VE)
  6. A*(A-start)
     • 설명
       • 다익스트라 + 휴리스틱
       • 게임/지도/AI 경로 탐색에서 많이 사용
     • 장점
       • 다익스트라보다 훨씬 빠른 경우 많음
       • 목적지까지의 휴리스틱을 활용해 탐색 감소
     • 단점
       • 정확한 휴리스틱 필요
       • 일반 그래프 최단 거리 문제에는 잘 안씀
     • 시간복잡도(b = branching factor(자식노드수), d = 최단 경로 깊이)
       • 휴리스틱이 좋으면 O(d)
       • 휴리스틱이 안좋으면 O(b^d)
       • 평균 O(E log V) → 그래도 대부분 다익스트라보다 훨씬 빠름
• 최소 신장 트리
  1. Kruskal
     • 설명
       • 간선을 오름차순으로 정렬한 후, 사이클이 생기지 않는 간선만 선택해 MST를 만드는 알고리즘
       • 핵심 자료구조 : Union-Find(Disjoint Set)
       • 간선 중심 알고리즘
     • 동작과정
       1. 간선 비용 오름차순 정렬
       2. 작은 간선부터 확인
       3. 사이클이 아니면 선택(Union)
       4. 간선이 V-1개 되면 종료
     • 장점
       • 구현 쉽고 직관적
       • 희소 그래프(간선이 적음)에 매우 효율적
       • 간선만 정렬하면 되서 메모리 효율적
     • 단점
       • 간선 정렬 필요 → O(E log E)
       • Union-Find 사용해야 효율적
       • Dense 그래프(간선이 많음)는 prim 보다 비효율
     • 시간복잡도
       • O(E log E) ≈ O(E log V)

     • 코드

         class Edge implements Comparable<Edge> {
             int u, v, w;
             Edge(int u, int v, int w) { this.u=u; this.v=v; this.w=w; }
                   
             @Override
             public int compareTo(Edge o) {
                 return this.w - o.w;
             }
         }
                   
         int kruskal(int V, List<Edge> edges) {
             Collections.sort(edges);
             UnionFind uf = new UnionFind(V);
                   
             int total = 0;
             for (Edge e : edges) {
                 if (uf.find(e.u) != uf.find(e.v)) { // cycle X
                     uf.union(e.u, e.v);
                     total += e.w;
                 }
             }
             return total;
         }
                   
         class UnionFind {
             int[] parent, rank;
                   
             UnionFind(int n) {
                 parent = new int[n];
                 rank = new int[n];
                 for (int i = 0; i < n; i++) parent[i] = i;
             }
                   
             int find(int x) {
                 if (parent[x] == x) return x;
                 return parent[x] = find(parent[x]);
             }
                   
             void union(int a, int b) {
                 a = find(a); b = find(b);
                 if (a == b) return;
                   
                 if (rank[a] < rank[b]) parent[a] = b;
                 else if (rank[a] > rank[b]) parent[b] = a;
                 else {
                     parent[b] = a;
                     rank[a]++;
                 }
             }
         }
       

  2. Prim
     • 설명
       • 하나의 정점에서 시작해서 늘 현재 MST에 가장 가까운 간선을 연결해 나가는 방식
       • 핵심 자료구조 : 우선순위 큐(Min-Heap)
       • 정점 중심 알고리즘
       • 다익스트라와 유사
     • 동작 과정
       1. 시작 노드 선택
       2. 최소 가중치 간선 선택해서 MST에 추가
       3. 새로운 정점 기준으로 가장 작은 간선 선택
       4. 모든 정점 포함될 때까지 반복
     • 장점
       • Dense 그래프(간선이 많음)에서 더 효율적 → 인접 리스트 + PQ 사용시 O(E log V)
       • 시작점 있어도 상관 없음
       • 음수 가중치 가능
     • 단점
       • 구현이 크루스칼보다 복잡
       • PQ 힙 사용 필수 → 메모리 사용 많음
     • 시간복잡도
       • O(E log V) 우선 순위 큐 사용 시

     • 코드

         class Node implements Comparable<Node> {
             int v, w;
             Node(int v, int w) { this.v=v; this.w=w; }
                   
             @Override
             public int compareTo(Node o) {
                 return this.w - o.w;
             }
         }
                   
         int prim(int V, List<List<Node>> graph) {
             boolean[] visited = new boolean[V];
             PriorityQueue<Node> pq = new PriorityQueue<>();
             pq.add(new Node(0, 0)); // 시작점: 0번
                   
             int total = 0;
             while (!pq.isEmpty()) {
                 Node cur = pq.poll();
                 if (visited[cur.v]) continue;
                 visited[cur.v] = true;
                 total += cur.w;
                   
                 for (Node next : graph.get(cur.v)) {
                     if (!visited[next.v]) pq.add(next);
                 }
             }
             return total;
         }
       

• TSP(Traveling Salesman Problem 외판원 순회)
  • 설명
    • 여러 도시를 한번씩 방문하고, 출발점으로 돌아오는 경로 중 총 비용이 최소가 되는 경로를 찾는 문제
    • 그래프에서 모든 정점을 한 번씩 방문하는 순환 경로의 최소 비용
    • 대표적인 NP-Hard 문제
    • 완전 탐색은 불가능 할 정도로 경우의 수 폭발
  • 해결 방법
    1. 완전 탐색
       • 설명
         • 모든 순열 만들어서 최솟값 찾기
         • 도시의 수 N ⇒ 경우의수 (n-1)!
           • N이 15만 되어도 불가능
       • 장점
         • 구현 쉬움
       • 단점
         • N>10이상이면 불가능
       • 시간 복잡도
         • O(N!)
    2. DP + Bitmask
       • 설명
         • 현재 위치 + 방문한 집합(mask)을 이용해 부분 문제를 정의하는 방식
         • 상태 정의 dp[mask][i] = mask(방문 상태)일 때, 마지막 도시가 i인 최소 비용
         • 점화식 dp[mask][i] = min(dp[mask - i][j] + cost[j][i])
       • 장점
         • N≈15~20까지 가능 / 정확한 최적해
       • 단점
         • 시간·메모리 크다
       • 시간 복잡도
         • O(N² × 2^N)

       • 코드

           static final int INF = 1_000_000_000;
                         
           int tsp(int[][] W) {
               int N = W.length;
               int FULL = (1 << N);
               int[][] dp = new int[FULL][N];
                         
               for (int i = 0; i < FULL; i++)
                   Arrays.fill(dp[i], INF);
                         
               dp[1][0] = 0; // 시작점: 도시 0 방문
                         
               for (int mask = 0; mask < FULL; mask++) {
                   for (int i = 0; i < N; i++) {
                       if ((mask & (1 << i)) == 0) continue; // i를 방문하지 않은 상태면 skip
                       for (int j = 0; j < N; j++) {
                           if ((mask & (1 << j)) != 0) continue; // 이미 j 방문
                           if (W[i][j] == 0) continue; // 경로 없음
                         
                           int nextMask = mask | (1 << j);
                           dp[nextMask][j] =
                               Math.min(dp[nextMask][j], dp[mask][i] + W[i][j]);
                       }
                   }
               }
                         
               int answer = INF;
               for (int i = 1; i < N; i++) {
                   if (W[i][0] == 0) continue;
                   answer = Math.min(answer, dp[FULL - 1][i] + W[i][0]);
               }
               return answer;
           }
                         
         

• 위상 정렬
  • 정의
    • 사이클이 없는 방향 그래프에서 모든 간선에 u가 v보다 먼저 오도록 정점을 일렬로 나열하는 알고리즘
    • 선행 조건이 있는 작업을 순서대로 나열하는 기법
  • 조건
    • 사이클이 없어야 함(DAG) 있으면 계속 순환!
  • 시간 복잡도
    • O(V + E)
  • 종류
    • Kahn’s Algorithm(진입 차수 기반, BFS 방식)
      • 동작 과정
        1. 모든 정점의 진입 차수 계산
        2. 진입 차수가 0인 정점을 큐에 삽입
        3. 큐에서 하나씩 꺼내 정렬 결과에 추가
        4. 해당 정점이 가진 간선을 제거
        5. 진입 차수가 0이 되면 다시 큐에 삽입
        6. 큐가 빌 때까지 반복
        7. 모든 노드가 처리되면 성공 // 처리 개수가 V보다 적으면 사이클 존재
      • 장점
        • 직관적이고 구현 쉬움
        • DAG 여부 같이 판별
      • 단점
        • 진입 차수 배열 필요
        • 스택으로 구현하려면 번거로움

      • 코드

          List<Integer> topologicalSort(int V, List<List<Integer>> graph) {
              int[] indegree = new int[V];
              for (int u = 0; u < V; u++) {
                  for (int v : graph.get(u)) {
                      indegree[v]++;
                  }
              }
                        
              Queue<Integer> q = new LinkedList<>();
              for (int i = 0; i < V; i++) {
                  if (indegree[i] == 0) q.add(i);
              }
                        
              List<Integer> result = new ArrayList<>();
                        
              while (!q.isEmpty()) {
                  int cur = q.poll();
                  result.add(cur);
                        
                  for (int next : graph.get(cur)) {
                      if (--indegree[next] == 0)
                          q.add(next);
                  }
              }
                        
              // 사이클 체크
              if (result.size() != V)
                  throw new RuntimeException("Cycle Exists – Topological Sort Not Possible");
                        
              return result;
          }
        

    • DFS 기반 위상 정렬 - 스택 활용
      • DFS로 깊게 탐색하고
      • 모든 자식을 다 방문한 뒤
      • 현재 노드를 스택에 푸시
      • 마지막에 스택을 뒤집으면 끝