자료구조 & 알고리즘

Tree, Binary Tree, Binary Search Tree

Tree 트리(Tree)의 기본 개념 트리(Tree)는 그래프의 한 종류로 사이클이 없으며 계층적인 관계를 표현할 수 있는 비선형 자료구조이다. 특징에 따라 트리의 종류를 세분화할 수 있다. 대표적인 트리의 종류로는 이진트리(Binary Tree), 이진탐색트리(Binary Search Tree)가 있다. 트리 관련 용어 부모 노드: 자신과 연결된 노드 중 자신보다 높은 계층에 위치한 노드를 의미한다. 자식 노드: 자신과 연결된 노드 중 자신보다 낮은 계층에 위치한 노드를 의미한다. 루트 노드: 부모 노드가 없는 최상위 계층의 노드를 의미한다. 단말 노드: 자식 노드가 없는 최하위 계층의 노드를 의미한다. 내부 노드: 단말 노드가 아닌 노드를 의미한다. 형제 노드: 부모 노드가 같은 노드들을 의미한다. ..

Hash Table

Hash Table의 특징 해시 테이블(Hash Table)은 Key와 Value를 매핑하여 저장하는 자료구조이다. Key를 통해 대응하는 Value에 빠르게 접근할 수 있는 장점을 가진다. Hash Table의 구성 요소 키(Key) 해시 테이블에 저장된 데이터에 접근하기 위한 입력 값이다. 해싱(Hashing)을 통해 해시(Hash)로 변환된다. 해시 함수(Hash Function) 임의의 길이의 값을 고정된 길이의 값으로 변환하는 함수를 말한다. 해시 함수를 적용하는 것을 해싱이라고 부른다. 해시(Hash) 해싱을 통해 변환된 값을 의미한다. 값(Value) 해시 테이블에 저장되는 데이터를 말한다. 해싱을 통해 키가 해시로 변환되면, 해시와 값이 매핑되어 해시 테이블에 저장된다. Hash 충돌 해시..

Binary Search

이진 탐색(Binary Search) 이진 탐색은 데이터가 정렬되어 있을 때, O(logN)의 시간 복잡도로 목표 데이터를 찾는 알고리즘이다. 재귀함수 또는 반복문을 통해 구현할 수 있다. 이진 탐색 동작 과정 mid(배열의 중간 값)을 target(목표 데이터)과 비교한다. mid > target인 경우, 현재 mid보다 작은 데이터들을 대상으로 새로운 mid를 선정하고 다시 target과 비교한다. mid < target인 경우, 현재 mid보다 큰 데이터들을 대상으로 새로운 mid를 선정하고 다시 target과 비교한다. 위와 같은 과정을 반복하다가 mid == target인 경우, mid를 반환하고 탐색을 종료한다. 이진 탐색 예시 코드 public class BinarySearch { /** *..

최소 신장 트리(Minimum Spanning Tree)-Kruskal

크루스칼(Kruskal) 최소 신장 트리(MST: Minimum Spanning Tree) 신장 트리(Spanning Tree) 신장 트리는 그래프의 모든 정점이 간선으로 연결되어있고, 사이클이 없는 그래프를 말한다. 최소 신장 트리(MST: Minimum Spanning Tree) 최소 신장 트리는 그래프의 가능한 신장 트리들 중 비용의 합 최소인 신장 트리를 말한다. 최소 신장 트리를 구할 수 있는 알고리즘으로는 크루스칼, 프림 알고리즘이 있다. 크루스칼(Kruscal) 크루스칼은 그래프의 간선들을 하나씩 연결하면서 최소 신장 트리를 완성해나가는 알고리즘이다. 연결할 간선을 선택함에 있어서 그리디한 방법을 사용한다. 간선의 수가 적을 때 효율적인 알고리즘이다. 시간 복잡도는 O(ElogE)이다. 구현..

서로소 집합(Disjoint Set)-Union-Find

Union-Find 서로소 집합(Disjoint Set) 서로소 집합은 상호 배타적인 집합들을 말한다. 즉 공통 원소가 없는 집합들을 말한다. 한 그래프에서의 서로소 집합은 서로 연결되지 않은 부분 그래프들이라고 볼 수 있다. Union-Find 서로소 집합은 서로 다른 두 집합을 병합하는 연산(Union or Merge)과 원소가 어떤 집합에 속해 있는지 확인하는 연산(Find)을 기반으로 표현할 수 있다. 따라서 서로소 집합을 표현하는 알고리즘을 Union-Find 또는 Merge-Find라고 부른다. Union-Find는 Tree를 사용하여 구현할 수 있다. Union-Find의 용어 부모는 각 원소가 가르키고 있는 원소를 말한다. 대표는 각 집합을 대표하는 원소를 말한다. Tree의 루트노드라고 ..

최단 경로(Shortest Path)-Dijkstra

다익스트라(Dijkstra) 다익스트라는 가중 그래프의 출발 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이다. 음의 가중치가 있는 경우, 다익스트라는 사용할 수 없으며, 벨만-포드, 플로이드-워셜 알고리즘을 사용해야한다. 음의 가중치가 없는 경우, 다익스트라가 다른 두 알고리즘보다 더 빠르다. 초기 모델은 O(V^2)의 시간 복잡도를 가졌지만, 우선순위 큐를 이용하면 O(Elog V)의 시간 복잡도로 개선할 수 있다. 다익스트라는 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘에 기반한다. 방문하지 않은 정점 중 가장 비용이 적은 정점을 선택한다(그리디). 정점들을 방문하면서 출발지로부터의 최단 거리를 갱신한다(다이나믹 프로그래밍). 구현 방법 최단 경로 업데이트를 위해 노드 수 만큼 dp ..

그리디(Greedy)

그리디(Greedy) 그리디 알고리즘은 최적의 해를 구하기 위해 사용되는 근시안적인 방법론으로 '각 단계에서 최적이라고 생각되는 해를 선택'하는 방식으로 전체 단계를 진행하여 최종적인 해에 도달하는 알고리즘이다. '전체 문제를 부분 문제로 쪼개고, 부분 문제의 해를 통합해 전체 문제의 해를 구한다'는 점에서 완전 탐색 및 동적 프로그래밍과 유사하다. 하지만 각 단계에서 모든 선택지를 고려해보는 다른 두 방법과는 달리, 그리디는 각 단계에서 최적의 선택지만을 고려한다. 따라서 그리디는 전체 문제에 대한 최적해를 보장하지는 않지만, 최적해의 근사치를 보다 빠른 속도로 구할 수 있으며, 경우에 따라 최적해를 구할 수도 있다. 그리디 알고리즘의 정당성 증명 알고리즘 문제는 대부분 최적해의 근사치가 아닌, 최적해..

BFS

BFS BFS(Breadth-First Search)는 루트 노드 또는 임의 노드에서 시작해서 가까운 거리에 있는 노드부터 먼저 탐색하는 완전 탐색 방법의 하나이다. BFS의 특징 선입선출의 자료구조인 큐를 통해 구현된다. 그래프에 대한 BFS를 구현할 경우 어떤 정점을 방문했는 지 여부를 반드시 검사해야 무한 루프를 방지할 수 있다. 시간 복잡도 그래프의 구현 방법에 따라 시간 복잡도에 차이가 있다. N은 정점의 수, E는 간선의 수이다. 인접 리스트로 표현된 그래프: O(N+E) 인접 행렬로 표현된 그래프: O(N^2) BFS를 사용하기 좋은 상황 그래프의 모든 정점을 방문하는 것이 목적인 경우 두 정점간의 최단 거리와 관련된 문제를 해결하는 것이 목적인 경우 BFS의 그래프 탐색 과정 시작 정점을 ..

DFS

DFS DFS(Depth-First Search)는 루트노드 또는 임의의 노드에서 시작해서 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 완전 탐색 방법의 하나이다. DFS의 특징 DFS는 스택 프레임의 알고리즘으로 구현되기 때문에 재귀 함수 또는 스택 자료구조를 통해 구현할 수 있다. 트리의 전위 순회, 중위 순회, 후위 순회 모두 DFS의 한 종류이다. 그래프에 대한 DFS를 구현할 경우, 어떤 정점(노드)를 방문했는 지 여부를 반드시 검사해야 무한 루프를 방지할 수 있다. 시간 복잡도 그래프의 구현 방법에 따라 시간 복잡도에 차이가 있다. N은 정점의 수, E는 간선의 수이다. 인접 리스트로 표현된 그래프: O(N+E) 인접 행렬로 표현된 그래프: O(N^2) DFS를 사용하기 좋은 상황 ..

Graph

그래프의 특징 그래프(graph)는 정점(vertex = 노드(node))와 간선(edge)로 구성된 자료구조이다. 그래프는 간선이 정점들을 잇는 형태로 구성된다. 그래프의 종류 그래프는 간선의 형태에 따라 무향 그래프(undirected graph)와 방향 그래프(directed graph)로 구분된다. 무향 그래프 무향 그래프는 간선에 방향이 없는 그래프를 의미한다. 무향 그래프에서 간선으로 이어진 정점은 방향에 상관없이 서로에게 이동할 수 있다. 방향 그래프 방향 그래프는 간선에 방향이 있는 그래프를 의미한다. 방향 그래프에서 간선으로 이어진 정점은 간선의 방향대로만 이동할 수 있다. 그래프의 구현 방법 그래프를 구현할 수 있는 대표적인 방법으로는 인접 행렬(adjacency matrix)과 인접 ..