본문 바로가기

Computer195

[C/C++] C++ Virtual Destructor C++에서 Virtual이 붙은면 이 함수는 부모 클래스든 자식 클래스든 마지막으로 대체되는 함수로 호출이 되는 특성이 있다. 예를 들어 class AA { public: virtual void func(){ cout 2007. 4. 5.
알고리즘의 문제 변환에 대한 짧은 생각 알고리즘에 대한 책들을 보면 대부분이 소팅 문제, 그래프 문제, Dynamic programming, Greedy algorithm등이 나온다. 뭐 기타로 Genetic algorithm이나 Machine learning등에 관련된 내용들도 있기도 하지만 기본적으로는 소팅,그래프의 문제가 기본이라고 할수가 있을 것이다. 어떤 문제를 풀려면 기존에 나와 있는 알고리즘의 어떤 문제에 속하느지를 뭔져 파악하고 그 문제로 변환해보는게 중요하다. 대부분의 문제는 다른 문제로 변환이 가능하다. 이것이 NP문제에 대한 수학/알고리즘 연구자들의 로망을 생겨나게 만들기도 하는데, 어떤 NP문제를 풀면 모든 NP문제를 풀수 있다는 명제가 나오게 되는 이유이다. 예를 들어 무수히 많은 Random한 정수의 입력 값에 대해서.. 2007. 4. 5.
Dynamic programming Dynamic programming은 어떤 상태에서의(n) 최적화된 솔류션 S(n)은 그 전의 최적화된 상태에 의해서 조합될수 있는 경우 적용이 가능하다. 예를 들어 "동전에 숫자가 1,3,5 로 적혀 있을 경우 합이 11인 최소의 동전 개수는?"에 대한 최적의 솔류션은 1. 합이 10인 솔류션 + 숫자1이 쓰여진 동전 1개 2. 합이 8인 솔류션 + 숫자3이 쓰여진 동전 1개 3. 합이 5인 솔류션 + 숫자5가 쓰여진 동전 1개 이 3가지 솔류션중 가장 동전 수가 작은 것의 동전 수가 답이다. 즉 S(11)=MAX(S(10),S(8),S(5))+1 이 된다. 일반적으로 S(n)=MAX(S(n-1),S(n-3),S(n-5))+1 이며 이를 기반하여 위의 예제를 풀어 보면 0. S(0)=0 1. S(1)=.. 2007. 4. 5.
Sorting에 대한 짧은 정리(Linear Time Sorting) 기본적으로 Merge sort, hearpsort 및 quick같은 NlogN 정렬 알고리즘은 입력 값들에 대한 비교(Comparison)에 기반한 방법이다. 이런 Comparison기반의 소팅들은 기본적으로 최악의 경우 NlogN보다 빠를수 없다는게 증명이 되어 있다. 특정 조건이 주어진다면 수행시간은 Linear Time(O(N))으로 줄일수 있다. 대표적인게 Radix sorting이다. Radix Sortting 예를 들어 10진수 기수 10(18,45,37,97,34,65,98,10,72,99)개에 대해서 정렬한다고 하면 먼져 1의 자리에 대해서 각 해당 bucket에 넣고 다시 해당 Bucker에서 뽑아서 자료를 만든다 그러면 10,72,34,45,65,37,97,18,98,99가 나오고 다시.. 2007. 4. 5.
Sorting에 대한 짧은 정리(NlogN, Quick정렬) C. Hoare가 고안, 가장 인기 있는 Sorting으로 일반적으로 속도가 매우 빠르다. 어떤 키 값을 중심으로 (a[i]) 왼쪽으로 부터는 키 값보다 큰 값을, 오른쪽으로 부터는 키 값보다 작은 값을 찾아서 교환하는 방법이다. 1. 기준값(Pivot)을 하나 선택하여 2. 그 기준값보다 작은 항목들은 모두 배열의 왼쪽으로 3. 그 기준값보다 큰 항목들은 모두 배열의 오른쪽으로 4. 왼쪽 부분 배열에 퀵정렬을 재귀적으로 적용 5. 오른쪽의 부분 배열에 퀵 정렬을 재귀적으로 이용 다음 그림은 1,2,3에 대해서 수행하는 그림이다 문제는 Pivot에 따라서 이 알고리즘으 수행 속도가 영향을 받는다, Pivot이 정 중앙 값일 수록 빨라지며, 최악의 경우 O(N^2)까지도 속도가 나올수 있다. Pivot을 .. 2007. 4. 5.
Sorting에 대한 짧은 정리(NlogN, Merge정렬) 5. Merge Sorting Merge정렬도 기본적으로 Divide and Conquor 방법으며 Recursive한 함수 호출 방식으로 구현한다. 아래와 같이 동작하며 수행 시간은 O(NlogN)이다 자바로 구현된 소스는 다음과 같다. public static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) { // base case if (hi - lo 2007. 4. 5.

티스토리툴바