기록기록 우는 갈매기

퀵 정렬 알고리즘이란? 선정된 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); // 오른쪽 ..

합병 정렬 알고리즘이란? 크기가 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..

이진탐색 알고리즘이란? 크기가 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의 핵심은 재귀호출이다. 전체를 풀 때와 부분을 풀 때의 풀이가 같은 경우 큰 문제를 작은 문제로 쪼개서 해결하는데, 이 때 top-down 방식과 bottom-up방식이 있다. top-down: 처음부터 큰 문제를 방문 후 작은 문제를 호출, 재귀(recursive)방식 사용 bottom-up: 작은 문제들부터 해결 후 이를 바탕으로 더 큰 문제들을 해결, 반복(iterative) 방식 사용 top-down과 bottom-up 모두 문제를 쪼갠다는 점에서 비슷해보일 수 있지만 시도 자체가 다르다. top-down은 처음부터 큰 문제를 해결하려고 시도하지만, bottom-up은 큰 문제부터 해결하려하지 않고 작은 문제부터 시작한다. divide-and-conquer은 위의..