오식랜드

Greedy Method 탐욕적인 알고리즘 최적화 문제 해결에 용이 : 최대, 최소를 구하는 문제 ( “가장 ~~한 것”을 고르는 문제) 결정의 순간 가장 좋다고 생각하는 것을 선택 ⇒ 번복 X ! 결정의 순간에는 가장 좋았다고 해도 최종 해답에서는 좋지 않을 수 있다. 최적의 해를 주는지 반드시 검증해줘야 한다! 과정 선정 과정 (selection procedure) : 최단 거리 / 최소 시간 등의 기준을 잡고 그에 맞추어 선택 적정성 점검 (feasiblity check) : 새로 구한 해답이 적절한지 점검. 적절하다면, solution set에 포함시킨다 해답 점검 (solution check) : 해답 모음이 최적의 해인지 결정한다 solution = null for i=1 to n do // ..

정렬 알고리즘 합병 정렬 (Merge sort) : O(nlogn) 퀵 정렬 (Quick sort) : O(n^2) 립 정렬 (Heap sort) : O(nlogn) 합병 정렬 (Merge sort) 입력을 2개의 부분 문제로 분할하며 크기가 1/2 씩 감소하는 분할 정복 알고리즘(DC) 이다 정렬이 안되어있는 배열 S를 비내림차순으로 정렬하는 과정 S를 반으로 나누어 A와 B로 명명 나눠진 배열을 각각 정렬 (이 때 A가 끝날 때 까지 B는 정렬하지 않음) 배열이 1개씩 남을 때 까지 반복 (분할) A와 B에 각각 비내림차순 정렬 A와 B의 앞 index의 수를 비교하며 병합 진행 (정복) 시간 복잡도 최선의 경우 : A와 B가 이미 정렬이 이미 되어있던 경우 ⇒ A번 또는 B번 최악의 경우 : 모든 ..

DC : Divaide-and-Conquer Divaide and Conquer : 분할정복식 분할 : 최대한 작게 문제를 분해 정복 : 나눈 문제를 각각 해결 통합 : 필요 시 해결한 문제를 합침 ⇒ 재귀적 방법으로 해결 (분할-정복 반복) ⇒ top-down 접근 방법이라고도 한다 (반대는 bottom-up) top-down (하향식) 접근 소프트웨어 개발 시 기능 / 구조 위주로 바라본다 모듈 단위의 관점 문제를 나누어 구체화 유지보수가 어렵다 절차지향적 프로그래밍에 사용 분할정복 설계 bottom-up (상향식) 접근 소프트웨어 개발 시 데이터를 위주로 바라본다 객체 단위의 관점 데이터들 간의 상호관계를 정의하며 해결 유지보수가 쉽다 객체지향적 프로그래밍에 사용 상호관계 정의 설계 Divaide ..

점근적 표기 입력 크기(n)가 무한대로 커질 때의 복잡도를 간단히 표기하기 위한 표기법 보통은 다항식이나 간단한 함수로 표기 복잡도의 상한선을 표기 Big-Oh 충족 조건 cf(n) ≥ g(n) c > 0 n ≥ 1 타이트한 값으로 설정 cf(n^2)이나 cf(n^3)도 g(n) 보다 클테지만, 타이트한 cf(n)을 사용 다양한 표기법 Big-Oh : 상한선 오메가 : 하한선 세타 : 빅오-오메가 사이에 속하는 식

logn < n < nlogn < n^2 < n^3 < 2^n < n! 분석 입력 크기에 따라, 단위 연산이 몇 번 수행되는지 결정하는 절차 사용하는 자료구조에 좌우되는 경우도 있다. 표현 척도 단위 연산 : 비교 / 지정 입력 크기 : 배열의 크기 / 리스트의 길이 / 행과 열의 크기 / 트리의 노트와 연결선의 수 분석 방법 최선의 경우 (Best-case) : 단위 연산 수행 횟수가 최소인 경우 잘 안 쓴다. ex) 순차검색의 x가 제일 처음에 위치하면 T=1 최악의 경우 (Worst-case) 단위 연산 수행 횟수가 최대인 경우 대부분 최악의 경우로 구한다. ex) 순차검색의 x가 제일 마지막에 위치하면 T=n 평균의 경우(Average-case) (최선+최악)/2 로 계산 최악의 경우보다 계산이 ..

피보나찌 수 구하기 피보니찌 재귀 함수의 한계를 설명하기 좋음 n(n ≥ 2)의 피보나찌 = (n-2) + (n-1) 1. 재귀적 방법으로 피보나찌 수 구하기 n-1과 n-2의 값이 1 또는 0이 될 때 까지 fib 함수가 재귀적으로 호출된다. int fib(int n) { if (n 2 x T(n - 2) → 왜냐하면 T(n - 1) > T(n - 2) > 2^2 x T(n - 4) > 2^3 x T(n - 6) … 2n/2 x T(n-n) = 2n/2xT(0) = 2^n/2 결론 재귀적 알고리즘으로 구성한 재귀 트리의 노드 수를 T(n)이라 하면, n2인 모든 n에 대하여 T(n)> 2n/2 이다. ⇒ 매우 느림 이유: 같은 피보나찌 수를 중복 계산 2. 반복적 방법으로 피보나찌 수 구하기 int ..