본문 바로가기

CS 이론

 (6)
탐욕 알고리즘 (Greedy Algorithm) 탐욕 알고리즘 (Greedy Algorithm) 탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법이다. 일반적으로, 머리 속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다. 여러 경우 중 하나를 선택할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 각 선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여 그것이 최적이라는 보장은 없다. 일단, 한번 선택된 것은 번복하지 않는다. 이런 특성 때문에 대부분의 탐욕 알고리즘들은 단순하며, 또한 제한적인 문제들에 적용된다. 최적화 문제(optimization)란 가능한 해들 중에서 가장 좋은(최대 또는 최소) 해를..
힙(Heap) 힙(Heap) 힙 : 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조 최대 힙(max heap) 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리 부모 노드의 키 값 > 자식 노드의 키 값 루트 노드 : 키 값이 가장 큰 노드 최소 힙(min heap) 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리 부모 노드의 키 값 < 자식 노드의 키 값 루트 노드 : 키 값이 가장 작은 노드 힙 연산 - 삽입 힙 연산 - 삭제 힙에서는 루트 노드의 원소만을 삭제할 수 있다. 루트 노드의 원소를 삭제하여 반환한다. 힙의 종류에 따라 최대값 또는 최소값을 구할 수 있다.
이진 탐색 트리(Binary Search Tree) 이진 탐색 트리(BST : Binary Search Tree) 탐색 작업을 효율적으로 하기 위한 자료구조 모든 원소는 서로 다른 유일한 키를 갖는다. key(왼쪽 서브트리) 루트 노드의 키 값) : 루트 노드의 오른쪽 서브트리에 대해서 탐색연산 ..
이진 트리(Binary Tree) 이진 트리 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리 각 노드가 자식 노드를 최대한 2개 까지만 가질 수 있는 트리 : 왼쪽 자식 노드(left child node), 오른쪽 자식 노드(right child node) 이진 트리의 예 이진 트리 - 특성 레벨 i에서의 노드의 최대 개수는 2^i개 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개, 최대 개수는 (2^(h+1) - 1)개 이진 트리 - 종류 포화 이진 트리(Full Binary Tree) 모든 레벨에 노드가 포화상태로 차있는 이진 트리 높이가 h일 때, 노드의 개수가 (2^(h+1) - 1)인 이진 트리 높이가 3일 때 노드의 개수 : 2^(3+1) - 1 = 15개 루트를 1번으로 하여 2^(h+1) -..
병합 정렬(Merge Sort) - Merge Sort 기본 개념 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 정복 (cnoquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합 (combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다. - 소스 코드 def merge_sort(arr, n): if n == 1: return arr # 분할(divide) : 부분 리스트 나누기 mid = n // 2 left_arr = arr[:mid] right_arr = arr[mid:] # 정복(conquer) : 각 부분 리스트 재귀적으로 병합 정렬 sorted_left..
트리(Tree) 트리의 개념 비선형 구조 원소들 간에 1:n 관계를 가지는 자료구조 원소들 간에 계층고나계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조 트리 - 정의 한 개 이상의 노드로 이루어진 유합 집합이며 다음 조건을 만족한다. 노드 중 최상위 노드를 루트(root)라 한다. 나머지 노드들은 n(>=0)개의 분리집합 T1, ..., Tn으로 분리될 수 있다. 이들 T1, ..., Tn은 각각 하나의 트리가 되며(재귀적 정의) 트리의 부트리(sub tree)라 한다. 트리 - 용어 정리 노드(node) 트리의 원소 트리 T의 노드 : A, B, C, D, E, F, G, H, I, J, K 간선(edge) 노드를 연결하는 선 부모 노드와 자식 노드를 연결 루트 노드(..

티스토리툴바