알고리즘
[백준 13397] 구간 나누기 2 C++
www.acmicpc.net/problem/13397 13397번: 구간 나누기 2 첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N) 둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수 www.acmicpc.net m개 이하의 구간을 나누어서 각 구간마다의 최댓값 최솟값을 뺀 값 중에서, 최댓값이 나올 수 있는 모든 경우의 수에서 최댓값 중에서 최솟값을 구하는 문제입니다. 구해야하는 값이 조금 복잡하다고 느낄 수 있습니다. 각 구간마다의 최댓값 최소값을 뺀 값 중에서 최댓값을 구하는건 알겠지만, 그러한 구간의 경우수가 정말 많기 때문에, 각 경우의 수마다의 최댓값 중에서 최솟값을 구하..
[백준 1756] 피자 굽기 C++
www.acmicpc.net/problem/1756 1756번: 피자 굽기 월드피자 원주 지점에서 N개의 피자 반죽을 오븐에 넣고 구우려고 한다. 그런데, 월드피자에서 만드는 피자 반죽은 지름이 제각각이다. 그런가하면, 월드피자에서 사용하는 오븐의 모양도 몹시 www.acmicpc.net 피자 굽기는 오븐에 들어갈 피자 크기를 판단하여 오븐 안에 차곡차곡 넣고, 오븐 크기에 따라, 들어갈 수 있는 피자 칸도 달라지게 됩니다. 예제 입력으로 5 6 4 3 6 2 3의 오븐 크기가 나오는데, 이부분을 좀 더 쉽게 생각하면, 5 5 4 3 3 2 2로 숫자를 바꿔서 생각할 수 있습니다. 피자 반죽 5가 5 6을 들어가던 5 5를 들어가던 들어갈 수 있는 크기는 정해져있습니다. 5 6 4에서 4부분을 통과하지 ..
[백준 9252] LCS 2 C++
www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS 2는 LCS 1를 응용한 문제입니다. LCS 2를 풀기위해서, LCS 1의 과정을 이해해야합니다. rolypolytoy.tistory.com/43?category=365766 [백준 9251] LCS C++ www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)..
[백준 2096] 내려가기 C++
www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 이번 문제는 다이나믹 프로그래밍 문제로, 기존의 다이나믹 문제 유형과 비슷하지만, 메모리를 효율적으로 구성해야하는 문제입니다. 메모리를 효율적으로 사용하기 전에, 기존의 간단한 방법으로 문제를 풀면 배열을 arr[n][3] 배열에서 이전의 위치에서 arr[n][0~3]에 더 해질 수 있는 칸들(arr[n-1][0~3] 중에서 최댓값을 구해서 arr[n][0~3]에 더해주면 됩니다. 문제에서는 별 가능 가능 불가능 이렇게 나와..
[백준 1707] 이분 그래프 C++
www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 이 문제는 두 개의 정점이 주어졌을 때, 두개의 정점은 인접하지 못하도록 표시 후, 이분 그래프가 맞는지 판별하는 문제입니다. BFS, DFS 둘 중 아무거나 사용하면 됩니다. 이분 그래프 알고리즘의 핵심은, 두 개의 정점이 인접하지 못하도록, 2 가지 색깔로 칠해주는 것입니다. 처음 노드를 선택했을 때 1, 1로 칠해진 노드안에 있는 다음 노드를 선택 했을 때 2, 그리고 2노드안에 있는 다음..
[백준 11660] 구간 합 구하기 5 C++
www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 다이나믹 프로그래밍 알고리즘을 사용해서 푸는 문제입니다. map의 전체 사이즈는 최대 1024x1024이고, 연산을 최대 100,000번 해야하기 때문에, 브루트포스로 풀게되면 당연히 시간초과가 나올 수 밖에 없습니다. 시간초과가 나오지 않으려면, DP를 사용해서 각 인덱스별로 누적합을 저장하면 되겠습니다. dp[i][j]는 i, j까지 누적합을 말합니다. 입력을 받을..