출처: https://www.whatwant.com

 

[ Terminology & Problem ]

이번에 살펴보고자 하는 알고리즘은 "Longest Common Subsequence (LCS)" 이다.
어떤 문제를 해결하고자 하는 것인지 설명하기 전에 용어에 대한 정의부터 살펴보겠다.

 

출처: https://www.whatwant.com

 

여기에서 주의깊게 살펴봐야 할 것은 "Substring"인데, 연속적인 character를 의미한다.

 

출처: https://www.whatwant.com

 

반면, "Subsequence"는 비연속적인 character 순서를 포함한다.

 

출처: https://www.whatwant.com

 

2개의 string이 주어졌을 때, 공통적으로 있는 subsequence를 "Common Subsequence"라고 한다.

그리고 "Common Subsequence" 중에서 가장 긴 길이를 갖는 것을 "Longest Common Subsequence (LCS)"라고 한다.

 

이런 LCS를 구하는 방법을 찾는 것이 이번 목표이다 ^^

 

[Brute force approach]

착실하게 (무식하게?) 찾는 방법은 다음과 같다.

 

출처: https://www.whatwant.com

 

당연히 이렇게 찾는 것은 말이 안된다.

입력 string의 갯수가 n개라고 했을 때 2의 n승만큼 subsequence가 나오기 때문이다.

 

[Notation]

이후 설명할 내용에서 사용하는 notation을 정리하면 다음과 같다.

 

 

[Idea]

똑똑하게 해결하기 위한 아이디어는 다음과 같다.

 

출처: https://www.whatwant.com

 

복잡해보이는데, 가만히 살펴보면 엄청 당연한 이야기를 하고 있다.

 

특정 위치의 chracter가 같다면 LCS는 그 같은 값은 일단 LCS에 포함되는 것이고,

각 입력 string에서 동일한 값보다 1씩 작은 string의 LCS값을 더해주면 전체 LCS가 된다.

 

반면, 특정 위치의 chracter가 같지 않다면 LCS는 입력 string중 하나의 값을 1 차감한 내역으로 다시 LCS를 구하면 된다.

 

 

[ Longest Common Subsequece - Dynamic Programming Algorithm ]

위의 아이디어를 정리하면 다음과 같은 알고리즘이 된다.

 

 

이걸 어떻게 하는 것인지 살펴보자.

 

다음과 같은 2개의 string이 입력되었을 때 다음과 같은 표를 그리고 초기화 하자.

  - X = ABCBDAB

  - Y = BDCABA

 

출처: https://www.whatwant.com

 

앞에서 정리한 알고리즘을 기반으로 하나씩 값을 채워나가면 된다.

 

출처: https://www.whatwant.com

 

① x ≠ y 이므로 둘 중 큰 값 선택해야 하는데, 둘 모두 0이므로, 0

② ③ 상동

④ ⑥ x = y 이므로, 왼쪽 대각선 위의 값 + 1

⑤ x ≠ y 이므로 둘 중 큰 값 선택해야 하는데, ④ 값이 1이므로, 1

 

그리고, 어느 곳에서 값을 받아갔는지 화살표로 표기 해줘야 한다.

 

이런식으로 하나씩 값을 작성해 나가면 다음과 같이 된다.

 

출처: https://www.whatwant.com

 

LCS값이 어떻게 되었는지는 다음과 같이 추적해볼 수 있다.

 

출처: https://www.whatwant.com

 

화살표를 보면 알겠지만, 정답이 하나만 있는 것은 아니다.

 

출처: https://www.whatwant.com

 

[Pseudo Code]

손으로 진행했던 것을 코드로 만들어 보자.

 

출처: https://www.whatwant.com

 

손으로 진행했던 것과 차이가 있는 부분 위주로만 설명해봤다.

위 표에서 화살표를 살짝 끄적였는데, code에서는 b array를 통해 기록하도록 했다.

 

결과를 출력하기 위한 코드는 다음과 같다.

 

 

[Time & Space]

code를 보면 직관적으로 파악 가능한 것 처럼 Time complexity는 다음과 같다.

 

 

Space는 b array + c array 공간이 추가적으로 필요하기에 다음과 같다.

 

 

그런데, Space를 줄일 수 있는 경우가 있다.

실제 String 정보까지는 필요없고, 길이값만 필요하다고 하면 다음과 같이 작은 space만 필요로 한다.

 

 

또 다른 경우로는 다음과 같은 case가 있을 수 있다.

 

출처: https://www.whatwant.com

 

LCS에 대해서는 여기까지~

반응형

출처 : https://www.whatwant.com

 

이번에 살펴볼 것은 한글로 말하자면, "막대 자르기" 알고리즘이다.

어떤 문제를 해결하기 위한 알고리즘인지 알아보자.

 

[Problem]

n만큼의 길이를 갖고 있는 막대기가 있다고 하자.

 

출처 : https://www.whatwant.com

 

이 막대기를 잘라서 팔아야 하는데, 길이에 따라서 판매되는 가격이 다르다고 했을 때

어떻게 잘라서 팔아야 최대 이익이 나오는지를 찾아내야 하는 것이 문제이다.

 

 

위와 같이 막대기 길이에 따른 수익은 제시가 된다.

알아야 할 notation 규칙은 다음과 같다.

 

 

[Brute force approach]

"n = 4" 만큼의 길이를 갖고 있는 막대기가 있고, 길이에 따른 가격은 다음과 같다.

 

출처 : https://www.whatwant.com

 

이 때, 나올 수 있는 모든 경우의 수를 다 살펴보자면 다음과 같다.

 

출처 : https://www.whatwant.com

 

최대 수익을 얻기 위해서는 ⑶번과 같이 2개 묶음으로 나누는 경우가 10만큼의 수익을 얻을 수 있다.

그런데, 이처럼 모든 경우의 수를 나열해서 모두 계산해보기에는 너무 비효율적이다.

 

[Rod-Cutting Algorithm]

일단 다음과 같은 계산식을 살펴보자.

 

 

n 길이의 막대기가 있을 때, i 길이의 가격과  'n - i' 길이일 때의 최대 수익의 합이 최대인 i값을 찾는 것을 의미 한다.

 

출처 : https://www.whatwant.com

 

다음과 같은 문제가 주어졌다고 해보자.

 

 

r[i], s[i] 값은 다음과 같이 계산해볼 수 있다.

 

 

그러면 다음과 같은 결과를 얻을 수 있다.

 

 

이렇게 만들어진 표가 있다면,

8 길이만큼의 막대기가 주어졌을 때 다음과 같이 활용할 수 있다.

 

출처 : https://www.whatwant.com

 

[Pseudo Code]

 

 

[Time & Space]

이 알고리즘에서는 r[n], s[n] 값을 저장하기 위한 메모리 공간을 필요로 한다.

길이 n 값에 선형으로 비례하는 만큼 사용하기 때문에 다음과 같이 정리할 수 있다.

 

 

소요 시간은 Pseudo Code를 보면 중복 for문이 사용되는 부분을 잘 살펴봐야 하는데,

다음과 같이 정리 해볼 수 있다.

 

 

수고하셨습니다 !!!

반응형

출처: https://www.whatwant.com

 

왠지 이름만 들어도 어려울 것 같은 느낌이 팍팍 드는, Dynamic Programming !!!

 

연구비를 타내기 위해 그냥 있어보이려고 멋지게 작명하다보니 이런 이름을 가졌다고 한다.

사람 사는게 다 그렇지 뭐~ ^^

 

"Dynamic Programming"은 뭔가 계산하는 알고리즘이라기 보다는

작은 문제를 풀어서 그 중간 결과를 기록해 놓음으로써 다시 재계산하지 않도록 하는 방법이다.

 

여러 유형의 문제를 Dynamic Programming으로 푸는 것을 살펴볼텐데

그 첫번째로 살펴볼 것이 바로 "Assembly-line scheduling" 이다.

 

 

[Definition]

'Assembly-line'이라는 것에 대한 정의 부터 살펴보자.

 

출처: https://ko.dict.naver.com/#/entry/koko/db51c8c4d1144a24b1d8103e3ebd94e3

 

컨베이어벨트를 따라 단계별로 부품 조립하는 것을 생각하면 된다.

 

출처: https://www.whatwant.com

 

- station : 조립 단계. 제품 조립은 n개의 station을 거치면 완성이 된다.

- a : 각 station 단계에서 소요되는 시간

- line : 하나의 컨베이어 벨트로 생각하면 된다.

- e : line에 조립을 시작하도록 하기 위해 소요되는 시간

- x : 조립 완료된 제품을 전달하기 위해 소요되는 시간

- t : line을 옮기기 위해 소요되는 시간

 

 

[Problem]

여러 line으로 구성된 assembly-line이 있을 때,

어떤 경로가 가장 짧은 소요 시간으로 조립할 수 있는지 최적의(가장 빠른) 경로를 찾는 방법은?

 

 

[Solution-1]

가장 확실하고 무식한(?) 방법으 모든 경우의 수를 구해서 찾는 방법이다.

 

하지만, 말 그대로 무식한 방법이기에 ... 경우의 수가 너무 크다.

 

 

 

[Solution-2]

스마트한 방법을 찾아보자.

 

▷ Idea

어느 시점(S)에서 자기 순서까지 올 수 있는 방법은 2가지 경우 밖에 없다.

 

출처: https://www.whatwant.com

 

자기가 있는 동일한 line의 직전 단계에서 오는 방법과, 다른 line의 직전 단계에서 오는 2가지의 경우이다.

 

 

그러면, 그 2가지의 경우 중에 가장 빠른 것을 선택하면 되게 되는 것이다.

 

▷ How to

그러면 예시를 살펴보자.

 

출처: https://www.whatwant.com

 

각 단계에서 소요되는 시간을 더해가면서 정리하면 된다.

보다 더 짧은 시간을 선택하면 되기 때문에 □로 표기된 값들이 선택된 결과들이다.

 

이렇게 선택하는 과정에서 소요되는 Running Time은 어떻게 될까?

각 Station에서 2개씩 값을 보면 되기 때문에 2n의 Running Time이 필요하고,

entry + exit 과정이 있기 때문에 이를 정리하면 다음과 같다.

 

 

Brute-force 방법으로 할 때에는 어느 시점(S)에서 자기한테 까지 오는 모든 경우의 수를 살펴보지만

지금 방식에서는 바로 직전의 2가지 경우만 살펴보기 때문에 n에 비례하는 복잡도를 갖게 되었다.

 

 

그러면, 중간에 각 S단계에 따른 값들을 어떻게 저장하면 될까?

 

 

위와 같은 표 내용만 기록/기억 하고 있으면 되는 것이다.

그런데, 이 것만 가지고는 어떤 경로로 구성된 것인지 알기가 어렵다.

 

출처: https://www.whatwant.com

 

이 내용을 기록할 표가 하나 더 필요한 것이다.

 

 

그런데, 2개의 테이블이 모두 필요할까?

 

경로만 확인 가능해도 되는 경우에는 L table만 있으면 된다.

S table은 현재 값과 직전 값만 알면 되고, 최적해(S* = 38) 값만 저장하면 된다.

 

S table에서 S3를 계산할 때 S2 값만 알면 된다. 즉, S1의 내용은 필요 없다.

메모리를 굳이 table 전체 크기만큼 잡아 놓지 않아도 된다는 것이다.

 

 

L table 값만 알면 최적 경로를 찾을 수 있기 때문이다.

 

반대로 S 값을 갖고 있는 table만 있어도 L 값 table 없이 경로를 찾아낼 수는 있다.

하지만 L 값 table을 사용하는 것이 훨씬 더 편하기에 L Table을 이용하는 것이다.

 

 

▷ Pseudo Code

코드로 구현해보면 다음과 같다.

 

출처: https://www.whatwant.com

 

뭔가 복잡해보이는데, 살펴보기 편하게 구분해보면 다음과 같다.

 

출처: https://www.whatwant.com

 

결과를 출력하는 부분은 아래와 같이 구현해볼 수 있다.

 

 

실행 결과는 다음과 같이 나올 것이다.

 

 

 

▷ Space consumption

일단 기본적으로는 S table과 L table 모두 필요로 한다는 전제 하에 다음과 같은 메모리 사용량을 필요로 한다.

 

 

 

▷ Running time

하나의 요소 別 소요 시간이 Θ(1) 소요시간이 걸린다고 했을 때, 전체 소요 시간은 Θ(n)이라고 할 수 있다.

 

 

 

뭔가 심오한 Dynamic Programming의 세계이다~

반응형

출처: https://www.whatwant.com

 

"Radix"가 뭘까?

'기수(基數)'는 0~9까지 기본이 되는 수를 의미하는데, 여기에서는 '진법(進法)'의 의미가 더 큰 것 같다.

 

https://en.dict.naver.com/#/entry/enko/17ef262637ad4f04a48f2e6a0186dbbd

 

"Radix Sort"의 다른 호칭은 다음과 같다.

- 기수 정렬

- Bucket Sort

- Digital Sort

 

Radix Sort 알고리즘도 역사가 오래된 아이인데, 1923년에 이미 천공카드 분류 방법으로 널리 사용되었단다.

(어!? 천공카드가 뭔지 아는 것 만으로도 년식 인증인가!?)

 

 

① MSD (Most Significant Digit,  최상위 유효숫자)

  - 앞(큰) 자리 부터 정렬을 해 나가는 방식이다.

 

출처: https://www.whatwant.com

 

  - 중간에 가로로 있는 구분선 위치 정보는 중요하다.

  - 단계 별로 구분선 안에서만 정렬이 이루어져야 하기 때문이다.

 

② LSD (Least Significant Digit, 최하위 유효숫자)

  - MSD 방식과 정반대로 뒤(작은) 자리 부터 정렬을 해보자.

 

출처: https://www.whatwant.com

 

  - Stable 이라는 속성을 정말 잘 이용한 방법으로 보인다.

  - MSD와 다르게 가로줄(각 단계에서의 구분 위치) 정보를 관리할 필요가 없다.

  - 아랫 자리들이 이미 sorting이 되어있기 때문에 윗 자리 sorting을 하면 전체가 sorting 된다.

 

③ Pseudo Code

  - 너무 추상적일 수 있지만, 일단 다음과 같이 Pseudo Code를 정리할 수 있다.

 

출처: https://www.whatwant.com

 

  - 여기에서 중요한 것은 "stable sort" 방식이어야 한다는 점이다.

 

④ Running Time

  - 우리는 바로 전에 훌륭한 stable sort 알고리즘 중 하나를 공부했었다 → Counting Sort !!!

  - Counting Sort 알고리즘을 이용해서 Radix Sort를 해본다고 가정하면, 다음과 같다.

 

출처: https://www.whatwant.com

 

  - 위 내용을 정리하자면, 다음과 같다.

 

출처: https://www.whatwant.com

 

⑤ Changing d and k

  - 우리가 지금까지 다루는 방식은 다음과 같다.

출처: https://www.whatwant.com

 

  - 하지만, 이것을 좀 다르게 처리할 수도 있다.

 

출처: https://www.whatwant.com

 

  - 응?! 10진법이 아니라 100진법(진수)으로 처리할 수도 있다는 것이다.

 

⑥ optimal r

  - 일단 아래 그림을 잘 살펴보고 각 변수값의 정의를 확인하자.

  - n개의 b-bit 숫자가 있다고 했을 때, r 묶음으로 처리를 하는 경우이다.

 

출처: https://www.whatwant.com

 

  - 이럴 때, 우리는 다음의 최적해 r 값을 찾아야 하는 것이다.

 

출처: https://www.whatwant.com

 

  - 2 가지 경우로 나누어서 생각해보자.

 

출처: https://www.whatwant.com

 

  - 위의 경우는 입력값 개수에 비해서 b값이 많이 작을 경우이다.

    . 이 때는 굳이 나누지 말고 통으로 (하나로) 묶어서 정렬을 해도 충분하다는 의미이다.

 

  - 다른 경우는 다음과 같다.

 

출처: https://www.whatwant.com

 

  - 입력값 개수보다 값 자체가 길면, 좀 나누어서(log n 정도) 정렬을 하는 것이 좋다는 의미이다.

 

⑦ extra memory

  - 앞에서 살펴봤겠지만, 일단 Radix Sort는 in place 알고리즘은 아니다.

 

⑧ memory copy

  - d 값만큼 정렬 step이 발생하는데, 이 때마다 값들을 복사해야하는데 이로 인한 cost가 크다.

 

 

 

뭔가 좀 어수선하게 설명이 되었는데,

전체적인 흐름은 파악이 되었을거라 기대해본다.

반응형

출처: https://www.whatwant.com

 

이번에 살펴볼 Sorting algorithm은 앞에서 공부한 것들과 궤를 달리한다.

 

지금까지 공부한 것은 비교(comparison) 기반의 정렬이었지만

이번에는 counting 방식으로 정렬을 하는 계수 정렬(Counting sort)이다.

 

① basic counting sort

  - 비교 행위 없이 입력값 하나씩 읽어가며 개수만 세는 것으로 정렬이 된다.

 

출처: https://www.whatwant.com

 

② extra memory

  - 개수를 세기 위한 C(count array)가 추가로 필요하다. (= in place 알고리즘이 아니다!)

 

③ No stable

  - 입력값의 순서가 유지되는 것을 "stable 하다"고 한다.

 

  - 위 그림에서 3개의 "3" 입력값에 대해서 살펴보면,

    . (빨간색) index 값으로 표현해보면 '3-3', '6-3', '8-3'이라고 할 수 있다. 각 '3'은 다른 '3'이다.

    . 이 때, 출력값(output array)에서 '5-3', '6-3', '7-3'이 있는데,

    . 입력값의 순서가 유지된 것이라고 할 수 있을까?

 

출처: https://www.whatwant.com

 

  - Counting sort는 stable 할 수 없는 algorithm 이다.

 

④ Stabled(Advanced) Counting Sort

  - Counting sort 를 Stable 하도록 만들 수 있다.

 

  - Encoding ..... 기존 count array를 기반으로 누적값을 저장하는 C' array를 만들어줘야 한다.

 

출처: https://www.whatwant.com

 

  - Decoding ..... 누적값을 갖고 있는 C' array와 입력값(A array)를 가지고 출력값(B array)를 만들어준다.

    . 입력값의 제일 끝에서 부터 역으로 하나씩 처리하는 방식이다.

 

출처: https://www.whatwant.com

 

    . 하나 더 해보면, 다음과 같다.

 

출처: https://www.whatwant.com

 

    . 그 다음 "3" 값을 주의 깊게 봐야 한다.

      왜냐하면, 처음에 했던 "3"과 이번에 해야하는 "3"은 다른 "3"이기 때문이다.

 

출처: https://www.whatwant.com

 

    . 뭔가 신기하게 보일 수도 있긴 하지만... 그래서 뭐?

    . 입력값(A array)의 3의 순서에 따라 출력값(B array)의 순서가 정해진다. → Stable 하다 !!!

 

⑤ Pseudo code

  - 왠지 복잡해보이지만, 복잡하지 않은 코드이다.

 

출처: https://www.whatwant.com

 

  - 변수 (메모리) 모습을 그려보면 다음과 같다.

 

출처: https://www.whatwant.com

 

  - 여기에서 k는 입력값의 종류(개수)를 의미한다.

  - 코드를 분석해보면 다음과 같다.

 

출처: https://www.whatwant.com

 

⑥ Running Time

  - 실행 시간은 선형이다.

 

출처: https://www.whatwant.com

 

  - 정리해보면 다음과 같다.

 

출처: https://www.whatwant.com

 

 

그 이름에 걸맞게 입력값을 하나씩 세기만 하면 되는 시간인 것이다 !!!

즉, 앞에서 살펴본 "Lower bounds for (comparison) sort" 제약에 해당하지 않는다 !!!

 

반응형

출처: https://www.whatwant.com

 

[ 공부 순서 ]

① Comparison sorts

② Lower bounds for (comparison) sorting

③ Decision-tree model

 

 

지금까지 공부한 Sorting 방식은 전부 비교(comparison)라는 행위를 이용하고 있다.

그런데, 이러한 Comparison sorting에 있어서 worst-case인 경우

최소한 "n log n" 번 비교를 해야한다는 것에 대한 증명 과정을 살펴보고자 한다.

 

 

① Comparison sorts

  - 정렬(Sorting)을 하기 위해서 크기 비교(comparison)만을 수행하는 알고리즘

  - 종류 : Insertion / Merge / Selection / Heap / Quick

 

② Lower bounds for (comparison) sorting

  - 모든 comparison sort는 worst case 상황에서 최소한  Ω(n log n) 번의 비교를 요구한다.

  → 이후 내용은 본 명제를 증명하는 과정

 

③ Decision-tree model

  - 모든 입력은 동일한 값이 없다고 가정

  - 비교(comparison)는 <, >, ≤, ≥ 4종류가 있지만, ai ≤ aj 하나로 모두 처리 가능

    ( ai ≤ aj 비교를 수행하게 되면 True or False 결과. 그러므로  ai ≤ aj 한 번만 수행하면 됨)

 

  - comparison sort는 decision-tree로 표현(설명) 가능

    . full binary tree

    . leaf는 입력 값들의 순열(permutation)

    . internal node는 어떤 값을 비교하는 지를 표현

 

  - 입력값 크기가 3인 insertion sort는 다음과 같은 decision-tree model로 표현

 

출처: https://www.whatwant.com

 

  - 예시를 하나 돌려보면 다음과 같다.

 

출처: https://www.whatwant.com

 

  - leaf 개수는 어떻게 계산할 수 있을까?

    . 입력값의 개수가 n 일 때, n!

    . 위 예시의 경우, n = 3 이기 때문에 3! = 6

 

  - Left / Right subtrees

    . 특정 node를 기준으로 왼쪽은 ai ≤ aj 값들만 존재, 오른쪽은 ai > aj 값들만 존재

    . 밑의 node들도 모두 동일한 결과

 

출처: https://www.whatwant.com

 

  ★ the worst-case number of comparisons = the height of its decision-tree

    - h : height

    - n : number of element

    - n! : number of leaves

 

출처: https://www.whatwant.com

 

 

음.... 일단 내용은 파악했는데,

그래서 어쩌라고? ^^

 

다음에 살펴볼 counting 방식의 정렬(sorting)은 이와 다르다 !!!

반응형

출처: https://www.whatwant.com

 

기사 작위를 갖고 계시는 '토니 호어'로 불리우시는 분이 1961년에 발표한 정말 정말 유명한 알고리즘이다.

이름 그대로 제일 빠른 정렬 알고리즘이 뭐야? 라고 하면 누구나 외치는 "퀵 정렬" !!!

(참고로 '토니 호어'님은 아직도 시니어 연구원으로 계신다고 한다. 무려 90세의 나이임에도 .... @.@)

 

출처: https://en.wikipedia.org/wiki/Quicksort

 

[ 공부 목차 ]

① Partition

② Balanced partitioning vs Unbalanced partitioning

③ Randomized-Partition

④ Quick-Sort

 

 

① Partition (vanilla Partition)

  - 'Quick Sort'에 있어서 가장 중요한 개념이 바로 partition 이다.

 

출처: https://www.whatwant.com

 

  - 기준값(Pivot element) 보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 배치하여 나누는 것을 의미한다.

  - 가장 기본이 되는 partition 방법은 제일 오른쪽 값을 pivot으로 해서 하나씩 비교하는 것이다.

 

출처: https://www.whatwant.com

 

  - 제일 오른쪽 값을 기준으로 제일 왼쪽부터 하나씩 비교해서 작은값 그룹과 큰값 그룹을 만들어 간다.

  - 그런데, "1"값을 만났을 때 작은값 그룹에 묶을 때가 문제가 된다.

 

출처: https://www.whatwant.com

 

  - 이럴 때에는 큰값의 제일 왼쪽에 위치한 것과 swap을 하면 된다. (i값 위치의 변화도 살펴봐야 한다)

  - 이렇게 하다보면 끝까지 진행을 하게 될텐데, 마지막에 위치한 pivot 값은 어떻게 해야할까?

 

출처: https://www.whatwant.com

 

  - 역시 마찬가지로 큰값의 제일 왼쪽값과 swap 하면 된다.

  - 이 과정을 pseudo code로 살펴보면 다음과 같다.

 

출처: https://www.whatwant.com

 

  - Running Time을 계산해보면 다음과 같다.

 

출처: https://www.whatwant.com

 

 

② Balanced partitioning vs Unbalanced partitioning

  - partitioning을 할 때에 좌우 균형이 잘 맞춰져서 나뉘어지면 좋겠지만,

  - 그렇지 않고 한 쪽에 치우칠 수도 있다.

 

출처: https://www.whatwant.com

 

  - 균형이 맞지 않는 극단적인 경우를 보면 다음과 같다.

 

출처: https://www.whatwant.com

 

  - Running Time은 다음과 같이 구할 수 있다.

 

출처: https://www.whatwant.com

 

  - 즉, 최악의 상황에서는 n제곱, 보통은 n로그n 이라고 정리하면 되겠다.

  - 그러면, 최악의 상황을 막을 방법은 없을까!?

 

③ Randomized-Partition

  - 최악의 상황이 발생하는 것은 pivot 값을 무조건 제일 끝값을 택하기 때문에 발생을 한다.

  - 그러면, pivot 값을 random하게 선택을 하게 되면 최악의 상황이 벌어질 가능성을 낮출 수 있다.

 

출처: https://www.whatwant.com

 

  - random하게 값을 뽑아서, 그것을 제일 오른쪽(끝) 값과 swap을 한 다음에 partition을 하면 되는 것이다.

 

출처: https://www.whatwant.com

 

  - 그런데, radom 호출 하는 것 자체가 over-head가 될 수도 있다. radom 자체가 비용이 크기 때문이다.

  - 그래서, (첫값 + 가운데값 + 끝값) 3개 중에 중간값을 선택하는 방법도 있긴 하다.

 

 

④ Quick-Sort

  - 지금까지 우리는 Partition을 공부했다. 이를 이용해서 Sort는 어떻게 할 수 있을까!?

 

출처: https://www.whatwant.com

 

  - 일단 partition을 한 다음, 왼쪽/오른쪽 각각 QuickSort를 하면 된다.

  - 그렇다 !!! Divide-and-Conquer 알고리즘이다.

 

출처: https://www.whatwant.com

 

  - Quick-Sort의 Running Time은 어떻게 될까?

 

출처: https://www.whatwant.com

 

  - 메모리 사용은?! 위치를 가르칠 변수 정도면 충분하다. 즉, 입력 데이터의 크기에 영향을 받지 않는다.

 

 

 

지금까지 여러 Sorting algorithm을 알아봤는데, 성능 비교 등을 해보면 좋을텐데...^^

다음 기회로~~~

 

반응형

이번에 살펴볼 정렬 알고리즘은 "Heap Sort(힙 정렬)"이다.

 

[출처] ChatGPT + WHATWANT

 

보통은 위키피디아의 animated-gif 를 통해서 정렬 알고리즘을 엿볼 수 있었는데,

heap-sort 경우에는 도저히 파악이 안되는 내용이라 다른 자료를 찾아봤다. (내가 무지해서 이해를 못한 것이겠지...)

 

[출처] https://www.cs.usfca.edu/~galles/visualization/HeapSort.html

 

너무나 친절한 Visualization을 제공해주는 곳은 다음과 같다.

- https://www.cs.usfca.edu/~galles/visualization/HeapSort.html

- 왼쪽 상단의 "Heap Sort" 버튼을 클릭하면 animation을 보여준다.

 

[출처] https://www.cs.usfca.edu/~galles/visualization/HeapSort.html

 

왜 저렇게 정렬이 되는지 바로 이해가 되시는 분은 그만 공부하셔도 된다!!! ^^

 

사실 공부하기 전에는 대체 어떤 이유로 이렇게 움직이는 것인지 잘 보이지 않아야 정상일 것 같다 ^^

우리에게 필요한건?

 

공부!!!

 

Heap Sort를 알기 위해서는 일단 Heap이 무엇인지 부터 알아야 한다.

 

⑴ Heap의 정의

⑵ MAX-HEAPIFY()

⑶ BUILD-MAX-HEAP()

⑷ HEAP-SORT

 

 

⑴ Heap

Heap은 2가지의 속성을 갖고 있다. 이에 대해서 알아보자.

 

  ① A nearly complete binary tree

  ② max-heap

 

① A nearly complete binary tree

일단 tree 구조와 관련한 용어부터 확인해야 이야기가 쉬울 것 같다.

 

[출처] https://www.whatwant.com

 

tree 관련한 용어들이 더 있지만, 일단 이 정도만 알아도 될 것 같다.

 

그러면, tree 구조 관련하여  "complete binary tree"가 뭔지부터 파악하고

"nearly complete binary tree"가 뭔지 이해해보도록 하자.

 

[출처] https://www.whatwant.com

 

▷ Complete Binary Tree

  - all leaves the same depth

  - all internal nodes have degree 2

 

그러면 nearly complete binary tree는 어떻게 생겼을까!?

 

[출처] https://www.whatwant.com

 

▷ A Nearly Complete Binary Tree

  - 기본적으로는 Complete Binary Tree 구조를 갖고자 

  - all internal nodes have degree 2, but 마지막 leaf는 1개가 부족할 수 있다.

  - 마지막 depth의 leaves는 왼쪽부터 차례대로 배치

 

 

우리가 공부하고자 하는 Heap 구조는 바로 이 "nearly complete binary tree"를 따르고 있다.

 

왜 그럴까!?

 

▷ Array

 

"nearly complete binary tree" 구조를 따를 경우에 이를 array 방식으로 표현하기가 쉽기 때문이다.

반대로 말하면 array를 사용하기 위해서는 nearly complete binary tree 구조여야 한다!!!

 

[출처] https://www.whatwant.com

 

이렇게 되면 어떤 장점이 있을까?

 

[출처] https://www.whatwant.com

 

그렇다 ! 위치에 대한 계산이 가능해진다 !!!

 

여기에서 하나 더 확인해볼 것은 "The height of a heap"이다.

 

▷ The height of a heap

  - 기본적으로 height는 depth와 같은 개념이고, 특정 node를 기준으로 depth가 얼마인지를 의미한다.

  - The height of a heap = The height of the root : 그러면 depth의 의미이다.

  - 그러면, 여기에서 질문 하나

    : 어떤 Heap의 전체 node의 갯수(n)를 알면 height가 얼마인지 알 수 있을까?

 

[출처] https://www.whatwant.com

 

  - height를 h라고 하면, 다음과 같다.

 

[출처] https://www.whatwant.com

 

② max-heap

'binary heap'은 max-heaps와 min-heaps의 2가지 종류가 있다.

 

앞에서는 tree 구조에 대해서만 이야기 했지, 각 node에 들어있는 값에 대해서 이야기하지 않았다.

이제는 각 node에 들어있는 값에 대한 이야기이다.

 

[출처] https://www.whatwant.com

 

위 그림을 보고 오해를 하면 안된다.

당연하게도 모든 parent-child 를 살펴봐도 모두 저 관계를 만족해야 한다.

 

그러면 제일 위의 root node에 들어있는 값은 전체 모든 node 중에서 가장 큰 값이 위치하게 된다.

 

min-heap은 반대이다. root node가 가장 작은 값을 갖는다.

 

우리는 보통 max-heap을 사용한다.

 

 

⑵ MAX-HEAPIFY()

"Max-Heapify" 함수에 대해서 알아보겠다.

함수이기에 입력(input)과 출력(output)이 있고, 그 과정에서 어떤 처리(processing)이 있을 것이다.

 

① input

  - 입력은 어떤 하나의 node가 된다.

 

[출처] https://www.whatwant.com

 

   - 단, 그 노드가 갖고 있는 왼쪽/오른쪽의 subtree들이 이미 max-heap 구조를 갖고 있어야 한다.

 

② float down

  - "4" node를 기준으로 왼쪽/오른쪽 subtree가 각각 max-heap이기에 max-heapify 가능

  - 그래서 "4" 값과 "14"값을 exchange

  - 그런데, "4" node를 봤더니 max-heap 상태가 아님

  - subtree 들은 각각 max-heap 상태이기에 max-heapify 실행

  - 그래서 "4"와 "8"값 exchange

  - 그랬더니, 처음 "4"에서 실행한 max-heapify가 전체적으로 이루어짐

 

[출처] https://www.whatwant.com

 

이렇게 밑으로 흘러가듯이 이루어지는 과정을 "float down"이라고 

 

③ running time

  - max-heapify의 running time을 알아보자.

 

[출처] https://www.whatwant.com

 

 

⑶ BUILD-MAX-HEAP()

max-heap을 만드는 것에 대한 Pseudo Code를 살펴봅시다!!!

 

[출처] https://www.whatwant.com

 

Text에서 floor 함수 표기가 쉽지 않아 조금 이상하게 보이는 부분은 이해해주시길 바라옵니다 ^^

 

일단 A는 max-heap을 하고자 하는 입력 데이터를 의미한다.

 

[출처] https://www.whatwant.com

 

그러면, 밑의 순환문은 어떤 의미일까!?

 

[출처] https://www.whatwant.com

 

그러므로, 순환문의 시작 위치는 다음과 같다.

 

[출처] https://www.whatwant.com

 

그 다음 index가 하나씩 감소하기 때문에 다음과 같은 흐름으로 진행하게 된다.

 

[출처] https://www.whatwant.com

 

전체 길이의 절반 위치에서 시작하는 것은 그 이후의 node는 edge-node 즉, leaves 들이기 때문에

이미 max-heapify가 되어 있어서 굳이 max-heapify를 할 필요가 없는 것이다.

 

▷ Running time

① Upper bound

  - Pseudo code를 기반으로 해서 찬찬히 살펴보면 다음과 같이 실행 시간(횟수)를 확인할 수 있다.

 

[출처] https://www.whatwant.com

 

이를 계산하면 다음과 같이 정리가 된다.

 

[출처] https://www.whatwant.com

 

 

② Tighter bound

 

그런데, 실제로 분석해보면 이는 지나친 upper-bound라고 볼 수 있다.

즉, 이것 보다는 조금 더 tighter-bound를 계산해볼 수 있는 것이다.

 

1번 node 기준으로 max-heapify를 한다고 했을 때, "n = 10" 이므로 O(log 10) 소요시간이 걸린다.

그러면, 5번 node 기준으로 max-heapify를 하면 소요시간이 얼마나 걸릴까?

 

[출처] https://www.whatwant.com

 

5번 node 위치에서의 "n = 2" 이므로 O(log 2) 소요시간이 걸린다.

4번 node 위치에서는 O(log 3), 3번 node 위치에서도 O(log 3) 이다.

 

즉, 실제로 많은 node에서 소요되는 시간이 우리가 계산한 O(log n) 값보다 작다는 것이다.

 

[출처] https://www.whatwant.com

 

이걸 고려해서 계산을 해보면 다음과 같다.

 

[출처] https://www.whatwant.com

 

엇?! 선형(linear)으로 정리가 되었다 !!!

 

⑷ HEAP-SORT

이제 마무리 단계에 왔다.

앞에서 공부한 것들을 모두 모아서 정렬하는데에 어떻게 사용할 수 있는지 Pseudo Code로 살펴보자.

 

[출처] https://www.whatwant.com

 

응!? 이건 뭔가 싶다.

 

▷ Extract-Max

  - BUILD-MAX-HEAP() 실행을 마치면, root-node에 있는 값이 가장 큰 값이 되게 된다.

 

[출처] https://www.whatwant.com

 

  - root-node에 있는 값을 제일 뒤에 있는 node와 교환을 한다.

  - 제일 뒤에 있는 node를 제외한 tree를 가지고, root-node에서 MAX-HEAPFY()를 실행한다.

  - 이 방식 가능한 이유는 이미 BUILD-MAX-HEAP()을 통해, 그 밑의 subtree들이 max-heap 상태이기 때문이다.

 

 

▷ Running Time

  - Pseudo Code를 가지고 수행 시간을 살펴보자.

 

[출처] https://www.whatwant.com

 

  - Worst-case는 이렇게 되겠지만, Best-case는? 모든 것이 같은 값일 때 !!!

  - 5번 라인의 경우 값이 하나씩 줄어들기 때문에, 시간이 조금씩 더 적게 들겠지만 유의미하지는 않다.

  - 결론적으로 Heap-Sort의 Running Time은 다음과 같이 정리할 수 있다.

 

[출처] https://www.whatwant.com

 

▷ Memory

  - Heap-Sort는 추가적인 메모리가 필요하지 않은 in-place 알고리즘이다.

  - 별도의 메모리 공간이 아니라 node 사이의 값을 exchange하는 것으로 처리되기 때문이다.

 

 

우아앙~ 너무 힘들었다.

반응형

+ Recent posts