본문 바로가기

Algorithm/DP(Dynamic Programing)

 (65)
(C++) - 백준(BOJ) 20438 : 출석체크 https://www.acmicpc.net/problem/20438 20438번: 출석체크 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000) 2번째 줄과 3번째 줄에 각각 K명 www.acmicpc.net 누적합 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 학생 수 n, 조는 인원 k, 출석코드를 받은 학생 수 q, 구간 개수 m, 구간 s와 e, 정답을 출력할 ans, 학생 vector, map sleep, attend를 선언후 입력받습니다. 📔 풀이과정 * 5000의 학생 수에 대해 50000개의 구간이 들어온다면 brute force로 탐색 시 2..
(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 문제였습니..

티스토리툴바