다이나믹 프로그래밍이란? 큰 문제를 작은 문제로 쪼개고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.다이나믹 프로그래밍을 구현하는 방법에는 작은 문제를 재귀적으로 호출하는 방식인 Top-Down(하향식)작은 문제부터 하나씩 해결해나가면서 답을 도출하는 방식인 Bottom-Up(상향식)예제 1) 1로 만들기정수 X가 주어지고 다음 연산을 적절히 사용해서 1을 만드려고 할 때, 연산을 사용하는 횟수의 최솟값을 출력하시오.- X가 5로 나누어 떨어지면, 5로 나눈다. - X가 3로 나누어 떨어지면, 3로 나눈다. - X가 2로 나누어 떨어지면, 2로 나눈다. - X에서 1을 뺀다. 문제 해설Bottom-Up 방식 사용문제의 규칙을 찾아보면 다음과 같다.f(1) = 0f(2) =..

문제 설명맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하세요.아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 or 대각선 오른쪽에 있는 것 중에서만 선택할 수 있습니다. 입력조건첫째 줄에 삼각형의 크기둘째 줄부터 n+1번째 줄까지 정수 삼각형출력조건합이 최대가 되는 경로에 있는 수의 합입출력 예시입력예시출력예시5 7 3 8 8 1 02 7 4 4 4 5 2 6 54 문제 풀이다이나믹 프로그래밍으로 풀이'금광' 문제와 비슷한 유형의 문제이다.정수삼각형의 수들을 배열에 저장하면, 윗층에서 현재 위치로 내려올 수 있는 경우는 2가지가 있다.(왼쪽 위 or 바로 위)이 두가지 경우 중에서 더..

문제 설명n × m 크기의 금광의 각 칸에 특정한 크기의 금이 들어있고, 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다.- 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다.- 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다.위의 규칙을 가지고 이동할 때, 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요. 입력조건첫째 줄에 테스트 케이스 T매 테스트 케이스의 첫째 줄에 n과 m매 테스트 케이스의 둘째 줄에 n × m개의 금의 개수출력조건테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기입출력 예시 입력예시출력예시23 41 3 3 2 2 1 4 1 0 6 4 74 41 3 1 4 2 2 4 1 5..

[문제링크]https://www.acmicpc.net/problem/18405문제 설명하나의 칸의 크기가 1 ×1인 N × N 크기의 시험관 안에 바이러스가 존재할 수 있고, 모든 바이러스는 1 ~ k번까지의 바이러스 종류 중 하나이다. - 시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식한다.- 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다.- 이미 어떠한 바이러스가 존재한다면 그곳에는 다른 바이러스가 들어갈 수 없다.S초가 지난 후에 (X, Y)에 존재하는 바이러스의 종류를 출력하세요. 만약 해당 위치에 바이러스가 존재하지 않는다면 0 출력 입력조건첫째 줄에 시험관의 크기 N, 바이러스 종류의 개수 K둘째줄 ~ N+1번째 줄 까지 시험관 안에 바이러스 정보N+2..

문제 설명N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요. 입력조건첫째 줄에 동전의 개수를 나타내는 양의 정수 N(1 둘째 줄에 각 동전의 화폐단위를 나타내는 N개의 자연수출력조건주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값입출력 예시입력예시출력예시53 2 1 1 98 문제 풀이입력받은 n개의 동전들을 오름차순 정렬한 후, 동전들로 1부터 차례대로 특정 금액(target)을 만들 수 있는지 확인한다.target >= (현재 동전금액) 일 경우, 현재 동전으로 target을 만들 수 있다 → target 값 업데이트여기서 target이 특정 값일 때, 1 ~ (target-1)까지의 모든 금액을 만들 수 있다고 가정한다. 예시) n=5, {3,..

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42891 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 설명무지가 1부터 N번까지의 음식을 음식번호가 증가하는 순서대로 먹기 시작한다.먹방을 시작한 지 K초 후에 네트워크 장애로 인해 방송이 잠시 중단된 후, 다시 먹기 시작할 때 몇 번 음식부터 먹어야 하는지 구한다.만약 더 섭취해야 할 음식이 없다면 -1을 반환한다. 입력조건각 음식을 모두 먹는데 필요한 시간이 들어있는 배열 food_times방송이 중단되 시간 k출력조건k입출력 예시입력예시출력예시[3, 1, 2]51 문제..