Unique Life

출처:http://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Divide-and-Conquer-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5

분할정복

정의 : 분할정복 알고리즘은 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘이다.

알고리즘을 설계하는 요령

(1) Divide : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다.

(2) Conquer : 나누어진 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 푼다.

(3) Combine : Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다.

• 문제를 제대로 나누면 Conquer하는 것은 쉽기 때문에 Divide를 제대로 하는 것이 가장 중요하다.
• 분할정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할정복 알고리즘의 효율성을 깎아내릴 수 있다.

분할정복의 응용

1. 병합 정렬 (Merge Sort)

헝가리 출신 미국인 수학자인 존 폰 노이만이 1945년에 개발한 알고리즘이다. 시간복잡도는 이고, 공간복잡도는 이다.

알고리즘

1. 정렬할 데이터 집합의 크기가 0또는 1이면 이미 정렬된 것으로 보고, 그렇지 않으면

2. 데이터 집합을 반으로 나눈다.

3. 원래 같은 집합에서 나뉘어져 나온 데이터 집합 둘을 병합하여 하나의 데이터 집합으로 만든다. 단, 병합할 때 데이터 집합의 원소는 순서에 맞춰 정렬한다.

4. 데이터 집합이 다시 하나가 될 때까지 3을 반복한다.

예를 들어 다음과 같은 데이터 집합이 있다고 해보자.

알고리즘의 1~2 과정을 반복하여 나눈다. 색칠한 부분은 나눈 기준이 되는 부분이다.

분할을 했으니 정복을 할 차례다. 3~4과정을 반복해서 수행한다.

조각난 데이터 집합을 정렬해가면서 병합하면 결국 완전히 정렬된 하나의 데이터 집합을 얻는 알고리즘이다.

그런데 병합이 어떻게 정렬하면서 합칠 수 있는 것일까.

두 데이터 집합을 정렬하면서 합치는 방법

1. 두 데이터 집합의 크기의 합만큼의 크기를 가지는 빈 데이터 집합을 만든다.

2. 두 데이터 집합의 첫 번째 요소들을 비교하여 작은 요소를 빈 데이터 집합에 추가한다. 그리고 새 데이터 집합에 추가한 요소는 원래 데이터 집합에서 삭제한다.

3. 원래 두 데이터 집합의 요소가 모두 삭제될 때 까지 2를 반복한다.

예를 들어 다음과 같은 데이터 집합 A, B와 이 두 데이터 집합의 크기의 합만큼의 크기를 가지는 빈 데이터 집합인 C가 있다고 하자.

두 데이터 집합의 첫 번째 요소를 비교한다. A의 첫 번째 요소는 2, B의 첫번째 요소는 1이므로 B의 것이 더 작다. C에 1을 추가하고 B에서 1을 삭제한다.

그 다음 A의 2와 B의 3을 비교한다. 2가 작으니 C에 2를 추가하고 A에서 2를 삭제한다.

A의 5와 B의 3을 비교한다. 3이 작으니 C에 3을 추가하고 B에서 3을 삭제한다.

이렇게 데이터 A와 B의 요소들을 비교해서 C에 넣고 A와 B의 각 요소들을 삭제해나가다보면, A에 9하나만 남게된다. B에는 비교할 요소가 남아 있지 않으므로 그냥 9를 C에 추가하고 A에서 9를 삭제한다. 이로써 A와 B의 요소들이 모두 삭제되었고 C는 정렬된 데이터 집합이 되었다.

2. 거듭 제곱 (Exponentiation)

n거듭 제곱은 자신을 n번 곱해야 함으로 의 시간이 소요된다. 이것을 개선하기 위해서 연산방법을 조금 바꾸어보자.

은 다음과 같이 정의되지만,

다음과 같이 표현할 수도 있다.

을 구할 때 C를 8번 곱하지 않고 를 구한 뒤 제곱을 두 번 더 반복하면 결국 세번의 연산만으로 같은 결과를 얻을 수 있다.

지수가 짝수일때는 지수를 반으로 나눠서 곱한다.

지수가 홀수일때는 지수에서 1을 빼고 반으로 나누어서 곱하고 밑을 한번 더 곱하면 된다.

이렇게 지수를 반으로 나눠가는 거듭 제곱 알고리즘의 수행 시간은 이다.

3. 피보나치 수열 (Fibonacci Sequence)

피보나치 수열은 다음과 같이 정의된다.

이 알고리즘으로는 걸리는 시간은 이다.

연산을 줄이기 위해 2차 정사각행렬을 이용한다.

 이므로 n제곱을 하게 되면

  이렇게 거듭제곱 알고리즘때와 비슷하게 나타낼 수 있다.

수행 시간 또한 거듭 제곱 알고리즘과 똑같은 이 걸리게 된다.

출처: http://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Greedy-Algorithm-%ED%83%90%EC%9A%95-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

탐욕 알고리즘

정의 : 미리 정한 기준에 따라서 매번 가장 좋아 보이는 답을 선택하는 알고리즘

동적 계획법과 마찬가지로 최적화 문제를 푸는데 사용한다.

근시안적으로 해를 구할 당시에 가장 최적인 해를 구한다.

탐욕 알고리즘은 동적 계획법보다 효율적이긴 하지만 동적 계획법처럼 반드시 최적의 해를 구해준다는 보장을 하지 못한다.

알고리즘

1. 해 선택 (Selection Procedure) : 지금 당시에 가장 최적인 해를 구한뒤, 이를 부분해 집합에 추가한다.

2. 적절성 검사 (Feasibility Check) : 새로운 부분해 집합이 적절한지 검사한다.

3. 해 검사 (Solution Check) : 새로운 부분해 집합이 문제의 해가 되는지 검사한다. 아직 문제의 해가 완성되지 않았다면 1번부터 다시 시작한다.

탐욕 알고리즘의 활용

1. 최소수의 동전으로 거스름돈 거슬러주기

편의점같은 곳에서 돈을 거슬러 줄 때에는 서비스 차원에서 최소한의 동전 개수로 돈을 거슬러 주는 게 좋다. 거스름돈이 550원인데 50원짜리 동전을 11개 주면 받는 손님은 불쾌할 것이 분명하다. 이 문제의 해는 거슬러 줄 총액에 해당하는 동전의 집합이고, 최적해는 동전의 개수가 최소가 되는 집합이다.

알고리즘

1. 해 선택 (Selection Procedure) : 가장 가치가 높은 동전을 우선으로 거스름돈을 구성하면 동전의 개수가 줄어들테니, 현재 고를 수 있는 가장 가치가 높은 동전을 골라서 부분해 집합에 추가한다.

2. 적절성 검사 (Feasibility Check) : 부분해 집합이 거슬러 줄 금액을 초과하는지 검사한다. 초과한다면 가장 최근에 추가한 동전을 삭제하고, 1로 돌아가서 현재보다 한 단계 작은 동전을 추가한다.

3. 해 검사 (Solution Check) : 부분해 집합이 거슬러 줄 금액과 일치하는지 검사한다. 액수가 모자라면 다시 1로 돌아가서 부분해 집합에 추가한 동전을 고른다.

이렇게 만든 알고리즘은 꽤 쓸만해 보인다. 하지만 항상 최적의 해를 구해주는 것은 아니다. 대부분의 국가에서 사용하는 화폐들의 단위는 이 알고리즘이 항상 최적의 해를 구할 수 있도록 되어있다. 우리나라의 동전은 500원, 100원, 50원, 10원 이렇게 네가지가 있다. 이 중 아무것이나 두 개를 골라서 최대공약수를 구하면 항상 작은 값의 동전 단위가 나온다. 예를 들어 500과 50의 최대 공약수는 50이고, 100과 10의 최대 공약수는 10이다.

이런 시스템에서는 가장 최소수의 동전으로 이루어진 거스름돈을 만들기가 쉽다. 예를 들어 물건금액이 3,800원이고 손님이 5,000원을 지불했다면 500원짜리 두개와 100원짜리 두개를 거슬러 주면 된다. 이것은 위의 알고리즘으로도 같은 결과를 얻을 수 있다.

하지만 여기에 400원짜리 동전이 생긴다면 어떻게 될까. 400은 500과 최대공약수가 100으로 작은 값의 동전 단위가 나오지 않는다. 이 때 거스름돈을 1200원 거슬러 주어야 한다면 400원짜리 동전 3개를 거슬러 주는 것이 가장 최적의 방법이지만, 위의 알고리즘대로라면 500원짜리 2개와 100원짜리 2개를 거슬러주게 될 것이다. 이처럼 탐욕 알고리즘은 항상 최적의 결과를 보장하지는 못한다.

2. 최소비용 신장트리 (Minimum Spanning Trees)

정의 : 그래프 내의 모든 정점을 최소의 비용으로 연결하는 트리

다음과 같은 그래프가 있다고 하면

최소비용 신장트리는 다음과 같을 수 있다.

최소비용 신장트리를 만드는 알고리즘에는 프림 알고리즘, 크루스칼 알고리즘 크게 두가지가 있다. 일단은 크루스칼 알고리즘만 다뤄보기로 한다.

크루스칼 알고리즘

1. 그래프 내의 모든 간선을 가중치의 오름차순으로 목록을 만든다.

2. 1에서 만든 간선의 목록을 차례대로 순회하면서 간선을 최소비용 신장트리에 추가한다. 단, 이때 추가된 간선으로 인해 트리구조가 망가지면 안된다.

탐욕적인 방법으로 처리되는 부분은 2단계이다.

이 부분에서 '해 선택 - 적설성 검사 - 해 검사'의 반복이 이루어진다.

해 검사는 부분해 집합이 하나가 되면 최적해로 판단한다.

위의 그래프로 간선의 가중치의 오름차순 목록을 만들면

C-E(1), A-C(2), E-F(2), B-D(3), C-F(3), D-E(3), D-G(3), A-B(4), B- C(4), F-G(6), A-E(8) 이다.

그리고 먼저 C-E(1)를 추가한다.

트리 구조가 망가지진 않았으니 계속한다.

파란원으로 묶은 정점들과 묶지 않은 개별 정점 하나하나는 부분해 집합들이다.

부분해 집합이 하나가 아니므로 반복한다.

그다음 A-C(2)와 E-F(2)를 추가한다.

트리 구조가 망가지진 않았으니 계속한다.

부분해 집합이 하나가 아니므로 반복한다.

B-D(3), C-F(3), D-E(3), D-G(3)를 추가한다.

C-F(3)은 사이클을 형성하여 트리 구조를 망가뜨리니 삭제한다.

부분해 집합이 하나이므로 종료한다.

3. 다익스트라 알고리즘 (Dijkstra's Algorithm)

정의 : 그래프 내의 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘

예를 들면 다음과 같은 그래프가 있다고 하면 최소한의 비용으로 A에서 G까지 가는 방법을 찾는 것이다.

알고리즘

1. 각 정점 위에 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 정의하고 모든 정점 위에 있는 경로의 길이를 (무한대)로 초기화한다.

2. 시작 정점의 길이를 0으로 초기화하고 최단 경로에 추가한다.

3. 최단 경로에 새로 추가된 정점의 인접 정점들에 대해 경로 길이를 갱신하고 이들을 최단 경로에 추가한다. 만약 추가하려는 인접 정점이 이미 최단 경로위에 있는 정점이라면 갱신할려는 경로의 길이가 더 짧은 경우에만 기존의 경로를 현재 정점을 경유하게 수정한다.

4. 그래프 내의 모든 정점이 최단 경로에 속할 때까지 3을 반복한다.

탐욕 알고리즘으로 이 알고리즘을 보면 1, 2 단계가 알고리즘의 초기화 단계이고, 3단계는 해 선택과 적절성 검사, 4단계는 해 검사를 맡고있다.

먼저 각 정점에 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 정의하고 모든 정점 위에 있는 경로의 길이를 (무한대)로 초기화한다.

A를 시작 정점이라고 하고 경로 길이를 0으로 초기화하고 최단 경로에 추가한다.

현재 새로 추가한 정점은 A이므로 정점 A에 인접한 정점인 정점 B, C, F를 최단 경로에 추가하고, 각 정점에 이르는 데 드는 비용을 갱신한다.

이미 최단 경로 안에 들어 있는 정점들은 없으므로 적절성 검사는 통과한다. 아직 최단 경로가 완성되진 않았으므로 4의 해 검사는 통과하지 못하므로 3을 반복한다.

새로 추가한 정점이 정점 B, F, C 세가지 이므로 차례차례대로 3을 수행한다.

먼저 B에 대해서 3을 수행한다. 인접 정점은 E 하나 뿐이므로, E를 최단 경로에 추가하고 경로의 길이를 갱신한다. 

적절성 검사는 통과하고, 해 검사는 통과하지 못하므로, 계속해서 C에 대해서 처리한다.

C의 인접 정점은 정점 D, F, G가 있는데 D와 G는 경로 길이가 무한대이므로 적절성 검사를 통과하지만, F는 이미 최단 경로 안에 포함되어 있고, 새로 추가할려는 경로보다 짧으므로 적절성 검사를 통과하지 못한다. 그리고 모든 정점이 최단 경로에 속하므로 해 검사를 통과한다.

하지만 이 해는 최적해가 아니다. A에서 E에 이르는 거리는 B를 거쳐 E로 가는 것보다 F를 거쳐 E로 가는게 더 짧다. 이처럼 탐욕 알고리즘은 항상 최적해를 보장하지 못한다.

하지만 이 알고리즘은 조금 더 개선하여 그래프에 사이클이 존재하지 않는 이상 무조건 최적해를 나오게 할 수 있다. 탐욕 알고리즘의 이점인 실행시간을 조금 포기해야한다.

알고리즘

1. 시작 정점에서 도달가능한 정점들에 대해 경로의 길이를 설정하고, 나머지 정점들까지의 거리는 로 초기화한다.

2. 제일 가까운 경로의 정점을 하나 선택한다.

3. 시작점에서 출발하여 결정된 최단거리 정점들을 제외한 모든 정점들을 경유하여 선택한 점까지 도달하는 거리를 체크한다. 기존의 경로보다 짧을 경우 기존의 경로를 갱신한다.

4. 2~3을 n-1번 반복한다.

같은 그래프에 대해서 다시 이 알고리즘을 수행해보자.

시작 정점에서 도달가능한 정점에 대해 경로의 길이를 설정하고, 나머지 정점들에 대한 거리는 로 초기화 하였다.

B에서 제일 가까운 정점인 E를 선택한다.

E까지 도달 가능한 경로는 A-B-E와 A-F-E이다. A-F-E경로가 더 짧으므로 해당 경로를 선택한다.

B에서 더 이상 선택가능한 정점이 없으므로 다음 정점인 C에서 제일 가까운 점인 D를 선택한다.

D까지 도달 가능한 경로 중 제일 짧은 거리를 선택한다.

A에서 C를 거쳐 F까지 다다르는 거리와 A에서 F로 바로 가는 경로의 길이를 비교하고, 원래 경로가 짧으므로 갱신하지 않는다.

A에서 C를 거쳐 G까지 다다르는 거리와 A에서 G로 바로 가는 경로의 길이를 비교하고, A에서 C를 거쳐 G로 가는 경로의 길이가 짧으므로 경로를 갱신한다.

나머지 정점들에 대해서 계속 진행해주어도 갱신되는 점 없이 이렇게 결정될 것이다.

방금과 달리 최적해가 나왔다.

사이클이 없는 경우 최적해를 보장하지만 이 알고리즘은 무조건 의 시간 복잡도를 가진다.

4. 허프만 코딩 (Huffman Coding)

정의 : 데이터를 압축하는 방법중의 하나로 쓰이는 알고리즘

허프만 코딩을 알기 위해서는 먼저 고정 길이 코드와 접두어 코드를 알아야 한다.

고정 길이 코드(Fixed Length Code)란 말 그대로 모든 코드의 길이가 똑같은 코드의 체계를 말한다. ASCII가 그 대표적인 예로, 모든 코드가 8bit의 길이를 가진다. 코드의 길이가 같으므로 다루기가 쉽지만 쓰지 않는 공간이 생기기 때문에 저장 공간의 낭비가 일어난다. 이를 위해 쓰는 것이 가변 길이 코드(Variable Length Code)이다. 접두어 코드(Prefix Code)는 이 가변 길이 코드의 한 종류이다.

접두어 코드란 코드 집합의 어느 한 코드도 다른 코드의 접두어가 되지 않는 코드를 말한다.예를 들어 {"0", "1", 01", "11"}은 접두어 코드가 아니다. "0"이 "01"의 접두어가 되고, "1"이 "11"의 접두어가 되기 때문이다. {"00", "01", "11", "101"}은 어느 코드도 다른 코드의 접두어가 되지 않기 때문에 접두어 코드이다.

ASCII와 같은 고정 길이 코드로 이루어진 데이터를 접두어 코드로 변환시켜 데이터를 압축시키는 메커니즘이 바로 허프만 코딩인것이다.

허프만 코딩에서 제일 중요한 요소는 기호의 빈도와 이진 트리이다.

기호의 빈도란 한 기호가 데이터 안에서 얼마나 자주 나오느냐이다. 기호의 빈도는 길이가 짧은 접두어 코드를 빈도가 높은 기호에 부여하기 위해 사용된다. 이렇게 함으로써 그만큼 저장공간을 아낄 수 있다. 예를 들어 어떤 문자열이 'x' 15개와 'y' 4개로 이루어진다고 하고,  'x'라는 코드에 111을, 'y'에 코드 10을 부여한다면, 변환된 데이터의 크기는 3(111의 비트 길이) X 15 + 2(10의 비트 길이) X 4 = 53비트가 된다. 하지만 이와 반대로 'x'에 10을, 'y'에 111을 부여한다면 2(111의 비트 길이) X 15 + 3(10의 비트 길이) X 4 = 42비트가 되어 앞의 방법보다 비트를 절약할 수 있다.

이진 트리는 접두어 코드를 표현하는데 사용된다. 트리의 왼쪽 자식 노드는 0, 오른쪽 자식 노드는 1을 나타낸다. 모든 기호는 잎 노드에만 저장된다. 루트 노드에서 잎 노드까지 이르는 경로가 기호의 접두어 코드가 된다. 이런 방식으로 작성된 이진 트리를 허프만 트리라고 한다. 다음이 그 예이다.

a까지의 경로는 0이고 이것이 a의 접두어 코드가 된다. b까지의 경로는 10이고 이것이 b의 접두어 코드가 된다. c까지의 경로는 11이고 이것이 접두어 코드가 된다.

이러한 원리로 허프만 코딩을 적용시켜보자. 'aabaabbccde'라는 문자열을 압축시켜보자. a의 빈도는 4이고 b의 빈도는 3이고 c는 2, d는 1, e는 1이다. 먼저 기호들을 빈도와 함께 노드를 생성한다.

노드 위의 숫자는 빈도를 나타낸다.

이 노드들은 끝까지 잎 노드로 남아야 함으로 노드들 위에 부모 노드를 생성해 나가면서 이어붙인다.

우선 가장 빈도가 작은 노드 두 개를 선택한다. d, e가 둘 다 빈도가 1이므로 d, e를 선택하고 이 노드들 위에 부모노드를 하나 만들어서 연결한다. 부모 노드의 빈도는 자식 노드의 빈도들의 합인 2가 된다.

모든 잎 노드들이 기호를 가지고 있으므로 적절성 검사는 통과하지만, 허프만 트리가 완성되지는 않았으므로 해 검사는 통과하지 못한다. 그러므로 다시 해 선택으로 돌아간다.

c와 새로 만든 노드(d와 e의 부모 노드)의 빈도가 가장 작으므로 이 두 노드 사이에 부모 노드를 새로 만든다.

적절성 검사는 통과하고, 해 검사는 통과하지 못하므로 다시 해 선택으로 돌아간다.

제일 같은 빈도가 b와 새로 만든 노드이므로 이 두 노드 사이에 부모 노드를 새로 만든다.

적절성 검사는 통과하고, 해 검사는 통과하지 못하므로 다시 해 선택으로 돌아간다.

제일 같은 빈도가 a와 새로 만든 노드이므로 이 두 노드 사이에 부모 노드를 새로 만든다.

적절성 검사를 통과하고, 허프만 트리가 완성되었으므로 해 검사도 통과한다.

이제 이 허프만 트리의 접두어 코드로 데이터를 표현하면 데이터가 압축되는 것이다.

압축 결과는 00100010101101101110111이다. ASCII로 표현하였을때는 88비트이겠지만, 23비트로 압축되었다.

압축을 했으면 압축을 해제하는 방법도 있어야한다.

알고리즘

1. 압축을 위해 만들었던 허프만 트리와, 압축 해제가 된 데이터를 담을 부분을 준비한다.

2. 압축 데이터에 아직 읽지 않은 부분이 있으면 한 비트 읽는다.

3. 읽은 비트가 0이면 왼쪽 자식 노드로, 1이면 오른쪽 자식 노드로 이동한다. 잎 노드에 다다르면 노드에 있는 기호를 데이터에 담고 다시 루트 노드로 이동한다.

앞에서 압축한 00100010101101101110111를 압축 해제 해보겠다.

데이터를 한 비트 읽는다. 0이 나왔으므로 왼쪽 자식 노드로 이동한다. 잎 노드 a가 나왔으니, a를 압축 해제된 데이터에 추가하고 루트 노드로 돌아간다.

그 다음 비트를 읽으니 또 0이 나왔으므로  왼쪽 자식 노드로 이동한다. 잎 노드 a가 나왔으니, a를 압축 해제된 데이터에 추가하고 루트 노드로 돌아간다.

그 다음 비트를 읽으면 1이 나온다. 오른쪽 자식 노드로 이동했는데 잎 노드가 아니므로 그 다음비트를 읽는다. 0이 나왔으므로 왼쪽 자식 노드로 이동한다. 잎 노드 b가 나왔으므로, b를 압축 해제된 데이터에 추가하고 루트 노드로 돌아간다.

같은 방법으로 계속 반복하다보면 데이터를 끝까지 읽고 압축이 완전히 해제된 데이터를 볼 수 있다.

압축 해제된 데이터는 'aabaabbccde'로 압축한 데이터와 같은 문자열을 얻었다.

출처:

※ 읽으시기 전에

- 제가 현재 숙지하고 있는 STL 내용은 대부분 레퍼런스를 참고하지 않고, 직접 이리저리 실험해가며 익힌 내용입니다. 글을 쓸 때는 레퍼런스를 이용하여 검증하지만, 그래도 이론적인 부분에서 제가 틀리게 작성할 수도 있습니다. 따라서 피드백은 언제나 환영입니다.

- 앞으로 소개드릴 자료구조, 함수 등은 반드시 직접 구현할 수 있어야 합니다. 100% 완벽하게 구현할 수 있어도 좋고, 핵심적인 부분만 구현할 수 있어도 좋습니다. 적어도 어떤 원리로 작동하는지는 알아야합니다. 원리를 모른 채 그냥 가져다 쓰는 건 언제 어떤 난관에 부딪칠지 모르기 때문에 상당히 위험합니다. 가져다 쓰는 건 구현이 가능한 이후입니다.

0. qsort 함수와 sort 함수와의 비교

“qsort 함수가 있는데 sort 함수를 굳이 사용할 필요가 있나요?”

  네, 있습니다. 사실 이 질문은 C++를 아직 제대로 접하지 못하였기에 일어나는 질문입니다. C++ 에서는 여러 가지 자료구조가 내장 라이브러리 내에 선언되어 있습니다. C에서는 아직 이러한 자료구조들이 라이브러리에 포함되어 있지 않기 때문에 qsort 함수는 단순히 배열을 기반으로 설계한 함수입니다. 한편 sort 함수는 연속된 주소 값을 가지는 컨테이너라면 (RandomAccessIterator) 무엇이든 정렬이 가능합니다. 게다가 C++ 에서는 함수의 오버로딩 및 템플릿 화가 되어있어서 인자를 적게 받습니다. 즉, 사용이 용이합니다. 

  그리고 하나 더. sort 함수가 qsort 함수보다 수행 시간이 빠릅니다. 분할이 최악으로 일어날 때 부가적으로 처리하는 부분이 다른 것으로 알고 있습니다. (그런데 우리가 흔히 다루는 범위에서는 많아봐야 50ms 정도 차이나는 정도라 크게 신경 쓰시지 않으셔도 됩니다.)

  마지막으로, 참고용으로 stdlib.h 에 선언되어있는 qsort 함수의 원형을 제시하겠습니다. 바로 다음 장에 제시될 sort 함수의 원형과 비교해 보셨으면 합니다.

qsort(void *_Base, size_t_NumOfElements, size_t_SizeOfElements, int (*_PtFuncCompare)(const void *, const void *))

1. sort 함수의 원형 및 사용법

  sort 함수는 algorithm 헤더 파일의 std 네임스페이스 내부에 선언되어있습니다. 함수의 원형은 다음과 같습니다.

template<class RandomAccessIterator>

void sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>

void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

  두 번째 선언은 나중에 다시 설명하니 일단 넘어가고. 첫 번째 선언은 [first,last) 범위에 있는 원소를 오름차순으로 정렬합니다. 여기서 [first,last)란 first에 있는 원소는 포함하고, last에 있는 원소는 제외한다는 의미입니다.

  예를 들어 a[0], a[1], ... a[9]를 오름차순으로 정렬하고 싶으면, std::sort(a,a+10); 라 호출하면 됩니다. 전처리기에 using namespace std; 라 적어두면 std::를 생략할 수 있습니다.

ex)

--- Source --- 

#include<stdio.h>

#include<algorithm>

using namespace std;

int main() {

    int a[]={12,-6,7,903,88,-105,42,27,3,0};

    int size=10;

    sort(a,a+size);

    for(int i=0 ; i<size ; i++)

        printf("%d ", a[i]);

    printf("\n");

    return 0;

}

--- Output --- 

-105 -6 0 3 7 12 27 42 88 903

2. 내림차순 정렬은?

  내림차순 정렬을 위해서는 두 번째 선언을 사용합니다. 두 번째 선언에서 전달받는 인자 중 Compare comp는 비교 함수를 의미합니다. 여기에 functional 헤더 파일에 선언되어있는 greater<자료형>()을 전달하면 내림차순으로 정렬을 수행합니다. 이 비교 함수를 직접 구현하여 인자로 전달하여도 되지만, 여기서는 이미 내장 라이브러리에 선언되어있는 함수를 사용하도록 하겠습니다.

  참고로 less<자료형>()을 전달하면 오름차순으로 정렬을 수행합니다. 이는 첫 번째 선언과 동일한 의미를 가집니다.

ex)

--- Source --- 

#include<stdio.h>

#include<algorithm>

#include<functional>

using namespace std;

int main() {

    int a[]={12,-6,7,903,88,-105,42,27,3,0};

    int size=10;

    sort(a,a+size,greater<int>());

    for(int i=0 ; i<size ; i++)   

        printf("%d ", a[i]);

    printf("\n");

    return 0;

}

--- Output --- 

903 88 42 27 12 7 3 0 –6 –105

3. Compare 함수 전달

  앞서 내림차순 정렬을 위하여 sort 함수 세 번째 인자로 greater<자료형>()를 전달하였습니다. 여기서는 세 번째 인자로 전달되는 Compare 함수가 어떤 형식을 가지고 있어야 하는 지 설명하겠습니다.

  sort 함수의 인자로 전달되는 Compare 함수는, 정렬하고자 하는 자료형을 두 개 받은 후 정렬이 일어나는 방향으로 true를 반환해야 합니다. 무슨 소리냐고요? 예를 들어 int형 데이터를 오름차순으로 정렬하고 싶다면, int형 데이터를 두 개 받은 후 두 번째 인자가 더 크면 true, 더 작으면 false를 반환해야 한다는 것입니다. (여기서 같은 경우는 true나 false 무엇을 반환해도 상관없습니다.)

  부족한 설명을 대신할 예시를 전달하도록 하겠습니다...^^ 2장 내림차순 정렬 때 greater<자료형>() 대신 직접 Compare 함수를 구현하여 대체하였습니다.

ex)

--- Source ---

#include<stdio.h>

#include<algorithm>

using namespace std;

bool cmp(int a, int b) { return a>b; }

int main() {

    int a[]={12,-6,7,903,88,-105,42,27,3,0};

    int size=10;

    sort(a,a+size,cmp);

    for(int i=0 ; i<size ; i++)

        printf("%d ", a[i]);

    printf("\n");

    return 0;

}

--- Output ---

903 88 42 27 12 7 3 0 –6 –105

출처: http://www.aistudy.co.kr/physics/monte_carlo_method.htm

Monte Carlo mothod

Monte Carlo method 는 임의의 수 (random number 또는 pseudo-random number) 를 사용하여 다양한 계산문제를 푸는 알고리즘 으로서 결정적 알고리즘 (deterministic algorithm) 의 반대되는 개념이다. 전산물리 (computational physics) 와 관련 응용분야에서 매우 중요한 방법이며 esoteric quantum chromodynamics calculations 로부터 heat shields and aerodynamic forms 설계 까지 다양한 응용을 갖는다. 이 방법은 radiance field 를 정의하는 적분-미분 방정식들을 푸는데 효율적인 것으로 증명되었고, 따라서 photorealistic images of virtual 3D models 를 만드는 global illumination computations 에 사용되어 왔으며, 비디오게임, 건축, 설계, 컴퓨터제작 필름, 영화의 특수효과, 경영, 경제 등등의 여러분야에 응용되었다.

흥미롭게도 Monte Carlo method 은 진짜 임의의 수를 사용할 필요는 없다. 대부분의 유용한 기술은 deterministic, pseudo-random sequences 를 사용하며 test and re-run simulations 를 쉽게 만든다. 좋은 시뮬레이션을 만드는데 필요한 진짜 중요한 것은 pseudo-random sequence 가 "충분히 임의적인 것으로 (random enough)" 보이게 하는 것이다. 즉 충분히 많은 수의 요소들의 순서가 고려될때 균일 분포 (uniformly distributed) 하거나 다른 바람직한 분포를 따라야 한다는 것이다.

알고리즘의 반복과 많은 수의 계산이 포함되기때문에, Monte Carlo 는 컴퓨터를 사용하여 계산하기에 적당한 방법이며, 컴퓨터 시뮬레이션의 많은 기술을 사용하기에 적당한 방법이다.

Monte Carlo algorithm 은 쉽게 풀리지 않는 수학문제 (많은 변수를 가지는 문제, 예를들면 integral calculus 같은) 의 해를 찾는데 사용하는 numerical Monte Carlo method 를 말한다. 문제의 차원 (dimension) 이 증가할때에 다른 수치적 방법들에 비교해서 Monte Carlo algorithm 의 효율성이 더 증가한다. ............. (Wikipedia : Monte Carlo mothod)

몬테칼로 기법이라 하면 뭐 대단히 어려운 전산과학의 기법인양 생각하게 쉬운데 사실은 간단한 보기를 통하여 그 핵심은 설명할 수 있다.   전산물리라 하면 몬테칼로 기법을 가지고 물리 문제를 푸는 것이라 해도 과언이 아닐 정도로 몬테칼로 기법은 전산물리의 중요 중심과제다.  

내가 내 생애의 절반 이상을  컴퓨터를 써서 이 몬테칼로 방법을 연구하고 개발하고 그 방법을 써서 물질의 상전이와 고비현상을 연구하였다.  그래서 내 논문중 여러개가 이와 관련되어 있다.  대표적인 것으로  Journal of Physics 에 발표한  "A New Efficient Monte Carlo Technique",  "A Rejection free Monte Carlo Technique" 라든가  또 물리학계에선 세계에서 가장 권위 있는 학술지인 Physical Review Letters 에 실린 논문도 "Monte Carlo Technique for Universal Finite Scaling Funtions..." 이다.  그래서 지금도 컴퓨터와 몬테칼로 기법을 이렇게 이야기하면서 써 내려가면 내 정열을 바쳤던 옛 추억에 내 가슴에는 잔잔한 흥분이 인다.  그 때가 세벽 3시였다.  새로운 효율적 몬테칼로 기법을 생각해 내고 그 방법을 연구하고 있을 때였다.  훨씬 좋은결과가 나와야 했다. 정확한 풀이가 알려진 상태함수를 새로 개발한 기법을 써서 셈한 다음 그 결과를 곡선으로 그려 정확한 곡선과 비교해 보는데 그 차이가   너무 컸다.  나는 좌절감 때문에 맥이 빠져 있었다.  아무래도 풀그림에 문제가 있다고 생각되었다.  아직 랩톱이 없을 때였고 집에 PC를 하나 놓을 만한 사치를 부릴 수 있는 때가 아니었다. 그래서 Televideo 라는 천근은 되는 휴대용(?) PC(IBM-XT 호환기종)를 학교와 집사이를 가지고 다니고 있었다. 나는 다시 컴퓨터를 켜고 풀그림을 자세히 하나 하나 점검해 갔다.  한군데 루프 변수 "i" 가 찍혀 있을 곳에  상수 "l" 이 찍혀 있었다.  그래서 그 버그를 수정하고 다시 풀그림을 돌려 보니 곡선이 하나가 사라졌다.  나는 착시현상을 일으켰거나 풀그림에 문제가 생긴줄 알았다.  나중에 알고 보니 몬테칼로 셈이 너무 잘 맞아서 정확한 풀이 곡선을 덮어 그렸던 것이다.   그 때 그 흥분과 감동은 아직도 어제 일인양 생생하다.   컴퓨팅의 맛이란 바로 그런 것이다. ......

몬테칼로 기법이란 막수 (random number) 만을 생성해서 수치셈 (computation) 을 하는 것이라 말할 수 있다 ......... (source 이구철)

먼저 몬테 칼로라는 이름의 유래에 대해서 말하지요.  프랑스의 남쪽 지중해를 마주 보는 이태리와의 국경지대에 모나코라는 작은 나라가 있습니다. 한 40 년쯤 전에 미국에서 한참 잘 나가던 여배우 그래이스 케리가  이 나라 왕과 결혼하는 사건이 있어 이 작은 나라는 세상을 떠들썩하게 했습니다.  이 나라의 서울의 이름이 몬테 칼로인데 이 곳은 카지노라는 도박장으로 유명합니다. 바티칸 다음으로 작은 독립국으로 국가 재정은 이 카지노 영업에서 생기는 수입으로 꾸려 나가고 있습니다.   도박을 즐기는 세계의 노름꾼들이 자신의 도박 운을 주사위에 걸기 위해 몰려 듭니다. 1942년 2 차 세계대전의 폭연이 막 피어 오르던 때 미국 서부지역에 있던 로스 알라모스의 비밀 연구소에서는 세계의 초 일류 두뇌들이 모여서 원자탄 개발을 서두르고 있었습니다.  이 지음 제 1 세대의 컴퓨터가 이곳에서 그 모습을 들어 내기도 했지요.  이곳에 연구하던 Stanisław Ulam 이라는 수학자가 Enrico Fermi, John von Neumann, Nicholas Metropolis 등등의 수학, 물리학자와 함께 수치 셈을 하는 한 방편으로 확률적 방법을 생각 해 내었습니다.  이 생각을 처음 한 유램이 제안한 이름이 몬테 칼로 방법입니다.  모나코의 카지노를 떠 올리고 지은 이름이 아닌가 생각합니다.  카지노나 수치적분이나 모두 주사위를 던져서 그 목적을 달성한다는 점에서 같은 동아리에 속한다고 볼 수 있기 때문입니다. ............... (source  이구철)

term :

계산 (Computation)   모의 담금질 (Simulated Annealing)   최적화 (Optimization)   순회판매원 문제 (Travelling Salesman Problem)    유전알고리즘 (Genetic Algorithm)   몬테칼로 기법 (Monte Carlo method)   

site :

• 뷔퐁의 바늘- 몬테칼로 기법의 원조 : 이구철
• 몬테칼로 기법이란 : 이구철
• 몬테칼로 시뮬레이션 (Monte Carlo Simulation)