Algorithm/알고리즘 정리

[알고리즘] LCS(Longest Common Subsequence) 알고리즘이란?

✔️ LCS란? LCS는 Longest Common Subsequence의 약자로, 번역하면 최장 공통 부분 문자열이라고 할 수 있다. LCS는 LIS(Longest Increasing Sebsequence, 최장 증가 부분 수열)와 같이 DP(Dynamic Programming)를 기반으로 한다. 부분 문자열이라는 개념에는 Substring이라는 개념과 Subsequence라는 개념이 있다. Substring은 연속된 부분 문자열을 확인하는 개념이고, Subsequence는 연속되지 않은 부분 문자열을 찾는 개념이다. 이 둘의 차이점은 연속 여부이다. 예를 들어 ABCDHEF를 봐보자. 최장 공통 문자열(Substring)의 길이는 3, 최장 공통 부분 문자열(Subsequence)의 길이는 5가 나오..

[알고리즘] 다익스트라(Dijkstra) 알고리즘 : MinHeap 사용

다익스트라(Dijkstra) 알고리즘이란 무엇인지, 단순하게 MinHeap 구조 없이 구현하는 방법은 다익스트라(Dijkstra) 알고리즘이란?에서 확인할 수 있다. 위의 글의 소스코드 처럼 단순하게 다익스트라를 구현할 수 있지만, 이러한 경우 시간복도가 O(N^2)로 형성된다. 그러나 가장 저렴한(min값 인) 경유지를 선택할 때 다익스트라에 Min Heap을 사용하면, 성능을 더 높일 수 있고, 이때 시간복잡도가 O(NlogN)으로 형성된다. MinHeap은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은, 즉 항상 가장 작은 값이 루트(root)에 존재하는 이진 트리이다. 실제로 여러 다익스트라 문제에서 MinHeap을 사용하지 않고 단순히 구현했을 때 시간 초과가 발생하는 경우를 직면할 ..

[알고리즘] 다익스트라(Dijkstra) 알고리즘이란?

다익스트라(Dijkstra) 알고리즘은 재귀호출 없이 다이나믹 프로그래밍을 이용하여 최단거리(최소비용)을 구하는 알고리즘이다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 계산한다. DP(Dynamic Programming)으로 분류되는 이유는 하나의 최단 거리를 구할 때, 그 이전까지 구했던 최단 거리 정보를 그대로 사용하기 때문이다. 단, 음의 간선(가중치)이 있는 경우에는 사용할 수 없는 알고리즘이다. 다익스트라 알고리즘의 원리 다음과 같은 규칙을 반복하면 최소 비용을 구할 수 있다. 가장 저렴하게 갈 수 있는 곳을 경유지로 선택한다. 선택된 경유지를 거쳐 다른 곳으로 이동할 때, 더 저렴한 지 확인한다. 더 저렴하다면, 최소비용 전광판 result에 갱신한다. 다익스트라 알고리즘의..

[알고리즘] MST(최소신장트리), 크루스칼(Kruskal) 알고리즘이란?

✔️ MST란? MST는 Minimum Spanning Tree의 약자로, 그래프에서 최소 비용으로 모든 구간을 연결한 Tree(최소 신장 트리)를 말한다. 무향 연결 가중 그래프에서 간선의 가중치의 합이 최소인 신장(Spanning) 트리(Tree)이다. MST의 특징 MST는 Tree이기 때문에, Cycle이 존재하면 안된다. 따라서 신장 트리는 정점의 갯수가 n개일 때, 간선이 n-1개가 된다. 답은 여러개가 될 수도 있다. ✔️ 크루스칼(Kruskal)이란? 크루스칼(kruskal) 알고리즘은 MST를 구하는 대표적인 알고리즘이다. 크루스칼 알고리즘의 시간복잡도는 O(nlog𝑛)이다. 여기서 n은 연결되는 간선의 수를 의미한다. Kruskal 알고리즘의 과정 가중치 값을 기준으로 정렬(sort) ..

[알고리즘] Union Find(서로소 집합)란?

✔️ Union Find란? Union Find(서로소 집합)는 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고할 수 있다. Union Find 자료구조를 사용하면 각 Data들이 같은 그룹에 속해있는지, 다른 그룹인지 확인할 수 있다. 즉 서로소 집합은 교집합이 공집합인 집합(서로 집합)들의 정보를 확인(Find)하고, 조작(Union)할 수 있는 자료구조이다. 그렇다면 왜 Union Find 자료구조를 사용할까❔ Data들이 어떤 조직에 속하는지 관리하기 쉬우며, 빠른 속도로 조직을 통합 처리 가능하다. ✔️ Union Find 자료구조의 조직 관리 방법 같은 트리에 묶여있으면 같은 그룹이라고 간주한다. 아래 트리에서 (A,B,C,D) (E,F,G) (H,I) 는 그룹이다...