다이나믹 프로그래밍

[백준] 14002. 가장 긴 증가하는 부분 수열 4 (Java)

문제 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 알고리즘 다이나믹 프로그래밍(DP) 풀이 가장 긴 증가하는 부분 수열 1, 2, 3 문제에서 LIS 출력이 추가된 문제이다. 입력 수열의 길이가 1,000으로 돌아왔기 때문에 가장 긴 증가하는 부분 수열 1 문제와 동일하게 다이나믹 프로그래밍을 이용한다. dp 배열에 각 원소의 LIS 길이가 저장되어있기 때문에 이를 뒤에서부터 탐색하며 LIS의 i번째에서부터 0번째 원소를 역추..

[백준] 11053. 가장 긴 증가하는 부분 수열 (Java)

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 알고리즘 다이나믹 프로그래밍(DP) 풀이 LIS(Longest Increasing Subsequence) 문제이다. LIS 문제는 시간 복잡도 O(n^2)를 가지는 다이나믹 프로그래밍과 O(nlogn)을 가지는 이분 탐색 풀이법이 있다. 해당 문제는 다이나믹 프로그래밍으로도 해결이 가능하기 때문에 이를 이용한다. 이분 탐색을 이용한 풀이는 12015. 가장 긴 증가하는 부분 수열 ..

[SWEA] 3307. 최장 증가 부분 수열 (Java)

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 다이나믹 프로그래밍, 이분 탐색 풀이 LIS 문제이다. LIS 문제는 시간 복잡도 O(n^2)를 가지는 다이나믹 프로그래밍과 O(nlogn)을 가지는 이분 탐색 풀이법이 있다. 1. 다이나믹 프로그래밍 배열의 각 원소마다 자기보다 앞에 있으면서 크기가 작은 원소들 중 최장 증가 부분 수열의 길이가 가장 큰 값 + 1 이 자신의 최장 증가 부분 수열의 길이가 된다. 따라서 모든 원소를 탐색 후 dp에 저장된 최댓값이 해당 수열의 최장 증가 부분 수열이다. 2. 이분 탐색 최장 증가 부분 수열의 길이만을 구할 수 있는 방법이다. 최장 증가 부분 수열을 ..

[백준] 2533. 사회망 서비스(SNS) (Java)

문제 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 알고리즘 트리, 다이나믹 프로그래밍(DP) 풀이 트리 DP 유형 문제이다. 단말 노드부터 거슬러 올라가며 dp 배열에 저장된 자식 노드의 최솟값을 이용하여 해당 노드 번호에 해당하는 사람이 얼리어답터일 경우와 아닐 경우의 최솟값을 구하고 저장한다. 2차원 배열 dp[N+1][2] 를 선언하고 i번째 번호에 해당하는 사람이 얼리어답터가 아닐 경우의 최솟값를 dp[i][0], 맞을 경우의 최솟값을 dp[i][1]에 저장한다. ..

[백준] 23258. 밤편지 (Java)

문제 23258번: 밤편지 $C = 3$일 때, 1번 정점에서 4번 정점으로 가는 경로 중 3번 정점을 지나는 경로는 반딧불이 3번 정점에서 8방울의 이슬을 마시고 잠들어버리기 때문에 불가능하다. 따라서 가능한 경로는 2번 정점 www.acmicpc.net 알고리즘 다이나믹 프로그래밍(DP), 플로이드-워셜 알고리즘(Floyd Warshall) 풀이 Q가 최대 50만으로 V2 보다 훨씬 크기 때문에 다익스트라 알고리즘을 이용하면 시간 초과가 날 것이다. 따라서 V3의 플로이드 워셜 알고리즘으로 모든 경우의 값을 저장하고 이를 출력한다. 만약 C가 3인 반딧불이는 어느 마을까지 이동할 수 있을까 23 = 8 방울을 마실 수 있으므로 3번 마을부터는 이동할 수 없을 것이다. 1번 마을에서 21 = 2 방울,..

[백준] 1912. 연속합 (Java)

문제 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 알고리즘 다이나믹 프로그래밍(DP) 풀이 수열의 앞에서부터 이전 값을 선택했을 때 최댓값이 0보다 크다면 합을 더하고, 연속합의 최댓값이 0보다 작다면 더하면 손해이므로 연속합을 버리고 자신부터 새로 시작한다. 이 방식으로 연속합의 최댓값을 보장할 수 있다. 예제 1을 기준으로 표를 그리면 다음과 같다. 8번째 값 12를 보면 이전 값인 -35를 선택했을 때의 최댓값이 -14 로 0보다 작기 때문에 버리고 자신부터 새로 시작하는 것이 최댓값을 보장한다. 코드 impo..

[백준] 9657. 돌 게임 3 (Java)

🔒 문제 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 🔑 알고리즘 다이나믹 프로그래밍(DP) 💡 풀이 돌이 1개 있다면 상근 1 ->SK 돌이 2개 있다면 상근 1 , 창영 1 -> CY 돌이 3개 있다면 상근 3 -> SK 돌이 4개 있다면 상근 4 -> SK 라는 결과가 나온다. 돌이 5개 있다면 어떻게 될까? 상근이가 먼저 1개를 가져간다면 창영이 턴에 4개가 남아있다. 돌이 4개였을 때 선 턴이였던 상근이 이겼으므로 이번에는 창영이 이길 것이다. 상근이가 먼저 3개를 가져간다면 창영이 턴에 2개가 남아있고 돌이 2개였을 때 선 턴이였던 상근이 졌으므로 이번에는 상근이 이길 것이다. 상근이가 먼저 4개를 가져간다면 창..

[백준] 2056. 작업 (Java)

🔒 문제 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 🔑 알고리즘 다이나믹 프로그래밍(DP), 위상 정렬 💡 풀이 작업에 선행 관계가 있고, "K번 작업의 선행 작업은 1에서 K-1번 사이", 즉 사이클이 없다는 조건이 있으므로 위상 정렬을 이용하였다. 각 작업에 걸리는 시간을 배열에 저장하고 입력으로 그래프를 생성 후 진입 차수가 0인 작업(선행 작업이 없는 작업)을 큐에 삽입한다. 그리고 위상 정렬을 진행한다. - 1. 큐에서 꺼낸 작업은 작업이 끝난 셈으로 해당 작업을 선행 작업으로 필요로 ..

[백준] 1351. 무한 수열 (Java)

🔒 문제 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 🔑 알고리즘 재귀, 해시맵(HashMap), 다이나믹 프로그래밍(DP) 💡 풀이 N이 최대 1012 이므로 dp[1]부터 dp[1012] 까지 채우는 상향식 접근 방식으로는 시간 초과가 난다. 따라서 재귀를 사용하는 하향식 접근 방식을 사용한다. 또한 배열을 사용하면, 1012 크기를 가져야하므로 메모리 초과가 나고, 수열이 N을 P와 Q로 나눈 수의 합 형태이기 때문에 쓰지 않는 칸이 대부분일 것이다. 따라서 해시맵을 사용하여 메모이제이션한다. ✏️ 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu..

[백준] 2302. 극장 좌석 (Java)

🔒 문제 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 🔑 알고리즘 다이나믹 프로그래밍(DP) 💡 풀이 VIP 좌석이 없는 경우를 먼저 생각해보자 1 2 3 4 네 자리의 좌석이 있다. 1번 사람은 1 또는 오른쪽인 2에 앉을 수 있다. 만약 1번 좌석에 앉는다면 다음 2번 사람은 1번 사람과 똑같이 2 또는 오른쪽인 3에 앉을 수 있을 것이다. 즉 1번 사람의 자리만 확정된 부분 문제가 된다. 만약 오른쪽인 2번 좌석에 앉는다면 1번 사람은 두 칸 건너서 앉을 수는 없으므로 2번 자리에만 앉을 수 있다. 즉 1, 2번..