본문 바로가기

Algorithm/DP(Dynamic Programing)

 (64)
(Python) - 백준(BOJ) 10826 : 피보나치 수 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 대표 dp문제였습니다. 📕 풀이방법 📔 입력 및 초기화 항 n, fibonacci수열을 저장할 일차원 배열 fibo을 선언 후 n에 입력받습니다. 📔 풀이과정 점화식은 f[n] = f[n-1] + f[n-2] (n >= 2, f[0] = 0, f[1] = 1) 입니다. 두 가지 풀이가 있습니다. 1. for loop를 2이상 ~ n이하까지 수행해 각 항의 수..
(C++) - 백준(BOJ) 1937 : 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net dp로 푼 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 상, 하, 좌, 우로 이동 및 비교를 위한 일차원 배열 dr, dc, 대나무 숲 정보를 저장할 이차원 배열 bamboo, 판다의 정보를 저장할 이차원 배열 live, 대나무 숲의 한 변 너비 n, 정답을 출력할 변수 ans를 선언해 줍니다. 📔 풀이과정 bfs혹은 dfs를 수행하려면 brute force처럼 i,j에 배치해 모든 ..
(C++) - 백준(BOJ) 20500 : Ezreal 여눈부터 가네 ㅈㅈ https://www.acmicpc.net/problem/20500 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net dp문제였습니다. 📕 풀이방법 📔 입력 및 초기화 10,000,000,007로 나눈 답을 출력해야하므로 MOD 상수를 선언해줍니다. n과 2차원 배열 d를 선언하고 n을 입력받습니다. memoization을 위해 d배열은 -1로 초기화해줍니다. 📔 풀이과정 15는 3과 5의 공배수입니다. 따라서 15의 배수는 3의 배수 특징과 5의 배수 특징을 합친 특징을 가지고 있습니다. 특징은 다음과 같습니다. 1. 각 자리의 합이 3의 배수 2. 마지막 자리가 0또는 5인 수 memoization을 이..
(C++) - 백준(BOJ) 17831 : 대기업 승범이네 https://www.acmicpc.net/problem/17831 17831번: 대기업 승범이네 첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대 www.acmicpc.net tree dp 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 사수, 부사수 관계를 인접 그래프로 나타내기 위한 변수 graph, 각 회사원의 능력을 입력할 일차원 배열 ability, 회사원의 수 n, dp함수를 수행하며 memoization을 수행할 d배열을 선언 후 입력받습니다. graph에 값을 저장할 때 i번 회사원의 사수를 입력하는 형태이므로 graph[사수..
(C++) - 백준(BOJ) 16507 : 어두운건 무서워 https://www.acmicpc.net/problem/16507 16507번: 어두운 건 무서워 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사 www.acmicpc.net 2차원 누적합 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 r(행), c(열), q(질의 개수), board(입력받을 2차원 배열), sum(누적합을 저장할 2차원 배열) 을 선언합니다.적절히 입력받습니다. 📔 풀이과정 1. 가로방향으로 구간합을 구해줍니다. 첫 번째 열에는 그냥 board의 값이 저장됩니다. 2. 세로방향으로 구간합을 구해줍니다...
(C++) - 백준(BOJ) 2098 : 외판원 순회 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net dp 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. n, 도시로 가는 비용 cost, d배열을 선언합니다. 2. n입력 후, n행, n열만큼 i -> j도시로 가는 비용들을 cost에 입력합니다. 📔 풀이과정 n이 16인 경우 도시의 경로는 16!로 매우 많습니다. 16개의 도시를 순열로 배열하는 것과 같기 때문입니다. 도시의 상태를 빠르게(O(1)) 알..
(C++) - 백준(BOJ) 17485~6번 : 진우의 달 여행 (Small, Large) https://www.acmicpc.net/problem/17484 17484번: 진우의 달 여행 (Small) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net https://www.acmicpc.net/problem/17485 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net dp 문제였습니..
(C++) - 백준(BOJ) 1823번 : 수확, 13002번 : Happy Cow https://www.acmicpc.net/problem/1823 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net https://www.acmicpc.net/problem/13002 13002번: Happy Cow 천나라에 살고있는 민호는 애지중지하는 소 한마리가 있다. 소의 행복은 곧 민호의 행복이기 때문에 가지고 있는 전재산을 털어 최고로 맛있는 여물 N개를 구매 했다. 민호는 여물을 관리하기 www.acmicpc.net dp 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. n, 벼의 가치를 입력받을 일차원 배열 a, 점화식을 계산할 이..

티스토리툴바