본문 바로가기

DP23

[백준] 14430번 - 자원 캐기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 자원 캐기 https://www.acmicpc.net/problem/14430 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. www.acmicpc.net 현재 칸에서 오른쪽, 아래쪽으로 갔을 때 얻을 수 있는 최대 광석 수를 동적 계획법을 통해 해결합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/14430_%EC%9E%90%EC%9B%90%EC%BA%90%EA%B8%B0.c.. 2022. 3. 4.
[백준] 21317번 - 징검다리 건너기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 징검다리 건너기 https://www.acmicpc.net/problem/21317 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net 전형적인 동적 계획법으로 쉽게 해결할 수 있는 문제였습니다. solve(i, usedMegajump)를 통해 i 번째 돌까지 갔을때 필요한 최소 에너지의 memoization을 통해 해결합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/21317_%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC%EA%B1%B4%EB%84%88%EA%B8%B0.cpp .. 2022. 2. 23.
[백준] 10653번 - 마라톤 2 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 마라톤 2 https://www.acmicpc.net/problem/10653 10653번: 마라톤 2 젖소 박승원이 2번째 와 4번째 체크포인트를 건너뛸경우 경로는 (0,0) -> (1,1) -> (2,2) 로 4가 된다. 이보다 더 짧게 달릴수는 없다. www.acmicpc.net 모든 체크 포인트의 좌표를 입력 받아 거리를 미리 계산합니다. 그 후, 체크 포인트를 뛰어넘는 경우와 그렇지 않는 경우로 각 최소 거리를 계산합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/10653_%EB%A7%88%EB%9D%BC%ED%86%A4%202... 2022. 1. 17.
[백준] 2533번 - 사회망 서비스(SNS) (C++) 문제 및 풀이 문제) 백준 - DP - 사회망 서비스(SNS) https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 양방향 그래프에서 해결할 방법이 떠오르지 않아 단방향 그래프로 바꾼 후에 DP를 통해 순회하며 해결했습니다. DP(node, flag)로 모델링하여 최소 얼리어답터의 수를 memo 합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201.. 2021. 12. 30.
[백준] 10826번 - 피보나치 수 4 (Python) 문제 및 풀이 문제) 백준 - DP - 피보나치 수 4 https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 큰 수 구현이 귀찮아서 파이썬으로 해결했습니다. Python 소스코드) import sys input = sys.stdin.readline dp = [0 for _ in range(10001)] N = int(input()) dp[0] = 0 dp[1] = 1 for i in range(2, N + 1): dp[i] .. 2021. 12. 30.
[백준] 5582번 - 공통 부분 문자열 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 공통 부분 문자열 https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net LCS랑 유사한 연속된 공통 문자열을 찾는 문제였습니다. LCS를 풀어봤다면 쉽게 풀 수 있는 문제입니다. C++ 소스코드) 2021. 12. 22.
[백준] 10803번 정사각형 만들기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 정사각형 만들기 https://www.acmicpc.net/problem/10803 10803번: 정사각형 만들기 두 변의 길이가 모두 양의 정수인 직사각형 모양의 종이가 주어져 있다. 이 종이를 칼로 여러 번 잘라서 모든 조각이 한 변의 길이가 양의 정수인 정사각형이 되도록 하고자 한다. 칼로 종이를 www.acmicpc.net 쉬운 DP문제일 줄 알았으나, TLE에서 최적화하느라 꽤 걸린 문제였습니다. (i)의 방법으로 1~n/2, 1~m/2까지 자릅니다. 하지만 큰 수에서 O(n*m)의 연산이 필요하기 때문에 큰 수에서는 (ii) 방법을 이용하여 최소 정사각형 개수를 구합니다. C++ 소스코드) Full Code) https://github.com/Chocochip1.. 2021. 12. 20.
[백준] 16194번 - 카드 구매하기 2 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 카드 구매하기 2 https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net Top-down 방식으로 풀이 했습니다. DP 모델링을 res카드를 구매하기 위해 지불해야하는 최소 금액으로 memoization을 진행했습니다. 풀다가 P의 범위를 i=0으로 지정해서 꽤 걸렸네요ㅜㅜ C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%.. 2021. 12. 3.
[백준] 15990번 - 1, 2, 3 더하기 5 (C++) 문제 및 풀이 문제) 백준 - DP(동적 계획법) - 1, 2, 3 더하기 5 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 이전 사용한 숫자(prev)를 memoization하여 prev를 제외한 숫자를 사용하여 합을 나타낼 수 있는 방법을 계산한다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2015000~19999/15990_1%2C%202%2C%203%20%EB%8D%94%ED%95%98%EA%.. 2021. 11. 13.
반응형

티스토리툴바