Falling in Love with Coding

깊이 우선 탐색(Depth-First Search:DFS) - 바이너리 트리를 순회할 때 사용하는 방법의 inorder, preorder, postorder를 사용 - 인접 노드를 타고 인접 노드가 없을 때까지 도달 후 다시 거슬러 올라오며 순회 Stack을 이용하여 구현 스택에 시작 노드를 넣어준 후 방문처리(Visited) 한다. 스택의 노드 하나를 꺼낸다(Pop). 꺼낸 노드가 인접(Adjacent) 노드가 있으며 방문하지 않았다면, 스택에 넣어준 후(Push) 방문처리한다. 스택이 비워질 때까지 2, 3번 과정을 반복한다. Recursion(재귀호출)을 이용한 구현 시작 노드를 먼저 방문처리 후 인접 노드를 방문한다. 방문한 인접 노드를 방문처리 후 인접 노드가 있다면 차례로 방문한다. 방문할 인..

유향 비순환 그래프(Directed Acyclic Graph, DAG) - 순환이 없도록 설계된 방향성을 가진 그래프이다. - 즉 어떤 정점이든 1회만 접근 가능하도록 비순환적(Acyclic)으로 만들어진 그래프이다. - 수학, 컴퓨터, 과학 등 여러분야에서 사용하는 용어이며, 높은 처리량에 우수하여 사물 인터넷과 소액 결제와 같은 많은 영역에서 활용될 수 있다. - 따라서 어떤 선행되어야 하는 것이 있는 경우를 표현할 때 유용하다. 위상정렬(Topological Sort) - DAG의 정점들을 순서화하기 위한 정렬, 즉 DAG 위에서만 동작 가능 - 우선순위를 표현하기 위해 사용하는 정렬 알고리즘 - 일반적으로 시간복도는 O(V + E)를 갖는다. DAG를 활용한 최단경로, 최장경로 - 위상순서 위에 ..

선택 알고리즘이란? - n개의 원소가 불규칙하게 저장된 배열에서 i 번째 작은 원소(또는 큰원소)를 찾는 문제를 해결하기 위한 알고리즘 - 정렬과 비슷하다고 할 수 있음 - 두 가지 알고리즘 ㄴ 평균적으로 선형시간이 소요되는 알고리즘 ㄴ 최악의 경우에 선형시간이 소요되는 알고리즘 평균 선형시간 선택 알고리즘 - 퀵 정렬처럼 분할한 후 자기호출 방법을 이용하여 평균적으로 선형시간에 i번째 작은 원소를 찾는 것 - 배열 A에서 i 번째 원소 찾기 1) 원소가 하나뿐인 경우, 그 하나를 리턴 2) 원소가 다수인 경우, 먼저 파티션을 통해 중간값이 몇 번째인지 확인 3) 중간값이 i와 같을 경우, A[파티션을 통해 얻은 중간] 값을 리턴 4) 중간값이 i 보다 클 경우, 오른쪽 그룹으로 범위를 좁혀 재귀적으로 ..

KD-트리 1) 이진검색트리를 확장 · k(k≥2)의 필드로 이루어진 키 사용 · 각 레벨에서 필드를 번갈아가며 검색에 사용 - 한 레벨에서는 하나의 필드만 사용 - 총 k개의 필드를 사용하는 검색이라면, k개의 레벨을 내려가면 검색에 사용하는 필드가 일치 - 기준 노드의 값과 비교 노드의 값으로 노드의 위치를 결정 - A의 x값을 기준으로 B는 왼쪽, C는 오른쪽에 위치 - B의 y값을 기준으로 D는 왼쪽, E는 오른쪽에 위치 - C의 y값을 기준으로 F는 오른쪽에 위치(크거나 같을 경우라면) - D의 x값을 기준으로 G는 왼쪽에 위치 2) KD-트리 검색 - 임의의 키가 입력되면, 각 필드를 차례대로 사용해서 트리를 검색 3) KD-트리 삽입 - 검색하듯이 트리를 따라 내려가다 리프 노드를 만나면 거..

정렬의 개요 1. 실행 방법에 따른 분류 1) 비교식 정렬과 분산식 정렬 - 비교식 정렬(Comparative Sort) ▪ 비교하고자 하는 각 키 값들을 한번에 두 개씩 비교하여 교환하는 방식으로 정렬을 실행하는 방법 - 분산식 정렬(Distributive Sort) ▪ 키 값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하고, 각 부분 집합을 정렬함으로써 전체를 정렬하는 방식으로 실행하는 방법 2. 정렬 장소에 따른 분류 1) 내부 정렬과 외부 정렬 ① 내부 정렬(Internal Sort) ▪ 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식 ▪ 정렬 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한됨 ▪ 내부 정렬 방식 ② 외부 정렬(External Sort) ▪ ..

2-3-4 트리 1. 개요 - 2-3-4 트리의 정의 ▪ O(log2N)과 O(log4N) 사이의 탐색 효율을 가짐 ▪ 추가로 4-노드를 정의 - 자식 노드로 가는 링크(Link)가 4개이고 키가 3개인 노드 - 왼쪽 자식(Left Child), 오른쪽 자식(Right Child), 왼쪽 중간 자식(Left Middle Child), 오른쪽 중간 자식(Right Middle Child)으로 구분 - 2-3-4 트리의 노드 구성 2. 2-3-4 트리의 필요성 1) 2-3-4 트리의 장단점 ▪ 높이를 log4N으로 조금 더 낮추기 위함 ▪ 리프 노드 근처의 널 포인터 공간도 2-3 트리에 비해서 더 많아짐 ▪ 필요시 최대 3개의 키를 비교해야 하는 시간적 부담 2) 단일 패스 삽입 ▪ 2-3 트리는 리프 노..

2-3트리 개요 - 2-3트리의 특징 ▪ AVL은 균형 트리를 지향하는 반면 2-3 트리는 완전 균형 트리를 지향함 ▪ AVL 트리에 비해 상대적으로 단순한 논리 ▪ 2-노드 또는 3-노드 모두 가능 ▪ 이진 탐색 트리와 마찬가지로 리프 노드에 삽입 - 삽입 시 높이 변화의 특성 * 2-3트리 ▪ 반복된 삽입에도 2-3 트리의 높이는 좀처럼 증가하지 않음 ▪ 3-노드를 사용해서 최대한 많은 레코드를 높이 변화 없이 수용 * 이진 트리 ▪ 이진 탐색 트리의 높이는 삽입할 때마다 리프 노드 아래로 1만큼 증가 - 여러 가지 방법 ▪ 삽입, 삭제를 위해서는 삽입 대상 노드의 부모 노드를 접근해야 함 ▪ 삽입 시에 중간 키를 올리기 위해서, 또 삭제 시에 부모 노드의 키를 아래로 내리기 위해서 이진 트리는 부모..

AVL 트리의 개요 1. AVL의 균형 1) 균형 인수(Balance Factor) ▪ 트리의 균형을 점검할 때 사용하는 인수 ▪ 노드 마다 오른쪽 서브 트리의 높이에서 왼쪽 서브 트리의 높이를 뺀 것 ▪ AVL 트리에서 균형 인수의 값은 반드시 -1, 0, +1 중 하나임 2) 균형 인수의 점검 ① 왼쪽 트리로부터 노드 K를 삭제하면 균형 인수 중 -2가 생겨 오른쪽 트리처럼 균형이 깨지게 됨 ② 왼쪽 트리에서 노드 F의 오른쪽 자식에 삭제가 가해졌다면 루트 F를 기준으로 오른쪽 서브 트리의 높이가 감소하게 됨 ③ 삭제로 인해 어떤 노드의 균형 인수가 범위를 벗어난 경우 : 균형이 깨진 노드는 삭제 위치의 부모 노드(F)의 왼쪽 자식 노드와 손자 노드까지 가는 길목에 있는 F, D, E 중에 존재하게 ..

히프 트리 구조 1. 히프의 개요 1) 정의 ▪ 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조 ▪ 최대 히프(Max Heap) - 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리 - {부모 노드의 키 값 ≥ 자식 노드의 키 값} - 루트 노드: 키 값이 가장 큰 노드 ▪ 최소 히프(Min Heap) - 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리 - {부모 노드의 키 값 ≤ 자식 노드의 키 값} - 루트 노드: 키 값이 가장 작은 노드 2) 히프 트리 예 3) 히프의 추상 자료형(ADT Heap) ▪ 데이터 : n개의 원소로 구성된 완전 이진 트리 ▪ 각 노드의 키 값은 그의 자식 노드의 키 값보다 크거나 같음 - 부모 노드..

탐색 연산 1. 탐색 연산의 기본 방법 - 연산 방법 ▪ 루트에서 시작함 ▪ 탐색할 키 값 x를 루트 노드의 키 값과 비교함 * 키 값 x = 루트 노드의 키 값 인 경우 => 원하는 원소를 찾았으므로 탐색 연산 성공 * 키 값 x 루트 노드의 왼쪽 서브 트리에 대해서 탐색 연산 수행 * 키 값 x > 루트 노드의 키 값 인 경우 => 루트 노드의 오른쪽 서브 트리에 대해서 탐색 연산 수행 ▪ 서브 트리에 대해서순환적으로 탐색 연산을 반복함 2. 탐색 연산 알고리즘 1) 이진 탐색 트리에서의 탐색 연산 알고리즘 searchBST(bsT, x) p ← bsT; if (p = null) then return null; if (x = p.key) then return p;..