DP

📍문제 링크 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 📍문제 풀이 N * N (4 { const N = +input.shift(); const board = input.map((row) => row.split(" ").map(Number)); // 아예 memo를 여유있게 넉넉하게 만들기 const memo = Array.from({ length: N + 10 }, (_) => Array..

📍문제 링크https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)www.acmicpc.net 📍알고리즘 분류- 다이나믹 프로그래밍 - 배낭 문제 📍문제 풀이배낭 문제(Knapsack Problem) 로 알려진 유명한 문제 - 메모이제이션을 이용하지 않으면 시간이 매우 매우 오래걸린다 - DP를 이용하면 O(N * K) 로 해결 가능 데이터 수 N과, 최대 배낭의 무게 K가 주어진다. N개의 줄에 아이템의 무게 W, ..

📍문제https://school.programmers.co.kr/learn/courses/30/lessons/12900 📍풀이: DP로 경우의 수 메모이제이션타일을 배치하는 경우의 수를i. 세로 타일로 시작할 때 (| 모양 스타트)ii. 아닐 때 (= 모양 스타트) 크게 이렇게 구분할 수 있음 n = 1 이라면i. 1ii. 0-> 1 n = 2 i. 1ii. 1-> 2 n = 3i. n = 2의 경우의 수 (2) (| 모양 채웠으므로 나머지 2개 영역만 채우면 됨)ii. n = 1의 경우의 수 (1) (= 모양 채웠으므로 나머지 1개 영역만 채우면 됨) n = 4i. n = 3의 경우의 수ii. n = 2의 경우의 수 n = 5i. n = 4의 경우의 수ii. n = 3의 경우의 수 그렇다면 f(n)..

📍문제 링크 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 📍문제 풀이 사탕이 R행 C열의 좌표평면에 몇 개씩 놓여져 있다 1행 1열에서 출발하여 R행 C열 까지 이동한다고 할때 경로를 지나며 획득할 수 있는 사탕의 최대 갯수를 구하면 된다 이때, 이동할 수 있는 방향은 3시 방향, 5시 방향, 6시 방향의 3개이다 R+1 * C+1 크기의 memoization 이차원 배열을 그리고, 직전..

📍문제 링크 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 - 슬라이딩 윈도우 📍문제 풀이 세 수가 일렬로 쭉 내려오는 수열이 있다. 내려올 때, 직선, 대각선으로 내려올 수 있다고 할 때 최댓값과 최솟값을 구하라 /* 1번 라인1 2 3 2번 라인4 5 6 3번 라인4 9 0 1 1 2 3 일 때 각 라인에서 가능한 최대 최소 123 최대123 최소123 2 1 2 3 4 5 6 일 때 각 라인에서 가능한 최대 최소..

📍문제 링크 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 📍문제 풀이 - 음이 아닌 정수 N이 주어진다. - 이친수의 조건 1. 11이 2번 등장하지 않음 2. 1과 0으로 만 이루어짐 - N 자리의 이친수가 몇개 존재하는지 갯수를 출력하라 N = 1 일때는 1 N = 2 일때는 10 N = 3 일때는 100 101 이것을 종합해보면, N = i 일 때, i - 1의 이친수 들에 0과 1을 ..