종식당

문제 설명 다이내믹 프로그래밍의 가장 기본적인 문제이다. 입력으로 받은 정수 x를 5로 나누기, 3으로 나누기, 2로 나누기, 1을 빼기 이 4가지 경우의 수를 조합해 최소한의 연산으로 1로 만드는 연산의 횟수를 출력하면 된다. 문제 코드 X = int(input()) dp = [0] * (X+1) for i in range(2,X+1): dp[i] = dp[i-1]+1 # 1 뺏을 때 if i%2 == 0: dp[i] = min(dp[i],dp[i//2]+1) # 2로 나누었을 때 if i%3 == 0: dp[i] = min(dp[i],dp[i//3]+1) # 3으로 나누었을 때 if i%5 == 0: dp[i] = min(dp[i],dp[i//5]+1) # 5로 나누었을 때 print(dp[X]) 일..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 설명 첫 번째 입력으로 수열의 길이를 입력받고 두 번째 줄에 수열을 입력받는다. 출력으로는 증가하는 부분 수열 중에 가장 긴 길이를 출력하면 된다. 이 문제 유형의 알고리즘으로는 LIS(Longest Increasing Subsequence)이다. 이 알고리즘에 대해서는 이진 탐색을 공부하면서 처음 알게 되었으며 ..

문제 설명 첫 번째 줄에 떡의 개수 N과 떡의 길이 M이 주어지고 두 번째 줄에 떡들의 길이가 주어지면 이들을 각각 잘라서 M만큼 길이의 떡을 얻기 위한 절단기의 최댓값을 출력하면 된다. 문제 풀이 문제 코드 N, M = map(int,input().split()) lst = list(map(int,input().split())) start = 0 end = max(lst) result = 0 while start mid: total+=i-mid if total < M: end = mid - 1 else: result = mid start = mid + 1 print(result) 이 문제는 이진 탐색을 생각해 내서 접근하기는 너무 어려운 문제였고 이진 탐색이라는 알고리즘을 알아도 적용하기 너무 어려워 ..

문제 설명 첫 번째 줄에 N을 입력받고 두 번째 줄에 N개의 부품을 입력받는다. 세 번째 줄에 M을 입력받고 네 번째 줄에 N개의 부품을 입력받은 후 N개의 부품이 M개 부품에 포함되는지 판단하여 포함되면 yes 안되면 no를 출력하면 된다. 개념 설명 문제를 풀기 전에 먼저 이진 탐색의 개념을 잡고 넘어가려 한다. 이진 탐색이란, 오름차순으로 정렬된 배열을 반복적으로 반으로 나누어 target이 선택될 때까지 탐색하는 알고리즘이다. 이때 이진 탐색을 사용할 때는 꼭 정렬된 상태에서 사용할 수 있다는 점을 기억해두자! 시간 복잡도는 O(logn)이다. 1. 반복문 사용 def binary_search(target, data): data.sort() start = 0 # 맨 처음 위치 end = len(d..