• 알기쉬운 알고리즘(양성봉 저, 생능 출판) 책을 바탕으로 작성한 내용이다.

04. 그리디(Greedy) 알고리즘

• 최적화 문제를 해결하는 알고리즘이다.

• 입력 데이터 간의 관계를 고려하지 않고, 수행 과정에서 최솟값 또는 최댓값을 가진 데이터를 선택한다.

  • 근시안적 선택으로 부분적인 최적해를 찾고, 이를 모아서 문제 전체의 최적해를 찾는다.

• 한번 선택하면 번복하지 않아서 알고리즘들이 비교적 단순하다.

4.1 동전 거스름돈

• 거스름돈의 동전 개수를 가장 적게 받는 방법

• 남은 액수를 초과하지 않는 조건에서 가장 큰 액면의 동전을 취하는 방법을 사용한다.

  Pseudo Code

  int CountCoin(int change)
  {
    int n500 = n100 = n50 = n10 = n1 = 0;
    while (change >= 500)
    {
      change -= 500;
      n500++;
    }
    while (change >= 100)
    {
      change -= 100;
      n100++;
    }
    while (change >= 50)
    {
      change -= 50;
      n50++;
    }
    while (change >= 10)
    {
      change -= 10;
      n10++;
    }
    while (change >= 1)
    {
      change -= 1;
      n1++;
    }
    return (n500 + n100 + n50 + n10 + n1);
  }

• 만약 160원짜리 동전이 추가된다면, 이 알고리즘은 최적해를 보장하지 못한다.

  • 어떤 경우에도 최적해를 찾고 싶으면 동적 계획 알고리즘을 사용해야 한다.

4.2 최소 신장 트리(Minimum Spanning Tree)

4.3 최단 경로 찾기(Shortest Path)

4.4 부분 배낭 문제(Fractional Kanpsack Problem)

4.5 집합 커버 문제(Set Cover Problem)

4.6 작업 스케줄링(Task Scheduling)

4.7 허프만 압축(Huffman Coding)

작업 스케줄링(Task Scheduling)

• 기계에서 수행되는 n개의 작업들을 수행 시간이 중복되지 않도록 가장 적은 수의 기계에 배정하는 문제이다.

  • 각 작업은 시작시간과 종료시간이 정해져있다.

  • 발표 시간이 정해진 학술대회에서 발표자들을 강의실에 배정하는 문제와 같다.

알고리즘

• 다음과 같은 그리디 알고리즘이 존재한다.

  • 빠른 시작 시간 작업 우선 (Earliest Start Time First)

  • 빠른 종료 시간 작업 우선 (Earliest Finish Time First)

  • 짧은 작업 우선 (Shortest Job First)

  • 긴 작업 우선 (Longest Job First)

  • 여기서는 최적해를 찾기 위해 첫 번째 방법을 선택한다.

• 빠른 시작 시간 작업 우선 (Earliest Start Time First)

  Pseudo Code

  JobScheduling(Task *arr)
  {
    Task list[] = arr를 시작 시간을 기준으로 오름차순 정렬한 배열
    while (list에 원소가 존재하면)
    {
      t_i = (가장 이른 시작 시간을 가진 작업);
      if (t_i를 수행할 기계가 존재하면)
        t_i를 해당 기계에 배정한다.
      else
        새로운 기계에 t_i를 배정한다.
      t_i를 list에서 제거한다.
    }
    return 각 기계에 배정된 작업 순서
  }

예제

• 시작 시간과 종료 시간을 [start time, end time]이라고 표기한다.

  t₁ = [7, 8]

  t₂ = [3, 7]

  t₃ = [1, 5]

  t₄ = [5, 9]

  t₅ = [0, 2]

  t₆ = [6, 8]

  t₇ = [1, 6]

• 시작 시간을 기준으로 오름차순 정렬하여 list에 저장하면 다음과 같다.

  list = { [0, 2], [1, 5], [1, 6], [3, 7], [5, 9], [6, 8], [7, 8] }

  

시간 복잡도

• 배열을 정렬할 때 O(nlogn) 시간이 걸린다.

• 사용된 기계의 수를 m이라고 하면, 루프 내부에서 기계를 찾을 때의 시간 복잡도는 O(m)이다.

  • 루프가 n번 반복되므로 총 O(mn)이다.

• 따라서 총 시간 복잡도는 O(nlogn) + O(mn)이다.

집합 커버 문제 (Set Cover Problem)

• 전체 집합 U와, 그 부분 집합 S_i들을 원소로 갖는 집합 F가 있다고 하자.

• F의 원소인 S_i들을 합집합하여 전체 집합 U와 같아지는 집합 S_i들의 최소 개수를 찾는 문제이다.

• F에 있는 집합들의 모든 조합을 하나씩 찾을 경우

  • 만약 F의 원소의 개수가 n개이면 나올 수 있는 경우의 수는 (2ⁿ - 1)개이고, n이 증가함에 따라 이 방식으로 최적해를 찾는 것은 실질적으로 불가능하다.

• 따라서 최적해 대신 최적해에 근접한 근사해(Approximation Solution)을 찾아야 한다.

  • U에 있는 원소를 가장 많이 커버하는 S_i를 반복적으로 찾아서 포함시키는 방식을 사용한다.

알고리즘

• 입력에 전체 집합 U와 그 부분 집합 S_i들을 포함한 집합 F가 주어진다.

  Pseudo Code

  SetCover(Set u, Set f)
  {
    Set cover;
    while (u.size() != 0)
    {
      u의 원소들을 가장 많이 포함하는 집합 s_i를 f에서 선택한다.
      u에서 s_i를 뺀다. (차집합)
      s_i를 cover에 추가한다.
      s_i를 f에서 제거한다.
    }
    return cover;
  }

  ---

예제

신도시를 계획하는데 10개의 마을에 학교를 배치해야 한다.

• 각 점은 마을을 의미하고, 선분은 15분 이내의 거리를 뜻한다.

• 학교는 마을에 위치해야 하고, 등교 거리는 15분 이내여야 한다.

  

• 집합 커버 문제로 변환시키면 다음과 같다.

  U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

  F = {S₁, S₂, S₃, S₄, S₅, S₆, S₇, S₈, S₉, S₁₀}

  S₁ = {1, 2, 3, 8}

  S₂ = {1, 2, 3, 4, 8}

  S₃ = {1, 2, 3, 4}

  S₄ = {2, 3, 4, 5, 7, 8}

  S₅ = {4, 5, 6, 7}

  S₆ = {5, 6, 7, 9, 10}

  S₇ = {4, 5, 6, 7}

  S₈ = {1, 2, 4, 8}

  S₉ = {6, 9}

  S₁₀ = {6, 10}

• 위의 알고리즘을 적용하는 순서는 다음과 같다.

  • 첫 번째 루프

    • 집합 U의 원소를 가장 많이 커버하는 집합인 S₄를 F에서 선택한다.

    • U에서 S₄를 빼면 U = {1, 6, 9, 10}이 된다.

    • S₄를 cover에 추가하고 F에서 제거한다.

  • 두 번째 루프

    • 집합 U의 원소를 가장 많이 커버하는 집합인 S₆를 F에서 선택한다.

    • U에서 S₆를 빼면 U = {1}이 된다.

    • S₆를 cover에 추가하고 F에서 제거한다.

  • 세 번째 루프

    • 집합 U의 원소를 가장 많이 커버하는 집합인 S₁를 F에서 선택한다.

    • U에서 S₁를 빼면 U는 공집합이 된다.

    • S₁를 cover에 추가하고 F에서 제거한다.

  • S₁, S₄, S₆이 담긴 cover를 리턴한다.

시간 복잡도

• 루프를 반복하는 횟수는 최대 n번이다.

• 전체 집합 U의 원소를 가장 많이 포함하는 집합 S_i를 찾을 때 걸리는 시간 복잡도는 O(n²)이다.

• 집합 U에서 집합 S_i를 뺄 때 O(n)이 걸린다.

• S_i를 cover에 추가하고 F에서 뺄 때 O(1)이 걸린다.

• 따라서 전체 시간 복잡도는 O(n³)이다.

  • 이는 지수 시간(2ⁿ)에 비해 굉장히 짧은 시간이다.

근사 비율 (Approximation Ratio)

• 근사 알고리즘에서 근사해가 최적해에 얼마나 가까운지를 나타내는 척도이다.

• SetCover 알고리즘의 근사 비율은 Klogn이라고 한다.

  • K는 최적해의 집합의 수이다.

  • 위의 예제에서는 최적해의 개수 K = 2이므로 Klogn = 2log10 < 8이다.

  • 즉 SetCover 알고리즘의 근사해의 집합 수가 8개를 초과하지 않는다는 것이다.

부분 배낭 문제 (Fractional Kanpsack Problem)

• 배낭 문제

  • n개의 물건이 각 무게와 가치를 가지고 있을 때, 한정된 용량의 배낭에 최대의 가치를 갖도록 넣는 방법에 대한 문제이다.

• 부분 배낭 문제는 물건을 부분적으로 담는 것이 허용된다.

알고리즘

• 물건을 부분적으로 담을 수 있으므로, 단위 무게당 가치가 제일 높은 것부터 배낭에 넣는다.

  • 만약 통째로 넣을 수 없다면, 넣을 수 있는 만큼만 부분적으로 넣는다.

• 입력으로 각 물건의 무게와 가치, 배낭의 용량을 받는다.

• 출력은 배낭에 담은 물건 리스트와 배낭에 담은 가치의 총합이다.

  Pseudo Code

  FractionalKnapsack(Item *arr, int capacity)
  {
    각 물건의 단위 무게당 가치를 계산한다.
    단위 무게당 가치를 기준으로 내림차순 정렬하여 저장한다.
    int weight = 0; // 배낭에 담긴 무게
    int value = 0; // 배낭에 담긴 가치의 총합
    Item highest = 단위 무게당 가치가 가장 큰 물건;
    Item *list; // 배낭에 담긴 물건의 리스트
    while (weight + highest.weight <= capacity)
    {
      highest를 list에 추가한다.
      weight += highest.weight;
      value += highest.value;
      highest를 arr에서 제거한다.
      새로운 highest를 선정한다.
    }
    if (capacity > weight)
    {
      highest를 (capacity - weight)만큼만 list에 추가한다.
      value += capacity - weight;
    }
    return list, value;
  }

시간 복잡도

• 각 물건의 단위 무게당 가치를 계산할 때 O(n) 시간이 걸린다.

• 정렬할 때 O(nlogn) 시간이 걸린다.

• 반복문에서 최대 O(n) 시간이 걸린다.

• 따라서 시간 복잡도는 O(nlogn)이다.

0-1 배낭 문제

• 부분 배낭 문제의 원형이다.

• 0/1 배낭 문제라고도 표기한다.

  • 0은 물건을 배낭에 넣지 않는다는 뜻이고, 1은 넣는다는 뜻이다.

• 그리디 알고리즘으로 해결할 수 없고, 다음 알고리즘들로 해결 가능하다.

  • 동적 계획(Dynamic Programming) 알고리즘

  • 백트래킹(Backtracking) 기법

  • 분기 한정(Branch-and-Bound)

최단 경로 찾기(Shortest Path)

• 가중치 그래프의 어느 한 출발점에서 도착점까지의 최단 경로를 찾는 문제이다.

• 대표적으로 다익스트라 최단 경로 알고리즘이 있다.

다익스트라(Dijkstra) 최단 경로 알고리즘

• 프림의 최소 신장 트리(MST) 알고리즘과 비슷하다.

• 주어진 출발점에서부터 최단 거리인 점을 하나씩 확정해가며 각 점까지의 최단 거리를 점차 업데이트하는 방식이다.

• 입력으로 주어지는 그래프에는 각 점과 선분에 대한 정보가 있다고 가정한다.

  Pseudo Code

  ShortestPath(Graph g, Node start)
  {
    int dist[n];  // 최단 거리를 저장한 배열
    dist[start] = 0;
    start를 제외한 나머지는 inf로 초기화시킨다.
    while (최단 거리가 확정되지 않은 점이 있다면)
    {
      start로부터 최단 거리가 확정되지 않은 점들 중 최소 거리인 점 v_min에 대해 dist[v_min]을 확정시킨다.
      start로부터 v_min을 통해 갈 수 있는 각 점 w에 대해 dist[w]를 갱신한다.
    }
    return dist;
  }

  

시간 복잡도

• 반복문이 (n - 1)번 반복되고, dist 배열에서 v_min을 찾을 때 O(n) 시간이 걸리므로 시간 복잡도는 O(n²)이다.

최소 신장 트리(Minimum Spanning Tree)

• 가중치 그래프에서, 사이클 없이 모든 점을 연결시킨 트리들 중에 가중치 합이 최소인 트리를 의미한다.

• 그래프의 점의 수가 n이면, 신장트리에는 (n - 1)개의 선분이 존재한다.

  • n개 이상의 선분이 존재할 경우 사이클이 생기고, 이는 트리라고 할 수 없다.

• 대표적인 그리디 알고리즘으로 크러스컬(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 존재한다.

  • 입력으로 받는 그래프 G에는 점의 집합 V와 선분 집합 E에 대한 정보가 포함되어 있다.

  • 점의 개수를 n, 선분의 개수를 m이라고 가정한다.

크러스컬(Kruskal) 알고리즘

• 최소 가중치를 가진 선분을 하나씩 뽑아서, 트리에 사이클을 형성하지 않는지 검사하고 추가하는 방식이다.

  Pseudo Code

  KruskalMST(Graph g)
  {
    가중치의 오름차순으로 선분들을 정렬하여 L에 저장한다.
    Tree t;
    while (t의 선분 수 < (점의 개수 n) - 1)
    {
      선분 e = 가장 작은 가중치를 가진 선분을 가져오고 L에서 제거한다.
      if (선분 e가 사이클을 형성하지 않으면)
        선분 e와 그를 구성하는 점들을 T에 추가시킨다.
    }
    return t;
  }

시간복잡도

• 선분들을 정렬하는 데에 걸리는 시간은 O(mlogm)이다.

• 반복문은 최대 m번 수행되고, 각각의 루프 내에서 선분이 사이클을 형성하는지 검사하는데 O(log*m) 시간이 걸리므로 반복문에서는 총 O(mlog*m)의 시간이 걸린다.

  • log*m은 반복 로그를 의미하는데, 굉장히 느리게 증가하는 함수이다.

  • 참고 : https://ko.wikipedia.org/wiki/%EB%B0%98%EB%B3%B5_%EB%A1%9C%EA%B7%B8

• 따라서 크러스컬 알고리즘의 시간 복잡도는 O(mlogm)이다.

프림(Prim) 알고리즘

• 최소 가중치의 점을 트리에 포함시키며 계속해서 점과 점 사이의 가중치를 업데이트하는 방식이다.

  Pseudo Code

  PrimMST(Graph g)
  {
    최소 가중치를 저장해둘 배열을 D로 설정하고, 임의의 점 p를 골라서 D[p] = 0로 놓는다.
    for (점 p가 아닌 각 점 v에 대하여)
    {
      if (p와 v를 잇는 선분이 있으면)
        D[v] = 선분(p, v)의 가중치
      else
        D[v] = inf
    }
    Tree t = { p };
    while (t.size() < n)
    {
      트리 t에 속하지 않은 각 점 v들에 대하여, D[v]가 최소인 v_min을 선분과 함께 t에 추가한다.
      for (트리 t에 속하지 않은 각 점 w에 대하여)
      {
        D[w] = min(선분(v_min, w)의 가중치, D[w]);
      }
    }
    return t;
  }

  

  ---

시간복잡도

• while 루프가 (n - 1)번 반복되고, 각 루프 내에서 D[v]가 최소인 점 v_min을 찾을 때 O(n) 시간이 걸리므로 시간복잡도는 O(n²)이다.

  • 단, 배열 D를 힙 자료구조로 구현하면 시간 복잡도는 O(mlogn)이 될 수 있다고 한다.

크러스컬과 프림 알고리즘 비교

• 크러스컬 알고리즘에서는 선분이 하나씩 트리에 추가되는데, 이는 n개의 점들이 각각의 트리인 상태에서 점점 하나의 트리로 합쳐지는 것과 같다.

  • 즉 n개의 트리들이 점차 합쳐져서 1개의 신장 트리를 구성한다.

• 프림 알고리즘에서는 점 1개인 트리에서 시작되어 선분을 하나씩 추가시킨다.

  • 즉 1개의 트리가 자라나서 신장 트리가 된다.

• 알기쉬운 알고리즘(양성봉 저, 생능 출판) 책을 바탕으로 작성한 내용이다.

03. 분할 정복 알고리즘

• 주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘이다.

• 분할된 입력의 문제(부분문제, Subproblem)에 대해 동일한 알고리즘을 적용하여 부분해를 얻으며, 이를 취합해서 원래 문제의 해를 얻는다.

  • 더 이상 분할할 수 없을 때까지 계속 부분문제로 분할한다.

• 문제 : 크기가 n인 입력을 3개로 분할하고, 각각 분할된 부분문제의 크기가 n/2이라고 할 때, 총 몇 번 분할하여야 더 이상 분할할 수 없는 크기인 1이 될까?

  • 총 분할 횟수를 k라고 하면, n/2^k = 1이므로 k는 log₂n이 된다.

분할 정복 알고리즘의 분류

• 문제가 a개로 분할되고, 부분문제의 크기가 1/b로 감소하는 알고리즘

  a	b	알고리즘
  2	2	합병 정렬(3.1절), 최근접 점의 쌍 찾기(3.4절), 공제선 문제(연습문제 25번)
  3	2	큰 정수의 곱셈(연습문제 21)
  4	2	큰 정수의 곱셈(연습문제 20)
  7	2	스트라센의 행렬 곱셈(연습문제 22)

• 문제가 2개로 분할되고, 부분문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘

  • 퀵 정렬(3.2절)

• 문제가 2개로 분할되나, 그중에 1개의 부분문제는 고려할 필요가 없고 부분문제의 크기가 1/2로 감소하는 알고리즘

  • 이진탐색(1.2절)

• 문제가 2개로 분할되나, 그중에 1개의 부분문제는 고려할 필요가 없고 부분문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘

  • 선택 문제 알고리즘(3.3절)

• 부분문제의 크기가 1, 2개씩 감소하는 알고리즘

  • 삽입 정렬(6.3절)

  • 피보나치 수의 계산(3.5절)

3.1 합병 정렬 (Merge Sort)

3.2 퀵 정렬 (Quick Sort)

3.3 선택 문제 (Selection Problem)

3.4 최근접 점의 쌍 찾기(Closest Pair)

3.5 분할 정복을 적용하는 데 있어서 주의할 점

• 만약 분할될 때마다 분할된 부분문제의 입력 크기의 합이 기존의 입력 크기보다 매우 커진다면 분할 정복 알고리즘을 적용하는게 부적절할 수 있다.

  • 예를 들어 n번째 피보나치 수를 구할 때 재귀 호출을 사용하면, 분할 후 입력 크기가 거의 2배씩 늘어나므로 반복문을 사용하는게 효율적이다.

• 분할 뿐만 아니라 취합 과정에도 신경을 써야 효율적인 알고리즘이 탄생한다.

선택 문제 (Selection Problem)

• n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제이다.

• 간단한 해결 방법

  • 최소인 숫자들 찾아서 제거하는 방법을 k번 반복한다.

    • 최악의 경우 시간 복잡도 : O(kn)

  • 오름차순으로 정렬한 뒤 k번째 숫자를 찾는다.

    • 최악의 경우 시간 복잡도 : O(nlogn)

  • 간단하지만 비효율적이다.

• 이진 탐색과 퀵 정렬을 섞으면 원하는 숫자를 효율적으로 찾을 수 있다.

• 데이터 분석에서 중앙값(median)을 찾는 데 활용된다.

아이디어

• 퀵 정렬에서 처럼 피벗을 정하고 피벗보다 작은건 왼쪽, 피벗보다 큰건 오른쪽에 위치하도록 정렬한다.

• 작은 그룹의 크기와 큰 그룹의 크기는 피벗의 인덱스를 통해 알 수 있다.

• 분할

  • 찾고자하는 k번째로 작은 숫자가 피벗인 경우 그대로 반환한다.

  • 찾고자하는 k번째로 작은 숫자가 작은 그룹에 있을 경우, 작은 그룹에서 k번째 작은 숫자를 찾는다.

  • 찾고자하는 k번째로 작은 숫자가 큰 그룹에 있을 경우, 큰 그룹에서 (k - (작은 그룹의 크기 + 1))번째로 작은 수를 찾는다.

• 2개의 부분문제로 나눠지지만, 그중에 1개만 고려하면 되고, 부분문제의 크기가 일정하지 않은 크기로 감소하는 형태이다.

  pseudo code

  int Selection(int* arr, int left, int right, int k)
  {
    피벗을 선택하고 arr[left]와 자리를 바꾼다.
    피벗보다 작은 숫자는 arr[left] ~ arr[p - 1]로 이동한다.
    피벗보다 큰 숫자는 arr[p + 1] ~ arr[right]로 이동한다.
    피벗은 arr[p]에 위치시킨다. 여기서의 p는 위의 과정이 끝난 후 피벗보다 작은 그룹의 가장 오른쪽 인덱스이다.
    small_group_size = p - left;
    if (k <= small_group_size) return Selection(arr, left, p - 1, k);
    else if (k == small_group_size + 1) return arr[p];
    else return Selection(arr, p + 1, right, k - (small_group_size + 1));
  }

  

시간복잡도

• 피벗을 정할 때 완벽하게 절반으로 나누는 분할은 불가능하다.

• 시간 복잡도 계산을 위해 다음과 같은 조건을 설정했다.

  • 분할했을 때 큰 쪽의 크기가 입력 크기의 3/4 이상일 경우 bad 분할, 이하인 경우 good 분할이라고 정의한다.

• 분할했을 때 good 분할이 될 확률은 1/2이다.

  • 평균 2회 연속해서 랜덤하게 피벗을 정하면 good 분할이 한번 나오는 것이다.

• 따라서 평균 경우 시간 복잡도를 구하려면, 연속으로 good 분할이 됐다고 가정한 다음 해당 시간 복잡도에 2를 곱하면 되는 것이다.

• 시간 복잡도를 구하는 과정은 다음과 같다.

  • 1번째 분할

    • 입력의 크기가 n일 때 두 그룹을 분할하는 데 걸리는 시간은 O(n)이다.

    • 분할 후 큰 부분의 최대 크기는 (3n - 1)/4 인데, 편의상 (3/4)n 이라고 생각한다.

  • 2번째 분할

    • 큰 부분의 입력 크기가 3n/4이고, 분할 시간은 O(3n/4)이다.

    • 분할 후 큰 부분의 최대 크기는 (3/4)²n이다.

  • 이를 반복하면 시간 복잡도는 다음과 같다.

    O(n + (3/4)n + (3/4)²n + ... + (3/4)ⁱn) = O(n)

  • 여기에 2를 곱한 평균 경우 시간 복잡도는 O(n)이다.

코드

#include <iostream>
#include <vector>

void PrintArr(const std::vector<int>& arr)
{
    for (const auto &e : arr)
        std::cout << e << ' ';
    std::cout << std::endl;
}

int Selection(std::vector<int>& arr, int left, int right, int k)
{
    if (left == right)
        return (arr[left]);

    int    pivot = (left + right) / 2;
    int    high = left + 1;
    int    low = right;

    std::swap(arr[pivot], arr[left]);
    while (high <= low)
    {
        while ((high <= right) && (arr[high] <= arr[left]))
            high++;
        while ((low >= left) && (arr[low] >= arr[left]))
            low--;
        if (high > low)
            break;
        std::swap(arr[low], arr[high]);
    }
    std::swap(arr[left], arr[low]);

    int small_group_size = low - left;
    if (k <= small_group_size)
        return Selection(arr, left, low - 1, k);
    else if (k == small_group_size + 1)
        return (arr[low]);
    else
        return Selection(arr, low + 1, right, k - (small_group_size + 1));
}

int main()
{
    using namespace std;

    vector<int> arr{ 6, 3, 11, 9, 12, 2, 8, 15 };
    int k = 7;

    PrintArr(arr);
    cout << k << "th number : " << Selection(arr, 0, arr.size() - 1, k) << endl;
}

/* stdout
6 3 11 9 12 2 8 15 
7th number : 12
*/

퀵 정렬 (Quick Sort)

• 분할 정복 알고리즘이지만 사실은 정복하고 분할한다.

• 입력의 크기가 클 경우 가장 좋은 성능을 보이는 정렬 알고리즘이다.

  • 생물 정보 공학(Bioinformatics)에서 특정 유전자를 찾을 때 접미 배열(Suffix Array)와 함께 사용된다고 한다.

• 피벗(pivot) 숫자를 기준으로 피벗보다 작은 숫자를 왼쪽으로, 큰 숫자를 오른쪽으로 이동시킨 다음 피벗을 사이에 놓고 분할하는 방식이다.

  • 피벗은 부분문제에 포함되지 않는다.

  pseudo code

  QuickSort(int *arr, int left, int right)
  {
    if (left < right)
    {
      피벗을 arr[left] ~ arr[right] 중에 선택한다.
      피벗을 arr[left]와 자리를 바꾼다.
      피벗보다 작은 숫자의 인덱스를 low, 피벗보다 큰 숫자의 인덱스를 high라고 하자.
        low = right, high = left + 1부터 시작하여 가운데쪽으로 이동하며 검사한다.
      arr[low]와 arr[high]를 비교하여 작은 수는 arr[left + 1] ~ arr[p]로, 큰 숫자는 arr[p + 1] ~ arr[right]로 서로 맞교환해가며 진행한다.
      low < high일 때는 정복이 끝난 것이므로 arr[left]와 arr[low]의 값을 바꾼 뒤 분할한다.
      QuickSort(arr, left, p - 1);
      QuickSort(arr, p + 1, right);
    }
  }

  • 11, 9, 2, 12, 8, 15, 18, 10의 정렬 예제

    • 피벗을 (right - left) / 2로 잡았다.

    • 먼저 피벗을 맨 왼쪽의 값과 바꾼다.

    • 반복문

      • high는 left + 1부터 시작하여 피벗의 값보다 큰 값이 나올 때까지 우측으로 이동한다.

        • 피벗의 값과 같은 값은 패스하는데, 이는 부분문제에서 해결 가능하기 때문이다.

      • low는 right부터 시작하여 피벗의 값보다 작은 값이 나올 때까지 좌측으로 이동한다.

      • 인덱스 low가 high보다 낮으면 정복이 끝났으므로 피벗과 low를 교체하고 부분문제로 분할한다.

      • 그렇지 않으면 low의 값과 high의 값을 바꾼다.

      

시간 복잡도

• 최악 경우 시간 복잡도는 O(n²)이다.

  • 예를 들면 피벗이 계속해서 가장 작은 값만 선택될 경우, 부분문제로 들어가도 입력의 크기만 1씩 줄어들 뿐 문제가 분할되지 않는다.

  • 입력의 크기가 n일 때 비교하는 횟수를 보면 (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1) / 2 = O(n²) 이다.

• 최선의 경우 시간 복잡도는 O(nlog₂n)이다.

  • 피벗이 계속해서 입력의 중앙값으로 선택되면, 항상 1/2로 분할되고 층마다 n번씩 비교를 하게된다.

  • 총 비교 횟수 = 층 수 * 각 층마다의 비교 횟수 = log₂n * O(n) = O(nlog₂n)

피벗 선정 방법

• 랜덤하게 선정하는 방법

• 3 숫자의 중앙값으로 선정하는 방법

  • 가장 왼쪽, 중앙, 가장 오른쪽의 값 중에 2번째의 값으로 피벗을 설정한다.

성능 관련 팁

• 입력의 크기가 매우 클 경우, 삽입 정렬을 같이 사용한다.

  • 입력의 크기가 작으면 퀵 정렬은 재귀 호출이기에 삽입 정렬보다 느리므로, 이 점을 보완한다.

코드

#include <iostream>
#include <vector>

void PrintArr(const std::vector<int>& arr)
{
    for (auto& e : arr)
        std::cout << e << ' ';
    std::cout << std::endl;
}

void QuickSort(std::vector<int>& arr, int left, int right)
{
    if (left >= right)
        return ;

    int    pivot = (left + right) / 2;
    int    high = left + 1;
    int    low = right;

    std::swap(arr[pivot], arr[left]);
    while (high <= low)
    {
        while ((high <= right) && (arr[high] <= arr[left]))
            high++;
        while ((low > left) && (arr[low] >= arr[left]))
            low--;
        if ((high > right) || (low == left) || (high >= low))
            break;
        std::swap(arr[high], arr[low]);
    }
    std::swap(arr[left], arr[low]);

    QuickSort(arr, left, low - 1);
    QuickSort(arr, low + 1, right);
}

int main()
{
    std::vector<int> arr{ 11, 9, 2, 12, 8, 15, 18, 10 };

    PrintArr(arr);
    QuickSort(arr, 0, arr.size() - 1);
    PrintArr(arr);
}

합병 정렬 (Merge Sort)

• 입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소하는 분할 정복 알고리즘

• 연결 리스트에 있는 데이터를 정렬할 때 퀵 정렬이나 힙 정렬보다 훨씬 효율적이라고 한다.

  pseudo code

  MergeSort(int arr[], int p, int q)
  {
    if (p < q)
    {
      int k = (p + q) / 2;
      MergeSort(arr, p, k);
      MergeSort(arr, k + 1, q);
      arr[p] ~ arr[k]와 arr[k + 1] ~ arr[q]를 합병한다.
    }
  }

  

시간 복잡도

• 분할하는 부분

  • 배열의 중간 인덱스 계산과 재귀 호출 2번으로 O(1) 시간이 걸린다.

• 합병하는 부분

  • 두 정렬된 배열 A, B의 크기가 각각 n과 m이고 이를 합병하여 새로운 배열 C를 만드는 부분

    • (n + m - 1)번의 비교를 통해 배열 C를 채우므로 시간 복잡도는 O(n + m)이다.

  • 층 별 비교

    • 각 층에서 수행되는 비교 횟수는 분할된 크기 * 분할된 개수로, 항상 O(n)이다.

    • 층 수는 log₂n이다.

    • 즉, 모든 층에서 수행되는 비교 횟수는 O(nlog₂n)이다.

  • 각 층에서 비교 후에 새로운 배열로 이동시키는 과정의 시간복잡도는 O(nlog₂n)이다.

• 모두 더하면 O(nlog₂n)이다.

공간 복잡도

• 입력과 같은 크기의 공간이 별도로 필요하므로 O(n)이다.

C++ 코드

#include <iostream>
#include <vector>

void PrintElements(const std::vector<int>& arr)
{
    for (const auto& e : arr)
        std::cout << e << " ";
    std::cout << std::endl;
}

void Merge(std::vector<int>& arr, int low, int mid, int high)
{
    int i = low;
    int j = mid + 1;
    int temp_idx = low;
    static std::vector<int> temp(arr);

    while ((i <= mid) && (j <= high))
    {
        if (arr[i] < arr[j])
            temp[temp_idx++] = arr[i++];
        else
            temp[temp_idx++] = arr[j++];
    }
    while (i <= mid)
        temp[temp_idx++] = arr[i++];
    while (j <= high)
        temp[temp_idx++] = arr[j++];

    while (low <= high)
    {
        arr[low] = temp[low];
        low++;
    }
}

void MergeSort(std::vector<int>& arr, int low, int high)
{
    if (low == high)
        return ;

    int mid = (low + high) / 2;

    MergeSort(arr, low, mid);
    MergeSort(arr, mid + 1, high);
    Merge(arr, low, mid, high);
}

int main()
{
    using namespace std;

    vector<int> arr = { 37, 10, 22, 30, 35, 13, 25, 24 };

    PrintElements(arr);
    MergeSort(arr, 0, arr.size() - 1);
    PrintElements(arr);
}

/* stdout
37 10 22 30 35 13 25 24 
10 13 22 24 25 30 35 37
*/

참고

• 알기쉬운 알고리즘 (양성봉 저, 생능 출판)

• 알기쉬운 알고리즘(양성봉 저, 생능 출판) 책을 바탕으로 작성한 내용이다.

02. 알고리즘을 배우기 위한 준비

2.1 알고리즘이란

• 유래 : 페르시아 수학자인 알콰리즈미(al-Khwarizmi)(서기 780~850년)

• 알고리즘은 문제를 해결하는 단계적 절차 또는 방법이다.

  • 이는 컴퓨터로 해결할 수 있어야 하며 입력과 출력이 존재한다.

• 알고리즘의 일반적인 특성

  • 정확성

    • 주어진 입력에 대해 올바른 해를 준다.

  • 수행성

    • 컴퓨터에서 수행이 가능해야 한다. (애매모호한 표현이 없어야 한다.)

  • 유한성

    • 현실적인 시간 내로 종료되어야 한다.

  • 효율성

    • 시간적, 공간적인 효율성을 최대한 고려해야 한다.

2.2 최초의 알고리즘

• 기원전 300년경에 만들어진 유클리드(Euclid)의 최대공약수를 찾는 알고리즘이 최초이다.

• 유클리드의 최대공약수 알고리즘

  a >= b >= 0 일 때,

  pseudo code

  int Euclid(int a, int b)
  {
    if (b == 0) return a;
    return Euclid(b, a mod b);
  }

2.3 알고리즘의 표현 방법

• 알고리즘의 각 단계는 보통 말로 서술할 수 있지만, 일반적으로 의사 코드(pseudo code)로 표현된다.

• 1장의 "1.1 최대 숫자 찾기"의 의사 코드는 다음과 같다.

  pseudo code

  max = Array[0]
  for i = 1 to 9
    if (Array[i] > max) max = Array[i]
  return max

• 이외에도 플로우차트(flow chart) 형태로 표현하기도 한다.

2.4 알고리즘의 분류

• 알고리즘은 문제의 해결 방식에 따라 대략 다음과 같이 분류된다.

  • 분할 정복(Divide-and-Conquer) - 3장

  • 그리디(Greedy) - 4장

  • 동적 계획(Dynamikc Programming) - 5장

  • 근사(Approximation) - 8장

  • 백트래킹(Backtracking) - 9장

  • 분기 한정(Branch-and-Bound) - 9장

  • 랜덤(Random)

  • 병렬(Parallel)

  • 분산(Distributed)

  • 양자(Quantum)

  • 유전자(Genetic)

• 문제에 기반하여 분류한 알고리즘들

  • 정렬 - 6장

  • 그래프(Graph)

  • 기하(Geometry)

2.5 알고리즘의 효율성 표현

• 일반적으로 시간 복잡도가 알고리즘의 비교 척도로 사용된다.

• 시간 복잡도(Time Complexity)

  • 알고리즘의 수행 시간

    • 실제로 수행되는 시간이 아닌, 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현하는 것이다.

  • 알고리즘의 복잡도를 분석하는 방법은 다음과 같다.

    • 최악 경우 분석(Worst Case Analysis)

      • 어떤 입력이 주어지더라도 넘지 않는 시간을 분석한다.

    • 평균 경우 분석(Average Case Analysis)

      • 입력이 균등 분포(Uniform Distribution)일 경우를 가정하고 분석한다.

    • 최선 경우 분석(Best Case Analysis)

      • 최적(Optimal) 알고리즘을 고안할 때 참고 자료로 활용된다.

• 공간 복잡도(Space Complexity)

  • 알고리즘이 수행되는 동안 사용되는 메모리 공간의 크기

2.6 복잡도의 점근적 표기

점근적 표기(Asymptotic Notation)

• 복잡한 식을 간단히 표현하기 위해 사용되는 표기법

• 일반적으로 빅오 표기법이 사용된다.

• O(Big-Oh) 표기

  • 복잡도의 점근적 상한을 나타낸다.

    • 점근적 상한

      • 단순화된 함수에 임의의 양수를 곱하여 나온 함수가, n이 증가함에 따라 f(n)의 상한이 되는 경우

  • 다항식의 최고 차항만 계수 없이 취하면 된다.

• Ω(Big-Omega) 표기

  • 복잡도의 점근적 하한을 나타낸다.

    • 점근적 하한

      • 단순화된 함수에 임의의 양수를 곱하여 나온 함수가, n이 증가함에 따라 f(n)의 하한이 되는 경우

  • 다항식의 최고 차항만 계수 없이 취하면 된다.

• θ(Theta) 표기

  • 복잡도의 상한과 하한이 동시에 적용되는 경우를 나타낸다.

    • n이 증가함에 따라 복잡도와 동일한 증가율을 가진다는 것을 의미한다.

  • 즉 빅오 표기법과 빅오메가 표기법의 복잡도가 같은 경우 사용한다.

  ---

예제

• 복잡도가 f(n) = 2n²-8n+3 일 때

  • O(n²)

    • 임의의 양수 c를 곱한 cn²은 n이 증가함에 따라 f(n)의 상한이 된다. (예를 들면 c = 5인 경우)

  • Ω(n²)

    • 임의의 양수 c를 곱한 cn²은 n이 증가함에 따라 f(n)의 하한이 된다. (예를 들면 c = 1인 경우)

  • θ(n²)

    • f(n)은 n이 증가함에 따라 n²과 동일한 증가율을 가진다.

  ---

자주 사용되는 O 표기

2.7 왜 효율적인 알고리즘이 필요한가?

• 입력 크기가 커질 수록 수행 시간의 차이가 엄청나며, 하드웨어 기술 개발보다는 효율적인 알고리즘 개발이 훨씬 경제적이다.

보간 탐색(Interpolation Search)

• 이진 탐색이 무조건 가운데를 검사한다는 것을 개선한 방법이다.

• 가장 높은 값과 가장 낮은 값을 통해 인덱스를 보간한다.

• 데이터가 균등하게 분포되어 있는 자료에 사용하기 적합하다.

  data : 데이터의 집합
  low : 가장 낮은 인덱스
  high : 가장 높은 인덱스
  mid : 비교할 값의 인덱스

  mid = low + (high - low) * (value - data[low]) / (data[high] - data[low]) 

  

참고

• https://jackpot53.tistory.com/35

• 알기쉬운 알고리즘(양성봉 저, 생능 출판) 책을 바탕으로 작성한 내용이다.

01. 알고리즘의 첫걸음

• 알고리즘이라는 용어는 9세기경 페르시아 수학자인 알콰리즈미(al-Khwarizmi)의 이름으로 부터 유래되었다.

  • 문제를 해결하기 위한 단계적인 절차를 의미한다.

• 1장에서는 다양한 예시를 보여준다.

1.1 최대 숫자 찾기

문제 : 카드 10장 중에서 가장 큰 숫자 찾기

알고리즘 : 순차 탐색(Sequential Search) == 선형 탐색(Linear Search)

• 카드를 한 장씩 차례대로 읽어가며 찾는 방식

1.2 임의의 숫자 찾기

문제1 : 45, 20, 60, 35, 10, 55, 90, 85, 75, 25가 적힌 카드 중에 85가 적힌 카드 찾기

• 알고리즘 : 순차 탐색

• 최대 숫자 찾기처럼 85를 기억하고 카드를 하나씩 읽으며 해당 숫자를 찾는 방식

문제2 : 위와 같은 카드가 오름차순으로 정렬되어 있을 때, 효율적으로 85가 적힌 카드를 찾기

• 알고리즘 : 이진 탐색(Binary Search)

• 중간의 카드를 읽어 85와 비교하고 85가 앞 부분에 있는지 뒷 부분에 있는지 판단하여, 반으로 나눠가면서 찾아가는 방식

• 분할 정복(Divide-and-Conquer) 알고리즘의 일종이다.

1.3 동전 거스름돈

문제 : 730원을 거슬러 받을 때, 가장 적은 수의 동전으로 받는 방법

• 알고리즘 : 그리디(Greedy) 알고리즘

• 남은 거스름돈 액수를 넘지 않는 한도에서 가장 큰 액면의 동전을 계속하여 선택하는 방식

1.4 한붓그리기

문제 : 한붓그리기의 해결 방법

• 알고리즘 : 현재 점으로부터 진행하고자 하는 점을 지나서 현재 점으로 돌아오는 사이클을 찾는다.

• 오일러 서킷(Euler Circuit) 문제와 같다.

1.5 미로 찾기

문제 : 미로에 갇혔을 때 따로 표시를 할 수 없는 상황에서 빠져나오는 방법

• 알고리즘 : 한 방향을 선택하여, 벽에 오른손을 대고 출구가 나올 때까지 손을 떼지 않고 걸어간다.

1.6 가짜 동전 찾기

문제 : 동전 더미 속에 1개의 가벼운 가짜 동전이 섞여있을 때, 이를 찾아낼 수 있는 최소한의 양팔 저울 사용 횟수 찾기

• 알고리즘 : 더미를 반으로 나누어 저울에 달고, 가벼운 쪽의 더미를 계속 반으로 나누어 저울에 달아 찾아낸다.

1.7 독이 든 술단지

문제 : 많은 술단지 중에 눈으로 확인할 수 없는 독이 든 단지가 하나 있다. 독이 들었는지 판단하는 방법은 오직 술을 마신 사람이 일주일 후에 죽는다는 것 밖에 없을 때, 죽는 사람을 최소화하며 일주일만에 독이 든 단지를 찾아내는 방법

• 알고리즘 : 술단지를 차례로 2진법으로 표기하고, 각 비트를 사람으로 생각한다. n개의 단지가 있으면 최대 log₂n명의 사람만 죽는다.

보간 탐색(Interpolation Search)