Kim Seon Deok

이진 트리(binary tree) 노드가 왼쪽자식과 오른쪽 자식 만을 갖는 트리 왼쪽 자식과 오른쪽 자식을 구분 완전 이진 트리 루트부터 아래쪽 레벨로 노드가 가득 차있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져있는 이진트리. 높이가 k인 완전 이진 트리가 가질 수 있는 노드의 수는 최대 2(k+1)-1개 이므로, n개의 노드를 저장할 수 있는 완전 이진 트리의 높이는 logn입니다. 이진 검색 트리 왼쪽 서브트리 노드의 키값은 자신의 노드 키값보다 작아야 합니다. 오른쪽 서브트리 노드의 키값은 자신의 노드 키값보다 커야 합니다. 키값이 같은 노드는 복수로 존재하지 않습니다. -구조가 단순하다. -중위 순회의 깊이 우선 검색을 통해 노드값을 오름차순으로 얻을 수 있다. -이진검색과 비슷한 방..

트리 데이터 사이의 계층관계를 표현 루트 트리의 가장 위쪽에 있는 노드 트리 하나에 1개만 존재 리프 = 단말 노드 = 외부 노드 가장 아래쪽에 있는 노드 가지가 더 이상 뻗어나갈 수 없는 마지막에 노드가 있다 >> 자식x 비단말 노드 = 내부 노드 리프를 제외한 노드 자식 어떤 노드와 가지가 연결괴엇을 때 아래쪽 노드 형제 부모가 같은 노드 조상 어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드 자손 어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드 레벨 루트에서 얼마나 멀리 떨어져 있는지를 나타내는 것 가지가 하나씩 아래로 뻗어 내려갈 때마다 레벨이 1씩 증가 차수 각 노드가 갖는 자식의 수 모든 노드의 차수가 n이하인 트리를 'n진 트리'라 한다. 높이 루트에서 가장 멀리 있는 리프..

문자열 검색 어떤 문자열 안에 다른 문자열이 포함되어 있는지 검사하고, 만약 포함되어 있다면 어디에 위치하는지 찾아내는 것 텍스트 : 검색되는 쪽의 문자열 패턴 : 찾아내는 문자열 1.브루트 포스법 = 단순법 선형검색을 단순하게 확장한 알고리즘 문자가 일치하는 동안 차례로 계속 검사. 그러나 다른 문자를 만나면 더이상 검사를 중단하고 다음 인덱스로 패턴의 첫번째문자부터 처음부터 다시 검사를 한다. 단순 알고리즘이나 매우 빠르게 동작한다. # 브루트 포스법으로 문자열 검색하기 def bf_match(txt: str, pat: str) -> int: """브루트 포스법으로 문자열 검색""" pt = 0 # txt를 따라가는 커서 pp = 0 # pat를 따라가는 커서 while pt != len(txt) a..

힙 정렬 힙의 특성을 이용하여 정렬하는 알고리즘 힙에서 최댓값은 루트에 위치한다. 선택 정렬을 응용한 알고리즘 최댓값인 원소를 선택하는 시간 복잡도는 O(n), 힙 정렬에서 다시 힙으로 만드는 작업의 시간 복잡도는 O(logn) 힙 부모의 값이 자식의 값보다 항상 크거나 작다는 조건을 만족하는 완전 이진 트리 두 값의 대소 관계가 일정하면 된다. 부모와 자식관계는 일정하지만 형제 사이의 대소관계는 일정하지 않다. 루트를 삭제한 힙의 재구성 힙에서 루트를 꺼냄 루트 위치의 힙의 마지막 원소(가장 하단의 오른쪽에 위치한 원소)를 비어있는 루트자리로 이동 다음 단계에 있는 자식의 크기를 비교하여 부모의 값이 자식의 값보다 항상 커야 한다는 힙의 조건을 만족시키기 위해 더 큰 자식과 위치를 바꾸고 아래로 내려감..

퀵 정렬 일반적으로 사용되는 아주 빠른 정렬 알고리즘 피벗을 선택하여 나누기를 반복하며 모든 그룹이 1명씩 남으면 정렬이 완료된다. 피벗 : 그룹을 나누는 기준 피벗을 어떤 값으로 선택하느냐에 따라 배열을 나누는 것과 정렬하는 성능에 영향을 미친다. # 퀵 정렬 알고리즘 구현하기 from typing import MutableSequence def qsort(a: MutableSequence, left : int, right: int) -> None: """a[left] ~ a[right]를 퀵 정렬""" pl = left # 왼쪽 커서 pr = right # 오른쪽 커서 x = a[(left + right) // 2] # 피벗 (가운데 원소) while pl x : pr -= 1 if pl None: ..