Algorithm 💡/DP41 [백준 2579번] 계단 오르기 이번 문제는 연속으로 3칸을 밟을 수 없고 한번에 1칸이나 2칸씩 계단을 오를 수 있다는 가정 하에, 마지막 도착 계단까지 도착하는데 얻을 수 있는 총 점수의 최댓값을 구하는 문제이다. 먼저 이 문제는 완전탐색으로 풀 경우에는 N이 최대 300이기 때문에 2^300 의 경우의 수로 인해 시간초과가 발생하게 된다. 따라서 O(n) 시간복잡도로 풀 수 있는 DP 알고리즘을 사용해야 한다. 처음에 이 문제를 풀이했을 때는 dp 테이블을 1차원 배열로 선언해서 점화식을 도출하려고 했었는데, 1차원으로 선언하게 되면 점화식을 세우고 싶어도 연속한 세 계단을 모두 밟아서는 안 된다는 제약 조건을 점화식에 넣을 방법이 없다.(연속해서 몇 개의 계단을 밟았는지 확인할 수 없음) 따라서 i번째 계단까지 밟았을 때의 총 .. 2023. 10. 1. [백준 7570번] 줄 세우기 n = int(input()) data = list(map(int,input().split())) data.insert(0,0) index_list = [0]*(n+1) count = 1 max_length = -1 for i in range(1,n+1): index_list[data[i]] = i for i in range(1,n): if index_list[i] < index_list[i+1]: count += 1 max_length = max(max_length, count) else: count = 1 if max_length != -1: print(n - max_length) else: print(0) 이번 문제는 임의의 순서로 세워진 번호를 맨 앞이나 맨 뒤로만 이동시킬 수 있다는 가정 하에 .. 2023. 8. 14. [백준 2631번] 줄세우기 n = int(input()) data = [] dp = [1]*n for i in range(n): data.append(int(input())) for i in range(n): for j in range(i): if data[i] > data[j]: dp[i] = max(dp[i],dp[j]+1) print(n - max(dp)) 이번 문제는 임의의 순서로 세워진 번호를 번호 순서대로 배치하기 위한 최소한의 이동횟수를 구하는 문제이다. 번호를 옮기는 횟수를 최소화하기 위해서는 번호 순서대로 세워져있는 어린이들을 최대한 많이 고정시키고 나머지만 이동시켜야 한다. 즉, 가장 긴 증가하는 부분수열 LIS(Longest Increasing Subsequence)의 길이를 구하고 이를 전체 어린이 수에서 빼.. 2023. 8. 14. [HackerRank] Knapsack def unboundedKnapsack(k, arr): # Write your code here row = len(arr) col = k dp = [[0]*(k+1) for _ in range(row+1)] for i in range(1,row+1): dp[i][0] = 1 for i in range(1,row+1): for j in range(1,col+1): if j >= arr[i-1]: dp[i][j] = dp[i-1][j] + dp[i][j-arr[i-1]] else: dp[i][j] = dp[i-1][j] for i in range(col,-1,-1): if dp[row][i] != 0: return i 이번 문제는 주어진 배열(arr)의 원소들을 가지고 만들 수 있는 타겟 값(k)을 초과하지.. 2023. 5. 20. [HackerRank] The Maximum Subarray def maxSubarray(arr): # Write your code here len_arr = len(arr) dp_array = [0]*(len_arr) dp_sequence = [0]*(len_arr) dp_array[0], dp_sequence[0] = arr[0], arr[0] for i in range(1,len_arr): dp_array[i] = max(arr[i], arr[i]+dp_array[i-1]) for i in range(1,len_arr): dp_sequence[i] = max(dp_sequence[i-1], dp_sequence[i-1]+arr[i], arr[i]) return [max(dp_array),dp_sequence[len_arr-1]] 이번 문제는 주어진 배열(ar.. 2023. 5. 15. [HackerRank] The Coin Change Problem def getWays(n, c): # Write your code here coin_count = len(c) dp = [[0]*(n+1) for _ in range(coin_count+1)] for i in range(1,coin_count+1): dp[i][0] = 1 for i in range(1,coin_count+1): for j in range(1,n+1): coin_value = c[i-1] if coin_value > j : dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i-1][j] + dp[i][j-coin_value] return dp[coin_count][n] 이번 문제는 주어진 c 배열 안의 값들로 n을 만들 수 있는 경우의 수를 구하는 문제이다. 문제.. 2023. 5. 14. 이전 1 2 3 4 5 ··· 7 다음
