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

문제 기술 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[..

문제 오름차순으로 정렬된 n(2이상 100,000이하 정수)개의 정수(1,000,000,000이하 양의 정수) 중 K(양의 정수)와 가장 가까운 정수를 찾는 프로그램을 작성하시오. K와 가장 가까운 정수가 여러 개일 경우, 이들 중 작은 수를 출력하시오. 요구 조건: 이진 탐색(binary search)을 이용해야 한다. 입력 예시 1 5 // n 20 30 40 55 60 // n개의 정수 36 // K 출력 예시 1 40 입력 예시 2 13 20 30 40 55 60 70 75 80 85 90 91 93 100 92 출력 예시 2 92 나의 풀이 n = int(input()) num_list = list(map(int, input().split())) K = int(input()) def binary..

문제 양의 정수 M, e, n, d에 대하여 C = M^e mod n을 구하시오. (mod는 나머지를 구하는 연산이다). 그리고 위의 C에 대하여 C^d mod n을 구하시오. 단, 양의 정수 a, k, n에 대하여 ak mod n을 구하는 방법은 다음을 이용한다. a^k mod n = a mod n if k = 1 = (a^2/k mod n)^2 mod n if k가 짝수 = (a*(a^k-1 mod n)) mod n if k가 홀수 입력 예시 15 3 7 33 // M e d n 출력 예시 9 15 나의 풀이 처음에 그냥 쉽게 생각했다. 거듭제곱을 구하는 함수 작성(재귀함수를 이용) 문제의 조건을 그대로 mod 함수로 만들어서 mod한 값을 다시 mod 함수에 넣어서 print하기 이렇게 생각하여 d..

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