📍문제 링크 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://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을 ..

📍문제 링크 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 📍문제 풀이 - 자연수 N이 주어질 때, 2 * N 배열에 원소를 채우는 경우의 수를 9901로 나눈 나머지를 구하라 - 원소는 가로나 세로로 붙을 수 없다 - 원소를 하나도 배치하지 않은 경우도 한 가지의 경우의 수로 친다 N =1 일 때의 결과를 N = 2 일 때 이용할 수 있다면, DP로 해결할 수 있다 """ N = 1 1. 0,0 좌표에 사자 배치 OX 2. 0,0 좌표에 사자 no배치 XO 3. no배치 XX ------------ N = 2 N = 1의 경우에다 밑에..

📍문제 링크 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 - 누적 합 📍문제 풀이 - 연속된 수열이 주어지고, 1 ~ 3 사이의 자연수 max가 하나 주어진다 - 연속된 수열에서 max 개의 연속하는 수를 3개 만들고, (겹치면 안됨) 그 합이 최대가 되는 수를 구하라 ⭐연속된 수열에서 구간 합을 빠르게 구하기 위해 누적 합 (prefix sum) 배열을 만들고 이용한다 - 예를 들어 1 2 3 ..

📍문제 링크 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 📍알고리즘 분류 - DP 📍문제 풀이 정수가 N개 주어질 때, 연속하는 정수들로 구성된 최댓값을 구하라 DP를 써서 O(N)에 해결할 수 있다 📍의사 코드 주어진 배열을 순회하며, memo 배열에는 arr[i] 까지의 연속합을 저장한다 (단, 더했을때 오히려 마이너스가 되면, 다음에 나오는 수로 업데이트) 예를 들면, 10 -4 3 1 5 6 -35 12 21 -1 배열에서 10 10 -4 10..