[Algorithm Week_3] Recursion Recursion - 자기 자신을 호출하는 구조? - 알고리즘 설계 & 문제해결의 필수 Recursion의 예 1) Factorial 2) 자료구조 (LinkedList & Binary Tree) LinkedList Null은 List이다 어떤 A가 List이면, A앞에 노드.. cs-ssupport.tistory.com "Fn은 n번째 피보나치 수" ▶ 1-(b) Solution 1-(a)에서 "추상적인 문제"를 묘사했다면 여기서 "해당 문제에 대한 Algorithm | 점화식"을 설계해야 한다 DP에서 점화식없이 문제를 해결할 수가 없다 2. Build Solutions to your recurrence from the bottom up 정의한 Pr..

Stable Sort 정렬 방식 상당히 간단한 정렬 알고리즘이다. 그냥 인접한 두 수끼리 크기를 비교해서 왼쪽값이 오른쪽값보다 크면 서로 exchange해주면 된다 이렇게 정렬하면 매번 정렬할 때마다 최댓값은 알아서 오른쪽에 순차적으로 정렬된다 43 1 25 9 16 ▶ Round 1 43 1 25 9 16 1 43 25 9 16 1 25 43 9 16 1 25 9 43 16 1 25 9 16 43 ▶ Round 2 1 25 9 16 43 1 25 9 16 43 1 9 25 16 43 1 9 16 25 43 Java Code static void bubble_sort(int [] list, int n){ for(int i = n - 1; i >= 0; i--){ for(int j = 0; j < i; j..

Stable Sort 정렬 방식 - 두번째 값부터 차례대로 해당 값을 넣을 위치를 전체적인 배열의 자리에서 결정해준다 >> 선택한 값의 "앞에 요소들"을 살펴보고 만약 앞에 요소들 중 자신보다 큰 값이 있다?? 그러면 앞에 요소들을 차례대로 오른쪽으로 shift 해준다 9 17 1 2 12 6 ▶ Round 1 (index 1) 인덱스 0 1 2 3 4 5 요소 9 17 1 2 12 6 - "index(1) 17"앞에는 "9"라는 값이 있다 - 9는 17보다 작다 - 따라서, 여기서는 shift 해줄 필요가 없다 ▶ Round 2 (index 2) 인덱스 0 1 2 3 4 5 요소 9 17 1 2 12 6 - insert하려는 기준 값 = "index(2) : 1" - 해당 값 이전의 요소들을 알아봐야 ..

Unstable Sort 정렬 방식 - 정렬되지 않은 요소들에 대해서 일단 가장 좌측을 최솟값의 index라고 생각 9 17 1 2 12 6 ▶ Round 1 (index 0) 인덱스 0 1 2 3 4 5 요소 9 17 1 3 12 6 정렬 여부 X X X X X X - 정한 index 다음 요소들로부터 진짜 최솟값 index를 찾아내기 (계속해서 index를 update해준다) 인덱스 0 1 2 3 4 5 요소 9 17 1 3 12 6 정렬 여부 X X X X X X - 진짜 최솟값의 index는 "2"니까 index(2)의 값과 index(0)의 값을 서로 교체 인덱스 0 1 2 3 4 5 요소 1 17 9 3 12 6 정렬 여부 O X X X X X - 이러면 0번째 요소는 정렬 완료 ▶ Round..

Union-Find Algorithm - Disjoint Set을 표현할 때 사용하는 알고리즘 Disjoint Set - 각 집합들에 대해 서로 공통 원소가 없는 집합 :: 서로소 집합 자료구조 트리 구조를 사용하면 가장 효율적으로 구현할 수 있다 최소 힙과 비슷하게 root를 가장 작은 값으로 설정해주면 편리하다 Union-Find 연산 (1) init-set(x) - 각 node들을 본인의 번호로 초기화 번호 1 2 3 4 5 6 root 1 2 3 4 5 6 (2) union(x, y) - x가 속한 집합과 y가 속한 집합을 합친다 ex) (1, 3) (2, 4, 5, 6) 합치기 - 합치고, 각자 번호를 해당 tree의 root번호로 변경해준다 바로 위의 부모 node로 변경하는게 아니라 최종적인..

호제법 두 수가 서로 상대방 수를 나눠서 결국 원하는 수를 얻는 알고리즘 두 수 A, B의 최대공약수를 G라고 하면 A = Ga / B = Gb → A를 B로 나누면 (A≥B라고 가정) A = BQ + R → Q : 몫, R : 나머지 Ga = GbQ + R R = G(a-bQ) ≫ G는 A를 B로 나눈 나머지의 약수 Example A : 20 / B : 55 → GCD(A, B) 20%55 = 20 → GCD(55, 20) 55%20 = 15 → GCD(20, 15) 20%15 = 5 → GCD(15, 5) 15%5 = 0 → GCD(5, 0) → B가 0이 되는 순간 알고리즘 종료 → 최종 최대공약수 = A Java Code static int GCD(int A, int B){ if(B==0) ret..

최단경로 - 정점 i ~ 정점 j까지 간선들의 weight 합이 최소가 되는 경로 Dijkstra 하나의 시작 정점 ~ 모든 다른 정점까지의 최단 경로 Floyd 모든 정점 ~ 다른 모든 정점까지의 최단 경로 Dijkstra Algorithm - 탐욕적 방법 (greedy method) 이용 - 특정 시작 정점 ~ 다른 모든 정점까지의 최단 경로 계산 - 가중치가 음수가 아닐 때 정상적으로 작동 - Dijkstra → Greedy → DP(최단경로 + 길찾기) / 매 상황에서 가장 비용이 적은 최선의 정점 선택 - 시작정점으로부터 거리를 저장하는 distance[] 1차원 배열이 필요 - O(n²) 시작 정점(v) 선택 시작 정점으로부터 다른 모든 정점까지의 distance 업데이트 (한 번에 갈 수 없..