728x90
✔️ LCS란? LCS는 Longest Common Subsequence의 약자로, 번역하면 최장 공통 부분 문자열이라고 할 수 있다. LCS는 LIS(Longest Increasing Sebsequence, 최장 증가 부분 수열)와 같이 DP(Dynamic Programming)를 기반으로 한다. 부분 문자열이라는 개념에는 Substring이라는 개념과 Subsequence라는 개념이 있다. Substring은 연속된 부분 문자열을 확인하는 개념이고, Subsequence는 연속되지 않은 부분 문자열을 찾는 개념이다. 이 둘의 차이점은 연속 여부이다. 예를 들어 ABCDHEF를 봐보자. 최장 공통 문자열(Substring)의 길이는 3, 최장 공통 부분 문자열(Subsequence)의 길이는 5가 나오..
문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 계단을 ..
구간 합 구하기 4 출처 : 11659번: 구간 합 구하기 4 (acmicpc.net) 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 나의 풀이 : #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int N, M; cin >> N >> M; vector dp(N + 1); dp[0] = 0; for (int i = 1; i > num; dp[i] ..
문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두..
다익스트라(Dijkstra) 알고리즘이란 무엇인지, 단순하게 MinHeap 구조 없이 구현하는 방법은 다익스트라(Dijkstra) 알고리즘이란?에서 확인할 수 있다. 위의 글의 소스코드 처럼 단순하게 다익스트라를 구현할 수 있지만, 이러한 경우 시간복도가 O(N^2)로 형성된다. 그러나 가장 저렴한(min값 인) 경유지를 선택할 때 다익스트라에 Min Heap을 사용하면, 성능을 더 높일 수 있고, 이때 시간복잡도가 O(NlogN)으로 형성된다. MinHeap은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은, 즉 항상 가장 작은 값이 루트(root)에 존재하는 이진 트리이다. 실제로 여러 다익스트라 문제에서 MinHeap을 사용하지 않고 단순히 구현했을 때 시간 초과가 발생하는 경우를 직면할 ..
다익스트라(Dijkstra) 알고리즘은 재귀호출 없이 다이나믹 프로그래밍을 이용하여 최단거리(최소비용)을 구하는 알고리즘이다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 계산한다. DP(Dynamic Programming)으로 분류되는 이유는 하나의 최단 거리를 구할 때, 그 이전까지 구했던 최단 거리 정보를 그대로 사용하기 때문이다. 단, 음의 간선(가중치)이 있는 경우에는 사용할 수 없는 알고리즘이다. 다익스트라 알고리즘의 원리 다음과 같은 규칙을 반복하면 최소 비용을 구할 수 있다. 가장 저렴하게 갈 수 있는 곳을 경유지로 선택한다. 선택된 경유지를 거쳐 다른 곳으로 이동할 때, 더 저렴한 지 확인한다. 더 저렴하다면, 최소비용 전광판 result에 갱신한다. 다익스트라 알고리즘의..