복습용

이 단원에서는 Longest Common SubSequence문제와 그 Dynamic Programming 해법에 대해 알아본다. LCS문제를 소개하기 위해 Sequence라는 것을 먼저 정의하자 Sequence는 다음과 같이 주어진 순서있는 집합이다. X= 이 때 X의 subsequence는 다음과 같이 X에 속하는 멤버들을 골라서 만드는 sequence를 얘기한다. , 이 때 LCS문제는 다음과 같이 주어진다. Q:X=, Y=의 common subsequence 중 그 길이가 가장 긴 Subsequence는? input: X,Y output: LCS Z 이 문제는 DP로 풀리는데, 다음과 같은 Thm을 생각해볼 수 있기 때문이다. Thm15.1 X와 Y에서 LCS Z가 주어졌을때 (1) xm=yn인 ..

이 챕터에서는 Dynamic Programming 문제 카테고리에 속하는 Matrix Multiplication 문제에 대해 다뤄보고자 한다. (1)Intuition: 행렬의 연쇄곱 ABCDE같은 것을 생각해보자.(행렬곱이 conformable하다는 것을 가정하고) 이 행렬곱은 (((AB)C)D)E로 계산하든, A(B(C(DE)))로 계산하든, 그 결과는 동일하지만, 하는 연산의 횟수가 동일하지 않다. 우선, mxn행렬 A와 nxr행렬 B를 생각해보면 AB를 계산하는데 걸리는 시간은 mnr이다. (loop를 작성해보면 3중 loop가 보여서 명확히 알 수 있을 것이다.) 또한, 이를 바탕으로 밑의 그림과 같은 예제를 보면 행렬곱의 순서에 따라 연산횟수가 달라지는 것이 명백히 보일 것이다. 따라서 이런 연..

이 챕터에서는 Dynamic Programming이라는 문제 해결 방법에 대해 배운다. Dynamic Programming은 어떤 문제를 해결할 때 sub문제들의 subsub문제가 overlap되는 경우 사용하는 Algorithm기법을 말한다. 책에서는 이 예시로 Rod Cutting문제를 말하고 있는데 Rod Cutting문제란 다음과 같은 문제를 말한다. Q: 어떤 Value를 지닌 통나무(Rod)를 판다고 해보자. 그런데 이 통나무는 길이에 따라 매기는 값이 비례하지 않게 달라진다. 예를 들어 다음 표와 같이 길이에 따른 값이 달라진다. 이 때 주어진 길이 n의 통나무와 값이 담겨있는 배열 p에 대해 이 Rod의 max Price는? Input: 통나무의 길이n, 값이 담긴 배열 p[1:n] Out..

이 챕터에서는 알고리즘 구현을 위해 이용되는 자료구조들 중 내가 잘 모르는 것에 대해서만 알아본다. (1) Stack과 Queue 쉽고 대충 알고 있으니까 안 다룸. array implementation과 linked list implementation둘다 가능. head와 tail정하는 것도신경써서 해야한다는 점만 유의하자. 근데 재미있어 보이는 문제가 있어서 소개한다. 사실 학교에서 자료구조 중간고사때 나왔던 문제 같은데 틀렸다. 근데 여기서 보니까 화가나서 열심히 풀어봤다. 그냥 발상 문제인 것 같다. 재밌는 문제: 두 개의 Stack을 써서 Queue를 만들고 Enqueue와 Dequeue의 Time Complexity를 분석하시오. Stack과 queue는 in과 out이 그 순서가 완전히 반대..

이 챕터에서는 n time안에 끝낼 수 있는 sorting들을 배우는데, 대표적으로 Counting sort를 다뤄보고자 한다. (*책에는 Bucket sort랑 Radix sort도 있음) 우선, 원소들의 대소를 부등호로 비교해가며 정렬하는 비교정렬 방법들은 n time안에 끝낼 수 없다는 것이 알려져있다. 이론적 증명을 보고싶다면 책을 참고하면 된다. 나는 안궁이어서 안 봤다. 그럼 n time안에 끝낼 수 있는 정렬이 있을까? 수의 range가 n에 const하게 비례할 때 n time안에 끝낼 수 있는 정렬로서 Storing Sort가 알려져있는데 다음과 같은 아이디어를 생각해보자. 만약 우리가 정렬하고자 하는 배열에서 어떤 수가 몇 번 나오는지 세어 놓은 자료가 있다면, 그 자료만 가지고도 원래..

이 챕터는 Sorting의 한 방법인 Quick Sort에 대해 배운다. Average case의 Time Complexity 증명은 생략하지만, Worst case n2에 average case nlgn인 알고리즘이라고 생각하면 될 것 같다. worst case의 증명은 쉬우니까 알고리즘을 설명하고 한 번 하고 가겠다. (1) QuickSort Algorithm의 설명 QuickSort algorithm은 다음과 같은 재귀적 알고리즘이다. (i) 배열의 원소 중 하나의 원소를 골라 Pivot으로 선정한다. (-->이 Pivot선정을 Randomize시켜야 average nlgn이 나온다.) (ii)그 Pivot보다 작은 놈들을 Pivot왼쪽에, 큰 놈들을 Pivot오른쪽에 놓는다.(called Part..

이 챕터는 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 비교를 해야할 수도 있다.(앞부터..