복습용

이 챕터에서는 Divide & conquer 방법과 그것을 적용하여 풀이할 수 있는 예제인 maximum-subarray problem을 소개하고 있다. Divide&conquer에 대해서는 1-(2) MergeSort에서 다루었으므로 이 글에서는 문제 소개와 그 풀이만 하도록 하겠다. *이 글의 흐름은 예전에 수강했던 심규석 교수님의 프로그래밍 방법론 수업 흐름을 거의 그대로 활용하였음을 알린다. 책에는 linear time solution이 제시되어있지 않아서 그 부분을 교수님의 강의를 들은 기억을 활용해서 썼다. 문제: 주어진 배열 A[1:n]에 대해 그 subarray A'=A[k:l]을 생각해볼 수 있다.(k>=1,l max_sum) max_sum = arr_sum; } } return max_..

이 단원에서는 알고리즘의 수행시간을 분석하는 방법에 대해 다룬다. 나는 그냥 대충 다루겠다. 알고리즘의 수행 시간은 CPU의 속도, 컴파일러의 성능 등 여러가지에 의해 결정되는 면이 있지만, 그것에 가장 지배적인 영향을 미치는 요인은 알고리즘의 특성이다. 즉, n개의 데이터가 주어지는 문제에서 해당 알고리즘은 몇 번 데이터를 봐야하는가? 가 그 수행시간을 지배적으로 결정한다고 보는 것이다. n개의 데이터가 주어졌을 때 수행시간인 T(n)은 다음과 같은 세 개의 notation에 의해 표현된다. 1. Θ-notation: T(n)의 tight한 수행시간 2. O-notation: T(n)의 upper bound가 될 수 있는 terms 3. Ω-notation: T(n)의 lower bound가 될 수 있..

(2)MergeSort 이 챕터에서는 Sorting의 대표적인 한 방법인 MergeSort에 대해 다루며 그 수행 시간을 분석해본다. MergeSort는 기본적으로 다음과 같은 아이디어에서 시작한다. 이미 정렬되어 있는 두 개의 배열 L[1,...,l]과 R[1,.....,r]이 있다고 해보자. 이 때 L과R 배열을 병합하여 새로운 배열A'을 만든다고 하면, 어떻게 하면 A'을 정렬된 배열로 병합할 수 있을까? 우선 처음A[1]을 생각해보자, 그러면 A[1]에 들어가야 할 원소는 L과 R의 원소를 합쳐놓은 집합에서 제일 작은 원소이다. 이는 L의 최소 원소(L[1])와 R의 최소 원소(R[1])중 더 작은 원소와 같으므로 min(L[1], R[1])이 된다. L[1]이 더 작은 상황이라고 가정해보면 A[..

이 챕터는 알고리즘의 대표적인 문제인 Sorting problem을 통해 이 책 전체의 framework를 제시하는 챕터라고 한다. 그냥 예제를 통해 책의 서술 방법을 말하는 챕터. Sorting problem은 다음과 같이 정의되는 문제이다. (대부분의 알고리즘 문제가 아래와 같은 형식으로 정의된다.) Input: n 개의 연속되는 수들 a1, ...., an Output:a1, ...., an 가 특정 순서에 대해 정렬된 수의 나열 a'1, ...., a'n 이 Sorting problem을 푸는 방법을 Insertion sort와 Merge sort를 통해 제시하고 있다. (1) insertion Sort(삽입 정렬) 책에 나와있지는 않지만 insertion sort는 incremental algo..

해당 단원은 알고리즘의 정의와 그 역활에 대해 서술하는 단원이다. 서술에 의하면, 알고리즘이란 잘 정의된 계산 문제(Well-specified computing problem)에서 input으로부터 원하는 output을 얻어내는 과정의 computational procedure라 얘기하고 있다. 그냥 수학적 문제를 푸는 방법의 수학적 서술이라 생각하면 될 것 같다. 대부분의 사람들이 갖고 있는 insight와 크게 다른 것을 제시하는 것 같지는 않다. 이런 알고리즘의 correctness는 모든 input에 대해 원하는 output을 얻어내는 성질로서 정의되며 알고리즘의 표현은 사람의 언어를 통해 이루어질 수도 있고 컴퓨터 언어를 통해 이루어질 수도 있다. 표현에서 중요한 것은 수학적인 형식으로 명확하게..

MIT 자체 출판 도서인 Introduction to algorithm의 내용 공부한 것을 정리할 예정인 카테고리. 순서는 대략 다음과 같음 (1)교재 내용 정리 (2)해당 내용과 관련된 백준 문제들 풀이 C++로 코드를 작성해서 올릴 생각임. (C++이 제일 손에 익어서) STL은 사용 경험이 거의 없기 때문에 그 쪽 코드는 비효율적일 수 있음. 모든 내용을 다 다루지는 않을 수 있음