종식당

문제 설명 다이내믹 프로그래밍의 가장 기본적인 문제이다. 입력으로 받은 정수 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)이다. 이 알고리즘에 대해서는 이진 탐색을 공부하면서 처음 알게 되었으며 ..