복습용

이 챕터는 2-(0)에서 알아본 Heap의 성질과 그 연산들을 통해 어떻게 효율적인 Sorting을 구현할 수 있는지 알아본다. 우선, 원래 있는 배열을 Heap으로 만든다. 이것이 2-(0)에서 말했듯이 BuildHeap과정인데, 이것이 n time걸리는 것을 저번 글에서 알아보았다. 이제 해야할 일은 계속 최대인 원소를 뽑는 것이다. 우선, 처음으로 만든 Heap을 생각해보자. 그러면 그 Heap에서 최대인 원소, 즉 배열의 맨 뒤로 가야할 원소는 현재 배열의 제일 첫번째 원소인 root node에 존재한다. 따라서 이 root node와 마지막 node를 swap해준다. 그 다음 마지막 노드는 더 이상 Heap의 일종으로 생각하지 않는다. 이러면 이제 바뀐 root입장에서 양 옆 tree는 Heap..

2-(0)에서는 이후 알고리즘들에 적용될 자료구조들에 대한 기본 내용을 다룰 생각이다. 그냥 자료구조를 좀 빼놓는 것이 좋을 것 같아 이렇게 둔다. 해당 단원은 시간 분석을 제외하고는 다른 부분들을 윤성우 저자의 열혈 자료구조에서 가져왔다. 다른 곳에도 설명이 잘 나와있지만 PQ(Priority Queue)와 Heap에 관한 설명이 잘 나와있었기 때문이다. 물론 열혈은 C로 되어있어서 코드는 내가 C++로 작성했다. PQ는 원소들이 우선 순위를 가진 채 Queue에 들어가는 자료구조를 얘기한다. Queue에 자료를 넣을 떄 우선 순위를 고려하여 위치를 정한다고 생각하면 될 것이다. 이런 Queue는 그냥 구현하면 삽입의 위치를 찾기 위해 worst case에 n-time 비교를 해야할 수도 있다.(앞부터..

이 챕터에서는 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은 사용 경험이 거의 없기 때문에 그 쪽 코드는 비효율적일 수 있음. 모든 내용을 다 다루지는 않을 수 있음