문제 기술 2) 다음과 같은 형태의 일방통행 도로망에서 호텔에서 공항까지 가는 버스를 운행하고 있다. 호텔에서 공항까지 가는 도로망의 구조는 다음과 같다. 위쪽 도로에 n개 교차로 u1, u2, …, un이 있고, 아래쪽 도로에 n개 교차로 l1, l2, …, ln이 있다. u0(=l0)는 호텔을 나타내고, un+1(=ln+1)은 공항을 나타낸다. 그리고 i

문제 기술 다음과 같은 m개의 행과 n개의 열의 셀(cell)들로 이루어진 m*n 격자가 있다.여기서 가장 아래 행은 행 1이고 가장 위의 행은 행 m이며, 가장 왼쪽 열은 열 1이고 가장 오른쪽 열은 열 n이다. 셀 (i, j)는 i번째 행과 j번째 열의 셀을 나타낸다. 각 셀 (i, j)에는 비용 C(i, j)이 주어진다. 2 8 9 5 8 4 4 6 5 3 5 7 5 1 1 3 2 5 4 8 가장 아래 행의 셀로부터 오른쪽 위쪽 대각선 방향 혹은 위쪽 방향 혹은 왼쪽 위쪽 대각선 방향으로만 가면서 가장 위의 행의 셀까지 가는 경로의 최소비용을 구하는 프로그램을 동적계획법을 이용하여 작성하시오. 경로의 비용이란 지나가는 셀의 비용의 총합이다. 제약조건: 부분문제의 해의 값를 저장하는 테이블로 1차원 ..

문제 기술 다음과 같은 m개의 행과 n개의 열의 셀(cell)들로 이루어진 m*n 격자가 있다.여기서 가장 아래 행은 행 1이고 가장 위의 행은 행 m이며, 가장 왼쪽 열은 열 1이고 가장 오른쪽 열은 열 n이다. 셀 (i, j)는 i번째 행과 j번째 열의 셀을 나타낸다. 각 셀 (i, j)에는 비용 C(i, j)이 주어진다. 2 8 9 5 8 4 9 6 5 3 6 7 5 2 1 3 2 5 4 8 (1, 1) 셀 (1, 1)에서 오른쪽 방향 혹은 위쪽 방향으로만 가면서 셀 (m, n)까지 가는 경로의 최소비용을 구하는 프로그램을 동적계획법을 이용하여 작성하시오. 경로의 비용이란 지나가는 셀의 비용의 총합이다. 제약조건: 부분문제의 해의 값를 저장하는 테이블로 1차원 배열(리스트)를 사용해야 하고, 이 배..

위의 라인은 S1, 아래 라인이 S2이다. 각 라인은 1부터 n까지의 공정이 있고, 이는 Si, j로 나타낸다. Si, j의 소요 시간은 각각 ai, j이다. ei는 i번째 라인에 들어가는 데 소요되는 시간을 의미하고(ex. e1: line 1에 들어가는 데 소요되는 시간) xi는 i번째 라인에서 작업을 다 마치고 나오는 데 소요되는 시간을 의미한다. 마지막으로 ti, j는, j번째 공정까지 마친 뒤 i번째 라인에서 다른 라인으로 교체하는 데 소요되는 시간이다. f1[j]은, i번째 라인에서 진행하는 j 공정(Si, j)을 시작 지점으로 했을 때 가장 빠른 시간이다. 여기서 우리가 구해야 될 것은, f*, 즉 최종적으로 가장 빠른 시간을 저장하는 변수이다. 동적 계획법을 사용하여 접근하면 이 문제를 선형..

문제 기술 프로그래머스 lv3 입국심사 문제를 변형한 문제이다. 공항에서 사람들의 입국을 심사하는 심사대가 k개있다. 사람들이 입국심사를 받기 위하여, 심사대 바로 앞에서 한 줄로 서서 기다린다. k개의 심사대 중 하나가 비어있으면(심사받는 사람이 없으면), 먼저 도착한 사람이 비어 있는 이 심사대에서 심사를 받는다. 입국심사를 받기 위한 각 사람의 심사대 앞에 도착하는 시간과 심사받는데 걸리는 시간이 주어진다. 각 사람이 심사대 앞에 도착한 시간에 대한 정보는, 바로 이전 사람이 심사대 앞에 도착한 시간과의 차이(분)로 주어진다. 각 사람이 심사를 받기 위하여 기다리는 시간 (심사시간은 제외)의 평균을 소수점 이하 1자리까지 (소수점 이하 2째 자리에서 반올림) 출력하는 프로그램을 작성하시오. 예를 들..

문제 기술 n(1이상 10,000이하 정수)개 계단을 바닥에서 위로 올라가려고 한다. 계단을 올라갈 때 한 번에 1개, 3개 혹은 4개의 계단만 오를 수 있으며, 각 계단은 밟을 때 비용이 있다. 바닥에서 가장 위의 계단으로 올라갈 때 밟는 계단의 비용 합이 최소가 되도록 하면서 올라가고자 한다. 이때의 최소 비용을 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 양의 정수 n이 주어진다. 다음 줄에 가장 아래 계단부터 위로 차례대로 n개 각 계단을 밟을 때 비용이 양의 정수로 주어진다. 출력 바닥에서 가장 위의 계단으로 올라갈 때 밟는 계단의 비용 합의 최소값을 출력한다. 입력 예 6 2 7 2 9 12 3 출력 예 5 나의 코드 import sys def stair(n, price): if 1

문제 기술 n(1이상 20이하 정수)개 계단을 바닥에서 위로 올라가려고 한다. 계단을 올라갈 때 한 번에 1개, 3개 혹은 4개의 계단만 오를 수 있다. 바닥에서 가장 위의 계단으로 올라갈 때, 올라가는 방법의 수를 구하는 프로그램을 작성하시오. 입력 형식 첫 번째 줄에 양의 정수 n이 주어진다. 출력 바닥에서 가장 위의 계단으로 올라가는 방법의 수를 출력한다. 입력 예 및 출력 예 8 // 25 나의 코드 import sys n = int(sys.stdin.readline()) def dpstair(n): C = [0 for i in range(n+1)] C[0] = C[1] = C[2] = 1 C[3] = 2 for i in range(4, n+1): C[i] = C[i-1] + C[i-3] + C[..

Algorithm - DP(Dynamic Programming) 동적 계획법 Dynamic Programming의 조건은 두 가지가 있다.이는 바로 최적 부분 구조(Optimal Substructure), 중복되는 부분 문제(Overlapping Subproblems)이다. 최적 부분 구조 최적 부분 구조가 있다는 것은 -> 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것을 의미한다. fib(5)를 구하려면, fib(4)와 fib(3)을 구하는 부분 문제를 먼저 해결해야 한다. 이 점에서, 피보나치는 최적 부분 구조를 갖고 있다. 중복되는 부분 문제 재귀 함수 -> 부분문제 를 봤었음. fib(5)를 해결하기 위해 fib(4)와 fib(3)이라는 부분문제를, fib(4)를..