JUINTINATION

최소 신장 트리(MST)란? 가중치 그래프에서 사이클 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리 즉, 어떤 가중치 그래프의 신장 트리 중 선분들의 가중치 합이 최소인 트리 신장 트리는 그래프에서 사이클 없이 모든 점들을 연결시킨 트리로 주어진 그래프의 신장 트리를 찾으려면 사이클이 없도록 모든 점을 연결시키면 된다. 신장 트리는 그래프에서 사이클 없이 모든 점들을 연결시킨 트리로 그래프의 점이 n개 있다면 신장 트리에는 n-1개의 선분이 있다. 다음 예시에서 왼쪽 그림의 그래프의 최소 신장 트리는 오른쪽 그림의 그래프와 같다. MST를 찾기 위한 알고리즘 최소 신장 트리를 찾는 대표적인 그리디 알고리즘으로는 크루스칼 알고리즘(Kruskal's Algorithm)과 프림 알고리..

해시 테이블이란? 해시 함수를 사용하여 입력 키 값으로부터 해시 값을 얻어 그것을 인덱스로 사용하여 효율적인 검색 방식을 제공하는 자료구조 원소가 저장될 자리가 원소의 값에 의해 결정됨 매우 빠른 응답을 요하는 경우에 유용하게 사용됨 ex) 주민 등록 시스템과 같은 호출 번호 관련 검색 해시 함수 해시 함수를 적용하여 입력 키값으로부터 해시 값을 얻었을 때 입력 원소가 해시 테이블에 골고루 저장되어야 한다. 계산이 간단해야 하며 대표적으로 나누기 방법과 곱하기 방법이 있다. 나누기 방법(Division Method) h(x) = x mod m m: 해시 테이블 사이즈, 보통 소수로 지정 곱하기 방법(Multiplication Method) h(x) = (xA mod 1) * m A: 0

서로소 집합(Disjoint Set)이란? 공통 원소가 없는 두 집합, 즉 A∩B=∅을 만족시키는 두 집합 A, B를 서로소 집합이라고 한다. 유니온 파인드(Union-Find)란? 서로소 집합에 대한 연산을 할 때 사용하는 알고리즘이다. 쉬운 이해를 위해 다음의 예시를 보자. https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 위의 문제처럼 초기에 n+1개의 집합 {0}, {1}, {2}, ... , {n}이..

힙이란? 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 다음과 같은 규칙을 갖는 완전이진트리를 기본으로 한 자료구조 A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다. 힙에는 두가지 종류가 있다. 최대 힙: 부모노드의 키 값이 자식노드의 키 값보다 항상 큰 힙 최소 힙: 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙 대부분의 경우는 자식노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 루트 노드에 오게 되는 특징이 있음 이를 응용하여 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다. 힙의 주요 연산 최소 힙을 기준으로 힙의 주요 연산은 다음과 같다. ..

트리란? 계층적(Hierarchical)인 구조를 나타내는 비선형 자료구조 나무를 뒤집어놓은 모양과 닮았다고 해서 붙여진 이름 부모-자식 관계의 노드들로 이루어진다. ex) Decision Tree(의사 결정 트리) in AI 리스트, 스택, 큐 등은 선형 구조 트리 용어 노드(node): 트리의 구성요소 루트(root): 부모가 없는 노드(A) 서브트리(subtree): 하나의 노드와 그 노드들의 자손들로 이루어진 트리 단말노드(terminal node): 자식이 없는 노드 비단말노드(leaf node): 적어도 하나의 자식을 가지는 노드 레벨(level): 트리의 각층의 번호 높이(height): 트리의 최대 레벨 차수(degree): 노드가 가지고 있는 자식 노드의 개수 A는 루트 노드이다. B는 ..

그래프(Graph)란? 연결되어 있는 객체 간의 관계를 표현하는 자료구조 그래프 G는 (V, E)로 표시 정점(vertices) 여러 가지 특성을 가질 수 있는 객체 노드(node)라고도 불림 간선(edge) 정점들 간의 관계 링크(link)라고도 불림 DFS란? 깊이 우선 탐색(depth-first search)한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이 곳으로부터 다른 방향으로 다시 탐색 진행 스택(Stack)을 사용하거나 재귀함수 사용 # 재귀함수를 사용한 DFS depth_first_search(v): v를 방문되었다고 표시; for all u ∈ (v에 인접한 정점) do if (u가 아직 방문되지 않았으면) then depth_first_..