Getting Started

알고리즘 공부 좀 미리 해둘걸ㅠㅅㅠ 이 과목은 철저한 복습과 암기가 살 길이라는 것을 2주차에 직감했다... 진짜 행복하네

수업시간에 모르는 것들이 나오면 따로 공부해서 추가적인 포스팅을 하도록 하겠슴미다. 

---

Insertion Sort: 삽입 정렬

삽입 정렬 알고리즘이란 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하고 정렬하는 알고리즘이다.

쉽게 말하자면, 카드 정리라고 할 수 있다. 나는 원카드 게임을 할 때 패를 받으면 오름차순으로 정렬을 한다(2, 5, 8, 9). 또 새로운 카드를 손에 넣었을 때 숫자 크기를 비교하여 알맞은 위치에 카드를 꽂아넣는다(2, 5, 7(new!), 8, 9). 이게 삽입 정렬이다. 

 

삽입 정렬 알고리즘의 알맞게 수행되는지를 증명할 때, 종종 Loop invariant(반복문 불변식)을 사용한다.

loop invariant란, 배열의 인덱스 j로 시작할 때, A[1...j-1]은 항상 정렬된 상태여야 한다는 것이다.

A[5]를 key값으로 설정하여 위치를 찾을 때, A[1]~A[4]는 오름차순이든 내림차순이든 정렬이 이루어진 상태인 것이다.

 

이 불변식을 사용하여 알고리즘의 정확성을 증명하기 위해서는 다음 세가지를 보여야 한다.

• Initialization(초기화): 첫 번째 반복이 시작되기 전, 불변식이 참이여야한다.

삽입 정렬 알고리즘은 배열의 두 번째 요소부터 key값에 넣는다. 사실 리스트의 맨 첫 번째 요소는 그 앞에 비교할 요소가 없기 때문에 이미 정렬이 완성된 것으로 본다.

• Maintenance(유지): 반복이 시작되기 전 참이라면, 반복이 끝난 후에도 여전히 참이여야한다.

새로운 key 값을 추가해도, 해당 요소를 올바른 위치에 삽입하기 때문에 그 앞쪽의 배열 요소들은 계속해서 정렬을 유지한 상태이다.

• Termination(종료): 반복문이 종료될 때, 배열 전체가 완전히 정렬된 배열이여야 한다.

---

Analyzing Algorithms: 알고리즘 분석

알고리즘 분석에는 Random-access machine(RAM) model을 사용한다. 이 모델에서는 기본 연산들이 모두 동일한 시간 안에 실행된다고 가정한다. 레지스터에서 CPU로, CPU에서 레지스터로 접근하는 시간이 사실상 '0'이라고 가정한다.

 

삽입 정렬의 분석

기본적으로 알고리즘의 실행 시간은 입력 크기에 따라 달라진다.

삽입 정렬의 한 명령문의 실행 시간은 ∑(명령문의 비용)×(명령문이 실행되는 횟수)로, 모든 명령문에 대한 실행 시간을 합산해야한다.

$t_j$ = 인덱스 j에 대한 반복문이 실행되는 횟수이다.

• 최선의 경우: 배열이 이미 정렬되어 있으므로($t_j$ = 1), 각 반복에서 한 번만 비교한다.
• 최악의 경우: 배열이 역순으로 정렬되어 있으므로($t_j$ = j), 각 반복마다 비교를 j번 수행한다. 최악의 경우의 실행시간은 입력에 상관없이 실행 시간이 최대로 걸리는 경우를 보장하는 상한선을 제공한다. 
• 평균적인 경우: 평균적으로 key값 A[j]는 A[1...j-1]의 절반보다 작고 나머지 절반보다 크다. ($t_j$ = j/2)

Order of Growth(증가 기준)

실행시간을 표현하는 방법 중 하나로, 분석을 쉽게하고 중요한 특징에 집중하게 해주는 추상화 방법이다.

주어진 실행 시간 공식에서 Leading term만 살펴본다. Leading term은 실행 시간 공식에서 가장 중요한 항으로, 가장 높은 차수의 항에서 상수를 무시한 것이 Leading term이다.

예시로 실행 시간 공식이 $an^2 + bn + c$이라면, 가장 높은 차수의 항은 $an^2$이고, 상수를 무시하면 $n^2$이 된다.

최악의 경우 실행시간 $T(n)$은 $n^2$처럼 증가하지만, 실제로 $n^2$과 정확히 같지는 않다.

알고리즘의 실행 시간이 $O(n^2)$로, 이는 알고리즘 증가 기준이 $n^2$라는 것이다.

빅O 표기법은 최악의 경우 실행시간 표기법이다. 난 몰라서 뭔 소리인가 했음ㅋㅡㅋ

최악의 경우 실행 시간이 더 작은 성장률을 가질 때, 우리는 그 알고리즘을 더 효율적인 알고리즘이라고 한다.

---

Designing algorithms: 알고리즘 설계

Divide and Conquer: 분할과 정복

merge sort algorithm(합병 정렬 알고리즘)에서 사용되는 메서드다.

문제를 여러 개의 서브 문제로 나누고, 부분 문제들을 재귀적으로 해결한 후, 부분문제들의 해결책을 결합하여 본 문제의 해결책을 얻는다.

 

참고로 삽입 정렬 알고리즘에서 사용되는 메서드는 Incremental method(점증적)로, 원소를 하나씩 처리하고 누적하여 결과를 도출한다.

---

Merge Sort: 합병 정렬

위에서 말했듯 divide and conquer에 기반한 정렬 알고리즘이다.

최악의 경우 실행 시간이 삽입 정렬보다 짧다.

 

A[p...r]을 정렬하기 위해서,

• 배열을 두 개의 서브배열 A[p...q] & A[q+1...r]로 나눈다. 이 때 q는 A[p...r]의 절반이다.
• 서브배열을 재귀적으로 정렬함으로써 정복한다.
• 두 개의 정렬된 서브 배열을 합병하여 하나의 정렬된 A[p...r]을 만든다.

위 단계를 모두 거치면 MERGE(A, p, q, r)에 대한 잘 정의된 절차가 나온다.

• 입력: 배열 A와, 입력값 p, q, r이 주어진다. 이 때 p≤q<r 이어야하며, 두 개의 서브 배열은 각각 정렬되어 있다. p, q, r의 제한 조건에 의해 두 서브 배열 중 빈 배열은 없다.
• 출력: 두 서브 배열을 합병하여 하나의 정렬된 A[p...r]이 출력된다.
• T(n) = O(n), 여기서 n = r-p+1은 병합되는 요소의 개수를 말한다.

---

Analyzing Divide-and-Conquer Algorithms

Divide and Conquer 메서드를 사용하는 알고리즘은 루프를 도는 알고리즘이 아니다.

실행 시간을 설명하기 위해서 재귀를 사용한다.

 

• T(n) = 크기가 n인 문제의 실행 시간을 말한다.
• Base case(기저 사례): 문제의 크기가 충분히 작으면(n≤c, c는 상수), 실행시간은 O(1)가 된다. 즉, 작은 문제는 상수 시간 안에 해결된다.
• 그렇지 않은 경우(n>c), 문제를 a개의 서브문제로 나눈다고 가정하면 각 서브문제의 크기는 원래 문제 크기의 1/b 이다. (merge sort에서, a=b=2)
• D(n) = 크기가  n인 문제를 나누는데 걸리는 시간을 말한다.
• a개의 문제를 해결해야하며, 각 서브문제의 크기는 n/b이다. 각 서브문제를 해결하는데 걸리는 시간은 T(n/b)이므로, aT(n/b)만큼의 시간이 소요된다.
• C(n) = 서브문제들의 해답을 결합하는데 걸리는 시간을 말한다.

따라서 재귀식은 다음과 같이 표현된다.

n ≤ c 일 때, T(n) = O(1)

n > c 일 때, T(n) = aT(n/b) + D(n) + C(n)

 

---

Analyzing Merge Sort - Use a Recurrence

간단히 설명하기 위해, n=1일 때는 T(n) = O(1)이라고 가정한다.

 

n ≥ 2 일때, 병합 정렬의 단계적 실행 시간은 다음과 같다.

• Divide:  p와 r의 평균을 계산해 q를 구하는데 O(1)의 시간이 걸린다. D(n) = O(1)
• Conquer: 크기가 n/2인 두 개의 서브문제를 재귀적으로 해결한다. 2T(n/2)
• Combine: 크기가 n인 서브배열을 MERGE하는데 O(n)의 시간이 걸린다. C(n) = O(n)

D(n) + C(n) = O(1) + O(n) = O(n) 이므로, 병합 정렬의 실행시간을 위한 재귀식은 다음과 같다.

n=1일 때, T(n) = O(1)

n>1일 때, T(n) = 2T(n/2) + O(n)

 

병합 정렬 재귀식을 풀면 T(n) = O(n$log_2$n) 으로 정리된다.

  

** 대학교 수업을 듣고 이해한 부분을 최대한 풀어서 작성한 글입니다.

틀린 정보가 존재할 수 있으며, 언제나 피드백은 환영입니다. **