알고리즘 1주차 월요일 강의

문제에 대한 알고리즘을 어떤 식으로 분석할지 이미 알고 있는 알고리즘으로 분석하는 시간

 

Unsorted List 에서 record 하나를 선택해서 Sorted List에 넣는다. 방바닥에 1부터 100까지 적혀져있는 숫자가 있고 카드 숫자가 안보인다고 가정하자. 만약 누가 정렬해서 1부터 100까지 정렬해서 가져오라고 하면 어떻게 할 것 인가? 대부분 임의의 카드 하나를 선택하는데 이는 이미 정렬된 값이고 다음 카드가 첫 번째 숫자보다 크면 오른손 작으면 왼손으로 넣는다. 같은 방법으로 위치시키면 왼손과 오른손에 카드가 정렬돼서 위치할 것이다. 노란색은 Sorted List이고 오른쪽은 Unsorted List이다. Bar가 그 사이를 구분한다고 하면 맨 왼쪽에 있는 Element는 Sorted List에 속하고 이렇게 시작하게 된다. 임의의 Element를 Unsorted List에서 하나 선택하게 되는데 Bar에서 가장 가까이 있는 핑크색 Element가 선택이 되고 그것을 Sorted List에 어디로 들어가야 하는지 계속 결정하게 된다. 하지만 두 번째 이후로 Sorted List에서는 정렬을 어떻게 할 것인가! 이는 Comparison 방법을 택해서 해당 위치와 Change 하게 된다.

 

 

이렇게 아이디어를 통해서 알고리즘을 만들어야 한다. 뭔가 절차적이고 논리적이고 명확하게 기술을 해야 한다. 포인트는 하나씩 하나씩 Pick을 옮겨 가는 것과 Sorted List로 잘 찾아서 Insert 하는 것 이 두가지이다. Example: Insertion Sort. 일단 Insert해야할 Element를 복사해서 Key라는 변수에 넣는다. 그리고 Key가 위치한 Index도 j에 저장해서 j보다 작은 j-1 부터 시작해서 1번째 Index까지 이동한다. 비교를 하다가 해당 Element가 Key값보다 크다면 계속 Change를 진행한다. i가 0이 되면 제일 작은 Element라는 것이므로 while 문의 탈출조건으로 적어놓는다. Key값과 Element를 비교해서 Key값이 Element보다 작을 때와 i = 0이 되었을 때 빠져나가게 되는 조건을 설정하면 된다.

 

Insertion sort
j = 2 일때 Key값을 복사를 하고 A[j]를 Sorted Array에 넣어야 한다. i는 j-1부터 시작해야 하고 i가 1씩 감소를 해야 한다. 만약 Key가 Element보다 크다면 i+1 위치에 i의 값을 넣는다. 하지만 여기서 i가 0보다 커야한다는 조건 또한 AND 조건으로 넣어야 한다. 왜냐하면 i가 0보다 작거나 같을 경우에도 시행이 된다면 범위를 벗어나도 성립하기 때문이다. While이 끝났을 때 Key값을 i+1 인덱스 위치에 집어넣어야 한다.

 

 

<ALgorithm>
알고리즘이란 문제를 푸는 방법인데, 이 수업에서 하는 것은 1. 알고리즘을 디자인하고 2. 알고리즘을 분석하는 것이다. 새로운 문제를 주고 알고리즘을 디자인해봐~ 의 수업이 아니라 이미 존재하는 알고리즘에 대한 분석을 진행하는 것이 주목적이 된다. 알고리즘이란 두가지로 나뉜다. 1. Correctness와 2. Efficient인데 주로 Time 과 Storage 측면에서 이야기하려고 한다.

 

Design paradigm
incremental 디자인 방법을 사용한다고 얘기를 한다. Divide-and-conquer approach라고 불린다. Merge sort를 보면 절반으로 Divide하고 반반을 다시 반으로 나누고 계속 Divide해 나간다. Element가 하나가 될때까지 Divide를 진행하고 이를 각각 Merge를 하면서 정렬하게 된다. 큰 문제를 사이즈가 작은 문제로 나누고 나누어진 것을 Conquer(Merge)를 진행한다. 1부터 j-1까지의 Sorted 된 SubArray가 있고 j를 하나더 집어넣어서 다시 j-1개의 비교를 진행한다. Divide -> Conquer -> Merge

 

Other Design paradigms
Brute force 방식은 모든 경우를 다 고려해서 진행하는 방식이기 때문에 Paradigm이라고 얘기하기는 살짝 애매한 감이 있다!!!

 

Correctness, 옳음을 판단하는 것이고 Efficiency는 Time complexity에 대해서 생각해보는 것이다. Storage 부분도 얘기하게 될 것

 

Correctness
알고리즘이 correct하다는 것은 모든 Input instance에 대해서 correct output을 만들고 멈춰야 한다. Halt!!) Input instance가 하나가 아니라 굉장히 많다. 예를 들어 수학의 경우 모든 자연수에 대해서, 모든 정수에 대해서 등등 조건처럼 동일하게 적용이 된다. 주어진 문제를 Solve할 수 잇어야 한다.

 

Loop invariant
Insertion 알고리즘이 옳다는 것을 증명해야 한다. 어떻게 증명할까? 교과서에서 Loop invariant를 사용해서 풀었다. Incremental Approach 처럼 독특한 방식을 언급하는 것이지 모든 책에서 동일하게 얘기하는 것은 아니라는 것은 알고 있어야 함. invariants는 변하지 않음을 의미하고 loop을 돌면서 변하지 않는 성질을 이야기 한다. Loop이 돌아가더라도 무엇인가 변하지만 변하지 않는 어떤 성질이 있고 그것을 이용하는 것이다. condition이나 relationship인데 loop이 한번 돌아가더라도 변하지 않는 조건과 관계를 이야기 한다.

 

Loop invariant
1. Initialization. 첫 번째 loop이 돌아가기 전에 True였던 어떤 것을 이용하자. 
2. Maintenance
3. Termination
Loop이 돌아가기 전, 중, 후 모두 True인 경우를 이용한다는 것이다.

 

Correctness of insertion sort
loop invariant. for loop이 돌아갈 때 마다 1부터 j-1까지의 배열은 원래부터 sorted되어 있다는 것이다. j가 2부터 시작하는데 j가 1일 때 그 하나는 원래 배열의 Element이고 Sorted된 상태이다. 다음 j = 3의 경우 j =1 , 2 의 값은 Element에 속하며 Sorted 배열이라는 점. Initialization일 때는 j = 2인 경우이고 Maintenance는 informally하게 증명이 되었다. 반복문의 Body에 속하는 것이라고 보면 된다.  A[j-1], A[j-2], A[j-3]으로 계속 이동해나가는 그 과정이다. 마지막으로  Termination은 j = n+1일 때 끝나게 된다. 1번째 index부터 n번째 index까지 모든 배열의 Element이고 Sorted 된 배열이 만족되므로 Correctness하다는 것이다.

 

 

Efficiency
알고리즘을 수행하기 위한 resource, 시간과 메모리에 관한 문제를 다룬다. 주로 Input size의 function을 표시한다. (n에 대한 표현) 메모리 사이즈는 시간에 비해 중요하게 여겨지지 않는다. 일반적으로 Time보다는 덜 중요하고 주로 Time에 대해서 이야기하게 된다.

 

Efficiency
알고리즘이 하드웨어에서 돌아가야 하는데 어떤 하드웨어인지 모델에 대해서 알아야 한다. Random access machine 모델로 일반적으로 만들어진 하드웨어를 이야기 한다. 기본적으로 RAM은 동시에 operation이 일어나지 않고 Pipeline의 방식을 따르지 않는다. 하나의 Process가 있고 Memory의 Instance가 Sequential하게 시행된다는 말이다. 일반적인 컴퓨터의 Instruction을 가지고 있다는 것이다. Arith, Data move, Control Instruction들이 있는 것 메모리 Hierachy를 생각하지 않고 굉장히 단순한 모델에서 작동한다고 가정하면 된다.

 

Efficiency
Input 사이즈에서 얼마만큼의 시간이 걸리는지 측정할 필요가 있다. n개의 Element가 있을 때 sort하면 어떻게 되는 것인지를 표현한다. 두 개의 Integer를 곱하는 경우,, Word가 굉장히 길다고 가정하면 Constant time이 걸린다고 보기 힘들다. 이런 경우 total number of bit로 표현을 한다. n bit x n bit일때는 다르게 표현한다는 것을 알고 있으면 된다. Graph의 경우는 Vertice와 Edge의 개수로 표현하므로 해당 정보가 중요하다. 

 

Efficiency
Primitive 한 Operation들이 필요하다. Step들은 Machine 에 independent하다. 독립적이라는 것. pseudocode를 작성하면 각각의 line들은 constant time이 걸린다고 가정을 하는 것이다. 그렇다고 동일한 시간은 아니다.

 

Time complexity Analysis
Worst-case를 가지고 보통 Time complexity를 구하게 된다. 최악의 경우 이 최대 이 시간만큼 걸린다는 것이다 . Average case의 경우도 의미 있는데 이는 대부분의 경우에 대한 Time에 대한 서술이므로 공정하게 볼 수 있는 자료가 될 수 있다. Input이 한정된 것이 아니므로 통계학적으로 어떻게 분포가 되어있는지에 따라 다르기 때문이다. Best-case는 의미가 없다. Cheat이라고 표현을 한다. 말로는 존재하지만 알고리즘에서는 존재하지 않는다.

 

Time complexity Analysis
Worst case의 경우 upper bound( 이것보다는 오래걸리지 않어) 를 설정할 수 있다. 어떤 알고리즘의 경우 worst만큼 안좋을 수도 있기 때문. 각각의 Input이 확률적으로 일어날 경우를 고려하기 때문에 수학적인 계산이 필요하게 된다. 

 

Analysis of insertion-sort
8개의 line으로 이루어져 잇고 C1~C8 각각의 시간만큼 시간이 걸린다고 한다. time은 몇 번 실행되는 가를 고려하게 된다. 

 

Analysis of insertion-sort
cost와 time을 곱해서 더하게 된다. 변수는 tj에 해당하는데, Best case의 경우는 한 번만 비교하면서 끝나게 된다. 각각의 While loop에서 한 번씩만 실행하게 되는 경우를 의미한다. 즉 tj = 1일 때를 의미한다. T(n) = O(n) Worst의 경우 비교가 모두 진행되는 경우이다. tj = i 가 되므로 n(n+1)/2이면 O(n^2)가 된다. Average case를 정확하게 구하려면 수학적인 수식이 필요하다. 하지만 대략적으로 생각해보면 n^2/2 의 경우이므로 이 역시 O(n^2)가 된다. Intuition 직관적으로 살펴볼때 나온 수치이다. 

 

Analysis of merge sort
master theorem, Theorem 에 3개의 case가 존재하고 어느 case에 속하는지 구하면 쉽게 선택할 수 있다. Insertion sort와 비교해보면
Time complexity는 빠르다. Merge는 복잡하기 때문에 input size가 작으면 insertion이 좀 더 빠르다. 하지만 점점 커지다보면 mergesort가 
훨씬 빨라진다. 일반적으로 merge가 insertion보다 빠르다고 할 수 잇다.

Recurrence for merge sort
4장에서 다룰 내용

Keyword
문제가 주어지면 Design Paradigm을 결정을 해야 한다. 기존의 Paradigm만을 이용할 필요 없이 창의적으로 구현할 수 있다.
Data Structure를 어떤 것을 사용할지 결정을 하게 된다. 알고리즘을 분석하기 위해서 Correctness를 증명하고 Efficiency를 계산하게 된다.
worst와  Average가 있고 Best case는 고려하지 않을 것이다.