Algorithm

[백준] 1563번: 개근상(Java)

Notion에 정리한 글을 옮긴 것입니다. 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net 문제 풀이 완전탐색을 이용해야하지만, 완전탐색만 사용한다면 경우의 수가 O(3^1000)의 시간복잡도가 발생한다. 그래서 재귀적 접근(DFS) + dp ⇒ dp의 bottom-up방식을 사용하여 풀었다. 이 문제의 핵심은 점화식을 찾는 것인데, 간단한 예를 통해 알아보자. 한 학기를 3일이라고 하자. 지각(late)는 2일 이상이면 안되고, 결석(absent)은 연속 3일 이상이면 안된다. dp[idx][late][absent] 3..

[알고리즘] 투포인터(Two Pointer) 알고리즘

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

[알고리즘] LCS(최장 공통 부분 수열) & LIS(가장 긴 증가하는 부분 수열)

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} ..

[알고리즘] Dynamic Programming(동적 계획법)

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

[알고리즘] 벨만포드 알고리즘 (Bellman-Ford)

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. 알고리즘 동작 원리 시작 정점을 선택한다. 모든 간선들을 탐색하면서..