DP

문제https://www.acmicpc.net/problem/2637백준 - 문제집 - 0x1A강 - 위상 정렬 알고리즘: 다이나믹 프로그래밍, 방향 비순환 그래프, 위상 정렬풀이 AI의 도움을 받았던 문제다...🤖DP + 위상 정렬을 사용해야하는 문제인데, DP에 더 가까워보인다. 문제에서 구하고자 하는것은 "필요한 기본부품의 종류와 수"인데,기본부품 - 완제품 사이 중간부품이 존재한다.그리고 기본부품은 중간부품, 완제품 모두에 사용될 수 있다. 그런고로 이 문제 역시 DFS로 풀려면 살짝 복잡해진다. (계보 복원가 호석 문제를 떠올려보자...)BFS를 사용하려면 진입차수부터 정리해줘야하는데 무의식적으로 풀다간 실수할수도 있다.장난감은 (기본부품 - 중간부품 - 완제품) 순으로 만들어져야한다.즉, 기..

문제https://www.acmicpc.net/problem/1005백준 문제집 - 0x1A강 - 위상 정렬 알고리즘: 다이나믹 프로그래밍, 방향 비순환 그래프, 위상 정렬풀이 2056: 작업 문제와 같은 로직이다. 작업이 A → B 순으로 처리되므로 B에 해당되는 작업들의 진입차수를 증가시킨다.진입차수 정리가 끝났다면 아래의 과정을 거친다.dp 리스트, queue 생성진입차수가 0인 작업들을 찾음dp값에 해당 작업의 소요시간을 저장queue에 추가위에서 저장한 queue를 가지고 BFS 실행queue: 지금 당장 시작할 수 있는 작업들queue에서 pop한 작업과 연결된 작업들을 탐색연결작업의 진입차수를 1 감소시킴연결작업의 dp값을 갱신함 => max(기존 dp값, 현재 작업의 dp값 + 연결작업의 ..

문제https://www.acmicpc.net/problem/2056백준 문제집 - 0x1A강 - 위상 정렬 알고리즘: 다이나믹 프로그래밍, 방향 비순환 그래프, 위상 정렬풀이 🗝️ DP + 위상정렬 문제다.각 작업은 선행 작업이 끝난 이후부터 시작할 수 있고, 서로 선행관계가 없는 작업들은 병렬적으로 작업할 수 있다.즉, 현재 작업의 선행 작업들 중 가장 늦게끝나는 작업을 시작 기준으로 삼아야한다. 일단 A: 선행작업, B: 후 작업 일 때 A → B 형태로 진입차수를 정리해준다.그리고 DP 리스트를 생성 후, 진입차수가 0인 작업들을 찾는다.해당 작업들의 DP값을 주어진 작업시간값으로 갱신 후, 작업번호를 queue에 삽입한다.BFS를 실행하며 DP값들을 갱신시켜준다. 과정은 아래와 같다.queue..

문제https://www.acmicpc.net/problem/15486백준 문제집 - 0x10강 - 다이나믹 프로그래밍 알고리즘: 다이나믹 프로그래밍풀이상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.문제 자체는 14501: 퇴사와 동일하다.그래서 혹시나 하고 이전 풀이를 그대로 제출해봤더니 ..

문제https://www.acmicpc.net/problem/14501백준 문제집 - 0x10강 - 다이나믹 프로그래밍 알고리즘: 다이나믹 프로그래밍, 브루트포스풀이상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.11055: 가장 큰 증가하는 부분수열 문제와 비슷하게 풀면 된다.단, 이전 상담..

문제https://www.acmicpc.net/problem/11055백준 문제집 - 0x10강 - 다이나믹 프로그래밍 알고리즘: 다이나믹 프로그래밍풀이수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다. 11053: 가장 긴 증가하는 부분수열과 비슷한 문제다.N만큼의 dp리스트를 생성 후 이중 for문을 통해 체크한다.dp[i] = i번째 숫자를 선택..