개발자

O 분할 정복 기법- 분할 정복순서설명Step 1. Divide문제를 작은 문제로 쪼갠다.Step 2. Conquer문제가 풀 수 있을 만큼 작아지면 문제를 직접 풀고, 그렇지 않으면 문제를 재귀로 푼다. - 구현function F(x): if F(x)의 문제가 간단 then: return F(x)을 직접 계산한 값 else: x를 y1, y2로 변환 F(y1)과 F(y2)를 호출 return F(y1), F(y2)로부터 F(x)를 구한 값 - Merge Sort (예제1)• 과정순서설명Step 1. Divide배열을 절반으로 나눠 서브배열 2개를 만든다.Step 2. Conquer서브배열이 충분히 작으면, 정렬하고 그렇지 않으면 재귀로 정렬한다.Step 3. Combine정렬된 서브배열을 하나의 정렬된..

O 빠른 알고리즘 중요성- 문제 1 : 정렬된 배열에 x 값 찾기=> Sequential Search vs. Binary Search (Worst Case 경우) Array Size(n)Sequential SearchBinary Search128 (2^7)128 (2^7)81024 (2^10)1024 (2^10)111048576 (2^20)1048576 (2^20)214294967296 (2^32)4294967296 (2^32)33 찾는 횟수 - 문제 2: 피보나치 수열=> Recursive vs. Iterative Fibonacci• Recursive Fibonacci 시간 복잡도 : 2^n/2• Iterative Fibonacci 시간 복잡도 : n+1 입력크기(n)입력크기(n+1)입력크기(2^n/2..