알고리즘/분할 정복(DivideConquer) (3) 썸네일형 리스트형 [알고리즘] 분할 정복 피보나치 - 코딩밥상 피보나치(Fibonacci) 구하는 방법 피보나치 수열이야 고등학생부터 흔하게 접했었던 수열이기에 설명을 각설하고, 이를 일반적인 방법으로 구현하고 분할 정복을 기반으로 다시 한번 구현해보겠습니다. 피보나치 수열의 정의가 다음과 같으므로 일반적인 구현은 전혀 어렵지 않습니다. 재귀 방정식을 그대로 코드로 옮길 수 있기 때문입니다. long Fibonacci(int n){ if(n==0) return 0; if(n==1 || n==2) return 1; return Fibonacci(n-1) + Fibonacci(n-2); } 하지만 이 코드는 하나의 호출이 재귀 호출로 또 다른 2개를 호출 하기 때문에 O(2^n)의 성능을 나타냅니다. 이는 최악의 성능이라고 볼 수도 있죠. 20번째 피보나치를 찾기 위해.. [알고리즘] 분할 정복 거듭 제곱 계산 - 코딩밥상 거듭 제곱(Exponentiation) 계산 거듭 제곱은 컴퓨팅에서 자주 사용되는 연산 중 하나입니다. 하지만 일반 산술 연산과 달리 의외로 수행시간이 오래 걸리는데, 이 문제를 분할 정복으로 해결할 수 있습니다. 먼저 거듭 제곱의 계산법을 살펴보면 C^n 을 계산 하려면 C*C*C*...*C 와 같이 C자신을 n번 곱해야 합니다. 지수의 크기만큼 곱셈을 수행하므로 O(n)의 수행 시간을 소요하는 것입니다. long Poewr(int Base, int Exponent){ int Result = 1; for(int i=0; i [알고리즘] 병합 정렬(Merge Sort) - 코딩밥상 병합 정렬(Merge Sort)이란? 병합 정렬은 앞서 배운 퀵 정렬과 같이 분할 정복에 기반한 알고리즘으로 성능도 퀵 정렬만큼 우수합니다. 이는 직역한 그대로 '나누고 조건에 맞게 합치는' 알고리즘입니다. 간략하게 동작 방식을 정리하자면, 정렬할 데이터를 반으로 나눈다 나뉜 하위 데이터의 크기가 2 이상이면 이 하위 데이터에 대해 첫번째 과정(반으로 나눔)을 반복한다 동일 데이터에서 나뉜 하위 데이터 둘을 병합하여 원래대로 하나의 데이터로 만든다. 단, 병합할 때 데이터의 원소는 정렬 기준에 따라 정렬한다 데이터가 원래대로 모두 하나가 될 때까지 세번째 과정(병합)을 반복한다. 이 병합 정렬을 구현할 때 두 하위 데이터를 병합하는 부분에 관심을 더욱 기울여야 합니다. 병합하는 과정이 성능을 좌우하기 때.. 이전 1 다음
