개발 블로그

다익스트라(Dijkstra) 알고리즘은 하나의 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘입니다. 플로이드 와샬 알고리즘은 "모든 정점"에서 "모든 정점"으로의 최단 경로를 구하기 위한 알고리즘입니다. 이는 왕복을 고려한다는 뜻입니다. 예시를 들어 1번 정점에서 다른 노드를 거쳐 1번 정점으로 돌아올 때의 최소 비용을 구하기 위해서는 "플로이드-와샬" 알고리즘으로 해결해야 합니다. 다익스트라 알고리즘은 최소 비용을 하나씩 선택해줘야 하는 반면, 플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행한다는 점에서 차이점을 지닙니다. 또한 Greedy한 다익스트라에 비해 플로이드 와샬 알고리즘은 Dynamic 프로그래밍에 속합니다. 또한 모든 정점에서 모든 정점으로 가기 위한 최소비용을 ..

https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 문제에서 주어지는 입력은 N(연주할 곡), S(시작 볼륨), M(최대 볼륨)입니다. 두 번째 입력에서는 연주할 곡의 볼륨입니다. 연주는 P-V[i], P+V[i]의 볼륨으로만 연주해야 하고, 구하고자 하는 결과는 마지막 곡을 연주했을 때의 볼륨의 최댓값입니다. D[i][j]는 i번 곡을 j로 연주할 수 있으면 true, 그렇지 않으면 false를 반환합니다. ..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 주어진 입력은 배낭의 무게(w)와 가치(v)입니다. 배낭의 수용량을 넘지 않으면서 가치의 최댓값을 구하는 문제입니다. 점화식은 다음과 같이 세울 수 있습니다. 물건을 담지 않은 경우 D[i][j] = D[i-1][j] 물건을 담은 경우 D[i][j] = D[i-1][j-w[i]] + v[i] 물건을 담은 경우 에는 수용량과 가치 갱..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 이 문제는 파일을 합치는데 최소 비용을 구하는 문제입니다. 테스트케이스를 예시로 들면, C1, C2, C3, C4의 파일 크기는 각각 40 30 30 50입니다. 파일을 합치는 경우의 수는 총 3가지입니다. (C1), (C2, C3, C4) (C1, C2), (C3, C4) (C1, C2, C3), (C4) 1번 경우에는 C2 + C3 = 60, C2 + C3 + C4 = 60 + 50 ..

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 이 문제는 기존 팰린드롬(Palindrome)과 유사한 문제입니다. 주어진 수열이 있는데, 시작 인덱스, 끝 인덱스를 입력받고 이 수열이 팰린드롬이면 1을 출력, 그렇지 않으면 0을 출력하는 문제입니다. 팰린드롬은 길이가 1이면 무조건 팰린드롬이고, 2이면 하나만 비교해 주면 됩니다. 이제, 길이가 3인 경우에는 i(첫번째 인덱스), j(마지막 인덱스)에서 인덱스를 하나씩 늘리고(시작 인덱스), 줄여나가면서(마지막 인덱스) 배열 값이 ..

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 이 문제는 예전에 풀기도 했었고, 보자마자 DP가 떠올랐습니다. 상담으로 얻을 수 있는 최대 수익을 출력해야 하는데, 이전에 벌어들인 수익을 누적시켜야 하기 때문에 DP를 이용했습니다. 기본 로직은 상담을 하는 것과 하지 않는 것으로 나누고, 상담을 했을 때는 max(상담을 했을 때의 누적값, 그날 상담으로 얻을 수 있는 비용)이고, 상담을 하지 않은 경우에는 max..

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 이 문제는 오른쪽, 아래쪽, 대각선으로 이동하여 가져올 수 있는 사탕의 개수의 최댓값을 구하는 문제입니다. 다양한 방식으로 풀 수 있는데, 저는 Top-down 방식(재귀)보다 Bottom-Up 방식이 익숙해서 Bottom-up으로 풀었습니다. 기본 로직은 이러합니다. dp[i][j] = max(max(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 이 문제도 마찬가지로 dp를 활용한 풀이입니다. 왜냐하면 값을 하나씩 누적해서 더하면 시간 복잡도가 O(2^20)이므로 dp 배열에 저장할 때, 이전 값을 참조해서 누적 값 자체를 저장해야 합니다. #include using namespace std; unsigned long long dp[1025][1025]; int main() { ios_base::..

https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 비교적 쉬운 문제의 DP 문제입니다. 백준 브론즈1 정도의 난이도입니다. 한창 생각없이 알고리즘 문제 풀 때, 이 문제를 dp로 바라보지 않고, 누적합이라고 생각했는데요. 하지만, 알고리즘을 단원별로 나눠서 풀고 문제를 바라보는 관점에 따라, 어떤 알고리즘으로 풀어야 되는지 알게되고 나서부터는 이 문제를 보자마자 DP를 써야겠다고 생각했습니다. #include using namespace std; int dp[15][15]; int ma..

Longest Increasing Subsequence(가장 긴 증가하는 부분 수열)이란? : 하위 시퀀스의 모든 요소가 오름차순으로 정렬되도록 주어진 시퀀스의 가장 긴 하위 시퀀스의 길이를 찾는 것이다. #include #include using namespace std; int d[1001]; int a[1001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin>>n; int i; for(i=0;i>a[i]; } int j; int max=1; for(i=0;i