본문 바로가기

전체 글

 (71)
[알고리즘] 동적계획법, Dynamic Programming dynamic programming는 divide-and-conquer와 마찬가지로 재귀적인 속성을 가지고있지만, 더 나아가 최적화 문제를 다룬다는 특징 또한 가지고있다. 최적화 문제란 주어진 문제에 대하여 하나 이상의 많은 해답이 존재할 때 이 가운데에서 가장 최적인 해답을 찾아야 하는 문제를 일컫는다. 따라서 재귀적인 속성에 최적화 문제인 경우 dynamic programming으로 해결하면 된다. dynamic programming은 bottom-up 방식을 이용하여 재귀적인 문제를 해결한다. 즉, 입력 사이즈가 제일 작은 문제부터 해결하여 점점 큰 문제를 해결해나가고, 이 때 나누어진 부분들 사이에는 서로 상관관계가 있다. dynamic programming 과 divide-and-conquer의..
[알고리즘] 퀵 정렬, Quick Sort | 설계 및 분석 퀵 정렬 알고리즘이란? 선정된 pivot값을 기준으로 배열을 나누어가면서 재귀적으로 정렬하는 알고리즘 알고리즘 설계 전략 pivot을 선정한다. pivot 보다 작은 값은 왼쪽, 더 큰 값은 오른쪽에 배치한다. 양쪽 배열에 대해 다시 같은 과정을 반복함으로써 최종적으로 배열을 정렬한다. 알고리즘 수도코드 void quicksort(index low, index high) { index pivotpoint; if(high > low) { partition(low, high, pivotpoint); //배열을 pivot 값을 기준으로 반으로 나눈다. quicksort(low, pivotpoint-1); // 왼쪽 배열에 대해 재귀적으로 정렬 quicksort(pivotpoint+1,high); // 오른쪽 ..
[알고리즘] 합병 정렬, Merge Sort | 설계 및 분석 합병 정렬 알고리즘이란? 크기가 n인 배열을 원소가 하나 밖에 남지 않을 때까지 계속 반으로 쪼갠 후 다시 크기 순으로 정렬 하면서 원래 크기의 배열로 합치는 정렬 알고리즘 알고리즘 설계 전략 배열 원소가 하나 남을 때 까지 배열을 재귀적으로 쪼갠다. (Divide) 쪼개진 배열들을 정렬하면서 다시 합친다. (Conquer) 알고리즘 수도코드 void mergesort(int n, keytype S[]) { if (n > 1) { const int h = ⌊n/2⌋, m= n - h; keytype U[1..h], v[1..m]; //S를 반으로 쪼개 왼쪽은 U에 오른쪽은 V에 저장 copy S[1] through S[h] to U[1] through U[h]; copy S[h+1] through S[n..
[알고리즘] 이진탐색, Binary Search | 설계 및 분석, 구현코드 이진탐색 알고리즘이란? 크기가 n인 정렬된 배열 s에 x가 있는지 결정하는 재귀 알고리즘 알고리즘 설계 전략 배열의 중간에 위치하고 있는 값이 x와 같은 경우 성공을 리턴, 그렇지 않으면 분할(Divide) 분할(Divide) : 배열을 반으로 나누고, x가 배열의 중간에 있는 값보다 작으면 왼쪽 배열을 선택(오른쪽 배열은 버림), 크면 오른쪽 배열을 선택(왼쪽 배열은 버림). 정복(Conquer) : 선택한 배열을 갖고 다시 x를 찾는다. 알고리즘 수도 코드 index location (index low, index high) { index mid; if(low > high) return 0; else { mid = ⌊(low+high) / 2⌋; //배열 가운데 값을 구함 if (x == s[mid]..
[알고리즘] 분할정복, Divide-and-Conquer divide-and-conquer의 핵심은 재귀호출이다. 전체를 풀 때와 부분을 풀 때의 풀이가 같은 경우 큰 문제를 작은 문제로 쪼개서 해결하는데, 이 때 top-down 방식과 bottom-up방식이 있다. top-down: 처음부터 큰 문제를 방문 후 작은 문제를 호출, 재귀(recursive)방식 사용 bottom-up: 작은 문제들부터 해결 후 이를 바탕으로 더 큰 문제들을 해결, 반복(iterative) 방식 사용 top-down과 bottom-up 모두 문제를 쪼갠다는 점에서 비슷해보일 수 있지만 시도 자체가 다르다. top-down은 처음부터 큰 문제를 해결하려고 시도하지만, bottom-up은 큰 문제부터 해결하려하지 않고 작은 문제부터 시작한다. divide-and-conquer은 위의..
[알고리즘] 점근표기법, asymptotic notation | 상한, 하한, 교집합 점근 표기법(asymptotic notation)은 시간 복잡도 또는 공간 복잡도 함수의 증가 양상을 구분하기 위해 사용하는 표기법이다. 대표적으로 상한(O), 하한(Ω), 교집합(Θ)이 있다. 먼저 간략하게 뜻을 말하면 아래와 같다. O(f(n)) : 상한, 아무리 느려봤자 f(n) 정도이다. f(n)보다 빠르거나 같다. Ω(f(n)) : 하한, 아무리 빨라봤자 f(n) 정도이다. f(n)보다 느리거나 같다. Θ(f(n)) : 차수, 상한과 하한을 함께 제시. 두 집합의 교집합 하나 하나 알아보기전에, 앞서 말한 '빠르다', '느리다'라는 표현에 대해 그 뜻을 정리할 필요가 있다. 함수의 차수가 높을수록 더 빠를 것 같지만, 차수가 낮은 것이 더 빠르다고 표현한다. 즉, 그래프 상으로 그렸을 때 더 아..
[알고리즘] 알고리즘 분석, Analysis | 최선, 최악, 평균, 모든 경우 알고리즘을 짰다고해서 끝나는 것이 아니다. 짜긴 짰는데 결과 값을 얻어내기까지 어마어마한 시간을 요구한다면 소용이 없기 때문이다. 따라서 분석을 통해 알고리즘의 효율성을 판단해야한다. 알고리즘의 성능은 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 표현한다. 시간복잡도: 얼마나 빠른가? 공간복잡도: 얼마나 많은 공간을 차지하는가? 우선, 시간 복잡도 측정에 대해 주로 다뤄보도록 하겠다. (공간 복잡도는 나중에 중간중간 나올 예정) 시간복잡도 시간복잡도(Time Complexity)는 알고리즘이 '얼마나 빠른가'를 나타내는 함수이며, 보통 함수 이름으로 T(n)을 사용한다. 즉, n과 T(n)의 관계를 구하는 것인데, 이 때 n은 input size가 된다. 시..

티스토리툴바