1. Greedy Algorithm?- 매 순간 국소적인 최적해를 찾는 과정을 반복함으로써 전체 문제에 대한 해를 찾는 문제 해결의 한 패러다임- Greedy Algorithm으로 얻은 해가 전체 문제에 대해 반드시 최적의 해라는것을 항상 보장 불가 2. Greedy Algorithm의 최적해를 가질 때2.1. ex 1) 거스름 돈(각각의 동전들이 배수관계)https://www.acmicpc.net/problem/11047n, k = map(int,input().split())cost = list(int(input()) for _ in range(n))cnt = 0 for _ in range(n): p = cost.pop() cnt += k//p k = k%pprint(cnt) 3. 결론..
Introduction to Algorithms
1. Intro- CLRS에서의 13챕터는 Red-Black Tree에 대해서 서술한다.- 하지만, 나는 AVL Tree(13-1) -> Red-Black Tree(13-2) -> LLRB Tree(13-3) 순으로 포스팅하고자 한다.- 이 순으로 이해해야 비교적 순조롭게 이해가 가능하다. 2. AVL Tree?- AVL Tree는 스스로 균형을 잡는 BST이다. 즉, BBST의 한 종류라고 생각하면 된다.- 한쪽으로 편향을 가진 이진트리가 되는 것을 방지해준다. 3. AVL Tree 특징I) AVL Tree는 BST의 속성을 가진다.II) left subtree와 right subtree의 높이 차이가 최대 1이다. --> Balance Factor의 절댓값이 1이하이다.--> Balance Facto..
1. Binary Search Tree?- 이진 탐색(Binary Search)의 개념을 트리 형태의 구조에 점목한 자료구조- 각 노드 키가 왼쪽 서브트리에 있는 키들보다 크고, 오른쪽 서브트리에 있는 키들보다 작다.- 일반적으로 키값이 같은 노드는 복수로 존재하지 않아야 한다. 2. BST의 구조- 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.- 노드의 오른쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.- 루트의 왼쪽 서브트리와 오른쪽 서브트리는 BST이다. 3. BST CODE구현3.1. BST에 사용되는 클래스 class Node: def __init__(self, key, value): self.key = ke..
1. Counting Sort?- Counting Sort는 정수로 표현할 수 있는 데이터에 대해 효율적으로 작동하는 O(n) 정렬 알고리즘.- 정렬의 대상이 되는 데이터 값의 범위가 명확할 때 주로 사용.- Counting Sort는 비교 정렬 알고리즘이 아닌 분포 정렬 알고리즘이다. 2. Counting Sort 알고리즘i) 입력 배열과 범위 설정- 주어진 입력 배열이 A라고 하고, 배열의 길이를 n이라고 하자.- 데이터 값은 0 이상 k이하인 양수라고 가정해보자. (이때 k == max(A)) ii) 카운트 배열 초기화- C라는 배열을 만들고, 길이를 k+1로 설정 (또는 max(A) - min(A)로 설정)- C[i]는 입력 배열에서 값이 i인 요소가 몇 번 등장하는지 저장함- C의 초기값은 전..
