위상 정렬(Topology Sort)  위의 위키피디아 문서를 참조하면, 위상 정렬이란 정점의 선형 순서 지정을 통해 모든 방향 간선 uv에 대해 정점 u가 v보다 앞에 올 수 있게 정렬하기 위해 사용되는 알고리즘으로, 방향성 비순환 그래프 - DAG(Directed Acyclic Graph)에만 적용할 수 있다고 한다.     쉽게 말하자면 순서가 정해져 있는 작업을 차례로 수행해야할 때 순서를 결정해주는 알고리즘이고,더 쉽게 말하자면, 순서를 찾아주는 알고리즘이다.  특징나열한 정렬 순서만 두 가지 경우가 존재하고 추가로 여러 개의 답이 더 존재할 수 있다. 이처럼 위상 정렬은 여러 개의 답이 존재할 수 있다는 특징이 있다. 순회하는 방법이 한 가지보다 많을 수 있기 때문이다. 또한, 위에서 DAG에..

크루스칼 알고리즘 (Kruskal Algorithm)크루스칼 알고리즘(Kruskal Algorithm)이란 최소 신장 트리(Minimum Spanning Tree)를 찾기 위해 사용되는 알고리즘이다. 신장 트리(Spanning Tree)그래프 내의 모든 정점을 포함하는 트리 최소 신장 트리(Minimum Spanning Tree)신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리   최소 신장 트리를 찾기 위해 모든 간선을 가중치에 따라 오름차순으로 정렬하는 아이디어를 사용하여 효과적으로 MST를 구할 수 있게 된다.세부적인 구현 방법은 다음과 같다. 1. 모든 간선을 가중치에 따라 오름차순 정렬한다.2. 간선을 하나씩 선택하여 사이클이 생기지 않을 때 연결하여 모든 노드가 연결될 때 까지 반복한..

LIS(최장 증가 부분 수열)N크기의 배열이 주어졌을때, 배열에서 일부 원소를 조합하여 만든 부분 수열 중, 오름차순의 조건을 만족하면서 길이가 최대인 부분 수열을 말한다. 아래처럼, {3, 6, 2, 1, 7, 8, 5, 4, 9}의 배열이 있다면, LIS는 {3, 6, 7, 8, 9} 이다  DPLIS 문제는 각 요소를 포함하는 증가하는 부분 수열의 최대 길이를 찾는 문제로 이를 효율적으로 해결하기 위해 동적 계획법을 사용한다.단일 배열 내에서, 이전 인덱스의 숫자와 비교하여 증가시켜주면 되기 때문에 DP로 문제를 해결할 수 있다.단일 배열이라는 점만 제외하면 LCS와 유사한 매커니즘이기에, 점화식도 비슷한 방법으로 구현할 수 있다.   [알고리즘] LCS (Longest Common Subseque..

벨만-포드 알고리즘은 그래프의 최단 경로를 구하는 알고리즘의 하나로, 다익스트라로 해결하지 못하는 음의 간선이 포함된 문제를 효과적으로 해결할 수 있는 알고리즘이다.  [알고리즘] 다익스트라(Dijkstra) 알고리즘다익스트라(Dijkstra) 알고리즘그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다. 탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로,mag1c.tistory.com   다익스트라 vs 벨만-포드백준 웜홀 문제의 2번 예시로 그래프를 그려보았다. 우리가 눈으로 보았을 때, 실제 1에서 1까지의 최단경로는 0이 아니라 한 바퀴를 돌았을 때, 무한히 -2의 가중치를 계속해서 더하는 경로이다. 1에서 3의 최단경로 또한 1에서 3까지의 ..

LCSLongest Common Subsequence는 최장 공통 부분 문자열로, Substring의 값을 구하는 것이 아니라연속되지 않은 부분 문자열 중 가장 긴 공통 문자열을 찾는 알고리즘이다. 반대로, Longest Common Substring은 비슷하지만 부분 문자열이 아닌, substring이 되는 문자열이다. 예를들어 ABCDEF, BCDFQQ라는 문자열이 주어지면Longest Common Subsequence는 BCDF가 되고Longest Common Substring은 BCD가 된다.  LCS의 길이를 구할 때는 DP(Dynamic Programming)를 통해 메모제이션으로 효율적인 문제 해결이 가능하다.   점화식char[] w1 = word1.toCharArray();char[] w..

다익스트라(Dijkstra) 알고리즘그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다. 탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로, 음의 가중치(음의 값)가 없어야한다.음의 가중치가 존재하게 되면, 최소 비용의 음의 무한대값이 생성될 수 있으며 그리디 알고리즘을 적용할 수 없다. 인접 행렬로 표현된 그래프의 경우 O(n^2)의 복잡도를 가지며, 우선순위 큐를 사용하여 시간복잡도를 O(m logn)까지 낮출 수 있다.  매커니즘(1) 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택한다 (그리디)(2) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다 (DP)  예시https://mag1c.tistory.com/451 [백준 1916번..

서론 Upper Bound, Lower Bound는 이진탐색을 활용한 알고리즘이다. [알고리즘] 이진탐색(이분탐색) - Binary Search Binary Search 정렬된 데이터 집합을 이분화 하면서 탐색하는 방법 정렬되어 있어야 한다 보통 세 개의 변수를 지정해 두고 (ex : left, mid, right) 찾고자 하는 값, 즉 mid의 값이 찾아낸 값보다 크면 mid는 mag1c.tistory.com 백준에서 이진탐색을 활용한 문제를 풀다가, 깔끔하게 풀리지 않아서 풀고 난 뒤 다른 분들의 코드나 설명을 참조했더니, 내가 사용했던 조건들이 Upper Bound라는 것을 알게되었고, 정리하고자 포스팅을 진행한다. [백준 1654번 / JAVA] 랜선 자르기 문제 링크 https://www.acm..

서론올해 초부터 어느정도 적당한 난이도 이상의 코딩테스트들에 응시하고 있는데,항상 5번문제는 MST관련 문제가 나왔다. 조금만 변형되어도 풀기가 애매해질 정도로 얕은 정도로만 학습을 한 상태였기 때문에, 복기를 위해 관련된 것들을 학습하려고 한다.   Union FindDisjoint Set(서로소 집합)을 관리하는 데 사용되는 알고리즘으로, 각 집합의 대표 요소를 통해 집합을 식별한다. 대표 요소를 해당 집합의 부모라고도 부르며, 루트로 표현된다. 일반적으로 작은 번호를 부모로 정하는데, 이는 트리의 높이를 최소화하여 연산의 효율성을 높일 수 있다. 여러 노드가 존재할 때, union과 find 연산을 수행한다.Union : 노드를 연결Find : 특정 노드의 루트 노드를 찾음   예제 원소ABC부모A..