자료구조 & 알고리즘/알고리즘

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를 사용하기 좋은 상황 ..