donghunkang

Greedy algorithm지역 최적화를 위한 탐욕적인 접근 방식으, 전체적으로 최적의 해답을 찾는 것이 목표이다.항상 최적의 해답을 보장하지는 않지만, 많은 상황에서 효과적으로 작동한다. Feasible(실현가능성)문제의 제약 조건을 만족해야 한다.Locally optimal(지역최적성)각 단계에서 가능한 모든 선택 중 가장 좋은 선택을 해야한다.이러한 지역적인 선택이 전체적으로 최적의 해답을 제공하는 경우 문제는 최적의 부분 구조를 갖는다. Irrevocable(돌이킬 수 없음)한 번 선택한 것은 알고리즘의 이후 단계에서 되돌리 수 없다.단순하고 매력적이지만 최적의 해답을 제공하지는 않는다.  EX)0-1 배낭 문제- 도둑이 n개의 아이템이 있는 상점을 털려고 합니다.- 각 아이템은 v[i] 달러의..

-LCS(Longest Common Substring)(최장 문자열)​

Dynamic programming(동적 프로그래밍): 부분 문제의 해를 결합하여 문제해결->각 부분문제를 단 한번만 풀고 그 해를 저장​-Rod cutting(막대 자르기)2. Dynamic programming: 다시 계산하지 않고 저장Top-down-> 둘 다 Θ(n^2)/ bottom-up:이중 중첩 루프/ top-down: 크기가 0,1,...n에 대한 하위문제를 한 번만 해결, 크기가 n인 부분문제를 풀기 위해 for루프 n번 반복 ​-Matrix-Chain Multiplication​

-Direct-access tables: 배열의 인덱스로 바로 접근하는 방식장점: 배열의 인덱스에 O(1)으로 바로 접근/ 단점: 공간을 많이 낭비​-Resolving collisions by chaining: : 각 인덱스에 할당된 것이 값이 아니라 키와 값을 가진 LinkedList(연결리스트)로 추가적인 공간을 활용하는 것-Choosing hash functions1. Division method: 간단하고 빠름, 해시테이블 크기가 결정되야 함2. Multiplication method:-Resolving collisions by open addressing: 충돌 발생시, 인접한 다른 비어있는 해시 버킷을 찾아 삽입하는 방법/테이블에 1개의 해시와 1개의 값이 매칭INSERT & SEARCH : ..

각 입력 크기 n에 대해 하나의 트리트리에는 가능한 모든 명령어 트레이스에 따른 비교가 포함알고리즘의 실행시간 = 이동한 경로의 길이최악의 경우 실행시간 = 트리의 높이-> lower bound for decision tree: -counting sort: 시간복잡도 O(n+k) - 비교정렬 아니다배열 내의 원소 값들의 객수를 저장하는 counting array 만든다.2. counting array(c[])의 요소들에 대해서 직전 요소들 값을 더함3. 입력배열과 동일한 크기의 출력배열(b[])을 만들고 입력배열의 역순으로 채움-Radix sorting: 시간복잡도 O(dn) - 정렬할 숫자의 자리수(d)일의자리->십의자리->백의자리 순으로 정렬장점: 큰입력에 대해 빠르고 코딩 및 유지 관리가 뛰어남단점..

-Quick sort(퀵 정렬): 시간 복잡도 O(nlgn)->일반적으로 merge-sort보다 2배이상 빠름/캐싱이나 가상메모리에서도 잘 작동worst-case recursion tree/ almost-best case

-Asymptotic notationBig-O notation (점근적 상한)(asymptotic upper bound)f(n)의 복잡도는 최악의 경우라도 g(n) 보다 작거나 같다는 의미입니다. (f(n) ≤ g(n))->알고리즘 성능이 최악의 경우라도 g(n) 이상이라는 의미​ 2. BIg-Ω notation (점근적 하한)(asymptotic lower bound)f(n)의 복잡도는 최선의 경우라도 g(n) 보다 크거나 같다는 의미입니다. (f(n) ≥ g(n))->알고리즘 성능이 아무리 빨라도 g(n) 이하라는 의미3. Big-Θ notation (점근적 상한 및 하한)(asymptotic tight bound)f(n)의 복잡도가 최선의 경우나 최악의 경우라도 g(n) 범위 내에 있다는 의미입니다..