카테고리 없음

[알고리즘] 그리디

Dev_Camp 2025. 4. 13. 01:00

다익스트라 (Dijkstra's Algorithm)

  1. 다익스트라 알고리즘은 가중치가 있는 그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 그리디 알고리즘이다. 이 알고리즘은 항상 현재 상태에서 가장 비용이 적은 노드를 선택하는 방식으로 동작한다.
    1. 시작 노드를 설정하고, 시작 노드에서 직접 연결된 모든 노드까지의 거리를 초기화한다.
    2. 미방문 노드 중에서 현재까지의 최단 거리가 가장 짧은 노드를 선택한다.
    3. 선택한 노드를 방문 처리하고, 이 노드를 거쳐 갈 수 있는 다른 노드들의 최단 거리를 갱신한다.
    4. 모든 노드를 방문할 때까지 2-3 과정을 반복한다. 
    구현 상세:
    • touch[i]: 노드 i로 가는 최단 경로에서 i 직전에 방문하는 노드 번호
    • length[i]: 시작 노드(v₁)에서 노드 i까지의 현재까지 발견된 최단 거리
    • F: 최단 경로가 확정된 노드들의 집합
    • vnear: 현재 탐색 중인, 미방문 노드 중 시작점으로부터 거리가 가장 가까운 노드
    코드는 다음과 같이 동작한다:

    1. 초기화:
      • touch[2..n]을 1로 설정 (모든 노드는 처음에는 시작 노드에서 직접 연결된다고 가정)
      • length[2..n]을 W[1][i]로 설정 (시작 노드에서 각 노드까지의 직접 연결 거리)
      • F를 빈 집합으로 초기화
    2. 주 반복문:
      • 미방문 노드 중 length 값이 가장 작은 노드 vnear를 찾는다.
      • (touch[vnear], vnear) 간선을 F에 추가한다.
      • vnear를 통해 다른 미방문 노드들의 최단 경로를 갱신한다:
        • 각 노드 i에 대해, length[vnear] + W[vnear][i] < length[i]이면
        • length[i] = length[vnear] + W[vnear][i]로 갱신
        • touch[i] = vnear로 설정
    3. length[vnear]를 -1로 설정하여 해당 노드를 처리 완료로 표시한다.


    • 시작 노드 v₁에서 출발하여 단계적으로 최단 경로를 찾아나간다.
    • 첫 단계에서 v₁과 직접 연결된 노드들(v₂, v₃, v₅)까지의 거리를 초기화한다.
    • 초기화 이후 가장 거리가 짧은 v₅를 선택하고(거리 1), 이를 통해 v₄까지의 경로를 갱신한다.
    • 다음으로 거리가 짧은 v₄를 선택하고(거리 2), 이를 통해 다른 노드들의 최단 경로를 갱신한다.
    • 이 과정을 반복하여 v₁에서 v₂까지의 최단 경로 [v₁, v₅, v₄, v₃, v₂]를 찾는다.

 

 

 

 

 

 

 

 

허프만 코딩 (Huffman Coding)

허프만 코딩은 문자의 출현 빈도에 따라 가변 길이 코드를 할당하는 데이터 압축 알고리즘이다. 자주 등장하는 문자에는 짧은 코드를, 드물게 등장하는 문자에는 긴 코드를 할당하여 전체 데이터 크기를 최소화한다.

 

알고리즘 원리:

  1. 각 문자와 그 출현 빈도수를 리프 노드로 하는 초기 포레스트를 구성한다.
  2. 출현 빈도가 가장 낮은 두 노드를 선택하여 이들을 자식으로 하는 새로운 노드를 생성한다. 이 새 노드의 빈도는 두 자식 노드 빈도의 합이다.
  3. 새 노드를 포레스트에 추가하고 선택된 두 노드를 제거한다.
  4. 포레스트에 단 하나의 노드만 남을 때까지 2-3 과정을 반복한다.
  5. 이렇게 구성된 이진 트리에서 루트에서 각 리프 노드까지의 경로를 코드워드로 사용한다. 왼쪽 간선은 '0', 오른쪽 간선은 '1'로 표현한다.

 


허프만 코드 구축 단계:

  1. 빈도수가 가장 낮은 두 노드 b-5와 e-10을 선택하여 합친다. 새 노드의 값은 15이다.
  2. 다음으로 빈도수가 낮은 두 노드 c-12와 15(b-5+e-10)를 선택하여 합친다. 새 노드의 값은 27이다.
  3. 다음으로 a-16과 d-17을 선택하여 합친다. 새 노드의 값은 33이다.
  4. 마지막으로 f-25와 27(c-12+(b-5+e-10))을 선택하여 합친다. 새 노드의 값은 52이다.
  5. 최종적으로 33(a-16+d-17)과 52(f-25+(c-12+(b-5+e-10)))를 합쳐 루트 노드 85를 생성한다.

트리가 완성되면 왼쪽 간선을 '0', 오른쪽 간선을 '1'로 간주하여 각 문자의 코드를 생성한다. 예를 들어, 'b'의 코드는 '100'이 된다.

 

이 코드는 힙 자료구조를 사용하여 빈도수가 낮은 노드들을 효율적으로 선택한다.

 

 

 

 

 

 

 

 

 

0-1 배낭 문제 (Knapsack Problem)

0-1 배낭 문제는 각 물품을 통째로 넣거나 넣지 않는 방식으로, 주어진 무게 제한 내에서 가치의 합이 최대가 되도록 물품을 선택하는 문제이다.

 

0-1 배낭 문제는 동적 계획법(Dynamic Programming)을 사용하여 해결한다. 점화식은 다음과 같다:



여기서:

  • P[n][W]: n개의 물품과 배낭 용량 W를 고려할 때 얻을 수 있는 최대 가치
  • p_n: n번째 물품의 가치
  • w_n: n번째 물품의 무게

 

다음은 3개의 물품과 최대 무게 30kg인 배낭 문제를 해결하는 과정을 보여준다:

 

 

  1. 물품 정보:
    • item₁: 5kg, 50만원, 단위 무게당 10만원/kg
    • item₂: 10kg, 60만원, 단위 무게당 6만원/kg
    • item₃: 20kg, 140만원, 단위 무게당 7만원/kg
  2. 점화식을 사용한 계산:
    • P[1][0] = 0 (물품이 없거나 배낭 용량이 0인 경우)
    • P[1][10] = max(P[0][10], 50 + P[0][10-5]) = max(0, 50 + 0) = 50
    • P[1][20] = max(P[0][20], 50 + P[0][20-5]) = max(0, 50 + 0) = 50
    • P[1][30] = max(P[0][30], 50 + P[0][30-5]) = max(0, 50 + 0) = 50
    • P[2][10] = max(P[1][10], 60 + P[1][0]) = max(50, 60 + 0) = 60
    • P[2][30] = max(P[1][30], 60 + P[1][20]) = max(50, 60 + 50) = 110
    • P[3][30] = max(P[2][30], 140 + P[2][10]) = max(110, 140 + 60) = 200

따라서 최대 가치는 200만원으로, item₂와 item₃를 선택하는 것이 최적이다.

  • P[n][W]는 n개의 물품과 배낭 용량 W를 고려할 때 얻을 수 있는 최대 가치이다.
  • 두 가지 경우를 고려한다:
    1. n번째 물품의 무게(wn)가 W 이하인 경우: max(n번째 물품을 포함하지 않는 경우, n번째 물품을 포함하는 경우)
    2. n번째 물품의 무게가 W보다 큰 경우: n번째 물품을 포함하지 않는 경우의 값

 

 

 

 

 

 

 

 

상호배타적 집합 (Disjoint Sets)

상호배타적 집합(또는 Union-Find 자료구조)은 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다.

 

주요 연산:

  1. Find: 어떤 원소가 속한 집합의 대표 원소(루트)를 찾는다.
  2. Union: 두 집합을 하나로 합친다.

 

 

최적화 기법:

  1. Weighting-Union Heuristic:
    • Union 연산 시 작은 집합을 큰 집합에 합친다.
    • 이를 통해 트리의 높이를 최소화하여 Find 연산의 효율성을 향상시킨다.
    • 시간 복잡도: O(n log n)
  2. Path Compression:
    • Find 연산을 수행할 때, 방문하는 모든 노드들을 루트 노드의 직접적인 자식으로 만든다.
    • 이를 통해 이후의 Find 연산이 더 빠르게 수행될 수 있도록 한다.
    • 위 그림에서 "path compression 수행 후"라고 표시된 부분에서 이러한 최적화가 적용된 결과를 볼 수 있다.

 

 

  1. Weighting-Union Heuristic: union 연산 시 작은 집합을 큰 집합으로 합쳐 트리의 높이를 최소화한다. 이로 인해 시간 복잡도가 O(n log n)으로 개선된다.
  2. Path Compression: find(z) 연산을 수행할 때 방문하는 모든 노드들을 루트의 직접적인 자식으로 만든다. 이는 find 연산의 성능을 크게 향상시킨다.

이러한 두 가지 최적화를 함께 사용하면, 연산의 수행 시간이 거의 상수 시간에 가까워진다.