Algorithm/KBro Study

투포인터 알고리즘 리스트나 배열에 순차적으로 접근해야 할 때, 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 1. 원리 1. 시작점과 끝점이 첫번째 원소의 인덱스를 가르키도록 한다. 2. 목표값 보다 시작점 인덱스부터 끝점의 인덱스까지의 결과값이 작으면 끝점(end)를 1 증가시킨다. 3. 목표값 보다 시작점 인덱스부터 끝점의 인덱스까지의 결과값이 크거나 같으면 시작점(start)를 1 증가시킨다. 4. 모든 경우를 확인할 때가지 2~3번 과정을 반복한다. 2. 예제 예제를 통해 알아보자. 투포인터 알고리즘의 대표적인 문제인 특정한 합을 가지는 부분 연속 수열 찾기로 알아보자. 아래와 같은 수열이 있다. 여기서 연속되는 수의 합이 5 일때의 개수를 구해보자. 투포인터 알고리즘을 사용하면 다음과 같은 ..

1. LCS란? Longest Common Subsequence의 약자이며, 두 문자열을 비교할 때 공통적으로 나타나는 부분 순서들 중 가장 긴 것을 말한다. 예를 들어, 'ABCBDAB'와 'BDCABA'의 LCS를 구해보면 ABCBDAB BDCABA => 'BCBA'가 나오게 된다. 그리고 LCS는 최적화를 해야 하는 문제이기 때문에, 동적계획법(DP)를 사용하여야 가장 효율적으로 구할 수 있다. 1-1. 접근 방법 & 예시 두 문자열 'GCABCD' 그리고 'ABDCED'가 주어졌을 때, LCS를 구하는 진행과정은 다음과 같다. 위 그림에서 확인할 수 있듯이, {GCA}, {GCAB}, {GCABC}, {GCABCD}와 {A}를 비교하면 공통 수열이 1임을 알 수 있다. 위 그림은 {ABDCED} ..

1. DP란? DP(Dynamic Programming)은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로, 이미 했던 연산이 반복되는 결점을 보완하기 위해서 고안되었다. 피보나치 수열에서 사용되는 일반적인 재귀 방식도 DP와 매우 유사하지만, 일반적인 재귀 방식은 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수도 있다는 것이다. Dynamic Programming 문제를 풀기 위한 방법에는 Top-Down과 Bottop-Up 방식이 있는데, 아래에서 알아보겠다. 2. Dynamic Programming 구현 2-1 Top-Down 방식 Top-Down 방식이란 재귀 함수로 다이나믹 프로그래밍을 구현하는 방식이며, 말 그대로..

1. 벨만포드(Bellman-Ford) 알고리즘이란? 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘 + 음수 사이클 존재 여부를 알 수 있음 다익스트라와는 달리 가중치에 음수가 있어도 사용 가능 시간복잡도: O(NE) (N:노드의 수, E:엣지의 수) 다음과 같은 그래프가 있다고 가정 다익스트라로 노드 1에서 모든 노드로의 거리를 구하면 1 -> 2 = 1 1 -> 2 ->3 = 2 1-> 2 ->3 ->4 = 4 가 되고 노드 2는 이미 방문했기 때문에 4 ->2 경로는 고려하지 않음 결과적으로 1 -> 2의 최단경로는 1이 됨 하지만 실제 1 -> 2의 최단경로는 -∞ 임 이를 해결하기 위해 벨만포드 알고리즘 탄생 2. 알고리즘 동작 원리 시작 정점을 선택한다. 모든 간선들을 탐색하면서..

그리디(Greedy) 알고리즘 들어가기에 앞서, 그리디 알고리즘에 대해 간략히 알아보자. 그리디(탐욕) 알고리즘 이란? => 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 알고리즘이다. = 탐욕 알고리즘 빠르지만, 항상 최적인 답이라는 보장은 없다. Union-Find 알고리즘 Disjoint-set(서로소 집합)을 표현하기 위해 사용하는 알고리즘 ex) {1,2} {3,4} → 서로소, {1,2} {2,3} → 서로소 아님 (1). Union 2개 원소로 이루어진 집합을 하나의 집합으로 합치기 ex) {1} + {2} → {1,2} (2). Find 특정 원소가 속한 집합이 뭔지 알려주는 연산 ex) Find({ {1,2,3}, {4,5}, {10} }, 2) → {1,2..