이모저모

N 개의 문제가 주어지고, 그에 대한 점수와 시간이 주어진다. 제한시간 M 안에 얻을 수 있는 최대 점수를 구하는 문제이고, 한 유형당 한 번만 풀 수 있다는 조건이 있다. knapsack 알고리즘 강의에서 제시된 문제여서 knapsack으로 풀어보고 싶었지만 잘 모르겠어서 우선 DFS를 활용한 조합 방식으로 풀었다. 이후에 강의를 들으면서 knapsack 알고리즘으로 어떻게 풀 수 있는지도 배웠다:)! 1. 손 정리 2. 코드 1) dfs를 통한 조합으로 풀기 # 테스트 재료 qs = [ [10, 5], [25, 12], [15, 8], [6, 3], [7, 4] ] M = 20 # DFS로 풀기 res = 0 def DFS(level, start, time, score): global res # 제한..

knapsack 알고리즘 연습! import sys n, target_amount = map(int, sys.stdin.readline().split()) coins = [] for _ in range(n): coins.append(int(sys.stdin.readline().rstrip())) # 최소값으로 업데이트되어야 하므로, 첫 수는 아주 크게 # 가능한 최대 금액(10,000) / 최소 동전 금액(1) 한 것보다 1 크게 초기화. dy = [10001] * (target_amount + 1) # 확실하게 알 수 있는 부분 확정(0원에 대한 답은 0개의 동전) dy[0] = 0 for i in range(len(coins)): # 각 동전마다의 점진적으로 하는 기록은, 자신의 액수번째 j 부터 t..

오우 참 알고리즘의 세계란... 어떻게 이런 알고리즘을 생각해냈을까? 세상에 똑똑한 분들이 참 많다..! 냅색 알고리즘..! 아직 신기한 친구.. 여러 문제로 연습해서 더 익숙해져야겠다! M = 11 jewels = [ [5, 12], [3, 8], [6, 14], [4, 8] ] dy = [0] * (M+1) for i in range(len(jewels)): # 지금 따져보고 있는 보석의 무게(w)와 가치(v) w = jewels[i][0] v = jewels[i][1] # 자신의 무게에 해당하는 인덱스부터, 구하고자 하는 최대무게에 해당하는 인덱스까지 # 쭉 돌면서 이전에 채워놓은 칸을 참고하여 가능한 최대 무게를 업데이트한다. for j in range(w, M+1): dy[j] = max(dy[..

동일한 문제에 대해 bottom-up, top-down 두 가지 접근을 연습해보기! 1. 손계획 2. 코드 n = 3 stones = [ [3, 3, 5], [2, 3, 4], [6, 5, 2] ] record = [[0] * n for _ in range(n)] record[0][0] = stones[0][0] ##### bottom-up 풀이 for i in range(n): for j in range(n): # 0행의 경우 참고할 위칸은 없으므로, 바로 왼쪽 칸만 참고하면 된다. # 그리고 j까지 0인 경우는 시작점이고 답을 미리 정해놓았으므로 따로 계산하지 않고 pass if i == 0: if j == 0: pass else: record[i][j] = record[i][j-1] + stones..

백준의 비슷한 두 문제이다. 이렇게 정렬 기준이 여러 개 주어질 때는 하위의 우선순위기준부터 적용하고, 가장 상위의 우선순위기준은 나중에 적용하면 된다. 아주 간단하고 좋은 팁인 것 같다 :) 나중에 혹시라도 까먹을지도 모르니까 적어놔야지 import sys n = int(input()) coordinate = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ] # 하위 우선순위기준부터 coordinate.sort(key=lambda x: x[1]) # 상위 우선순위기준을 가장 마지막에 적용 coordinate.sort(key=lambda x: x[0]) for i in range(n): print(coordinate[i][0], coo..

김태원 t의 인프런 강의에서 나온 문제로 bottom-up 연습! LIS를 응용하는 문제에요~ 라는 걸 알고 접근하니까 비교적 금방 풀 수 있었던 것 같다. 나중에 낯선 곳에서 이런 문제를 만나더라도, 아 너는 최대증가수열 풀던 방법처럼 bottom up으로 풀면 되겠구나! 라고 반갑게 알아볼 수 있으면 좋겠다..!!🤓 * 미약하게나마 .. 언제 이 LIS에서의 패턴을 적용할 수 있을지 감을 잡아놓자면. 지금으로서는, 직전 단계/범위 에서 고 바로 다음 단계/범위로 넘어가거나 확장할 때 규칙적으로 적용되는 논리나 패턴이 있는 듯하다면! (예를 들어 최대증가수열은 - 언제나 이전 수보다 추가할 수가 더 커야 한다든지, 이 문제의 경우 언제나 이전 벽돌보다 무게/밑면넓이가 더 커야 한다든지 하는!) 그 때 ..