one Book a Day

0 - 1Knapsack Problem 쪼갤 수 없는 물건을 배낭에 담는문제로 DP로 풀어야하는 대표적인 문제 DP로 풀수 있는지 여부는 Principle of Optimality 성립 여부를 보면 된다. Principle of Optimality 어떤 문제의 입력 사례의 최적해가 그 입력 사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면, 그 문제에 대하여 최적의 원리가 성립한다 즉 부분사례의 최적해가 현 사례의 최적해의 부품이 된다면 DP로 풀 수 있다. 물건을 취하지 않고 P[i-1][j]를 선택하느냐 취하고 P[i-1][j-wk] + v[i]를 하느냐. 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 13 13 2 0 0 0 0 8 8 13 13 3..

비트마스크(bit mask) 비크마스크란 무엇인가? 정수를 이진수로 표현, 비트 연산을 통해 문제를 해결해 나가는 기술. 집합에서 하나의 원소는 하나의 bit로 표현(꺼져있다, 켜져있다.) ex switch_states = [True, False, False, True, True, False, False, False, True, True] switch_states = 0b1001100011 # 611, python에서는 앞에 '0b'를 붙여 이진수 표현 가능 정수형으로 표현하면 비트연산을 통한 삽입, 삭제, 조회 등이 간단해짐 더 간결한 코드 작성이 가능 더 빠른 연산이 가능 더 작은 메모리의 사용. 비트마스크를 이용한 정수 표현으로 다이나믹 프로그래밍이 가능함. (중요) 위와같은 장점이 ..

다른 스터디원들 보면 뭔가 짧게 풀었던데 일단 나는 0,0기준 고쳐야하는것 체크하고 그 값 범위마다 따로sum구해서 비교했다. import sys input = sys.stdin.readline N,M = map(int,input().split()) chess = [list(input().rstrip()) for _ in range(N)] dp = [[0]*M for _ in range(N)] for i in range(N): for j in range(M): if i%2 == j%2: if chess[0][0] != chess[i][j]: dp[i][j]=1 else: if chess[0][0] == chess[i][j]: dp[i][j]=1 min_change = float('inf') for i i..

0,1 knapsack 선택하느냐 마느냐의 문제는 greedy가 안되기 때문에 점화식을 세울 수 있다면 dp 아니면 완탐이다. K라는 무게값을 1~target값까지 증가시키며 최고 가치를 누적시키면 된다. import sys input = sys.stdin.readline N, K = map(int, input().split()) wei_cost = [[0,0]] dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)] for _ in range(N): wei_cost.append(list(map(int, input().split()))) for i in range(1, N + 1): for j in range(1, K + 1): weight = wei_cost[..

이해하는데 꽤 오래 걸렸다. dp를 대각선으로 그려야 답을 구할 수 있는 문제로 아주 신박하고 연습이 필요한 문제일 것 같다. dp[i][i+j]로 놓고 i를 증가시키면 양쪽이 1,1씩 증가해 대각선 배열을 먼저 연산 할 수 있으며 j가 늘어나면 가운데 대각선에서 한칸 더 멀어진 배열을 연산하게 되는 식이다. 즉 2개씩 묶은 행렬을 계산하고(AB,BC,CD,CE) 그 값을 가지고 3개씩 묶은 행렬을 계산. min(AB*C or A*BC) 그걸 가지고 4개씩 묶은 행렬을 계산min(A*BCD,AB*CD,ABC*D) N*N 인접 행렬에서 대각선으로 배열을 채우는법을 이해할 수 있었고 차후 다른 문제에서도 쓸만한아이디어인 것 같다. 행렬의 곱셈이 이루어지는 숫자는 [앞행렬의 행값 * 앞행렬의 열값(==뒷행렬의..

아이디어 1. 추 무게의 합을 전부 구해서 dp에 체크 2. 모든 무게에 다시한번 추를 빼주며(반대쪽 저울에 올려놓으며) dp체크 사실 같은 추를 두번사용하는 즉 왼쪽에도 오른쪽에도 올려놓는 경우를 체크하기는 하나 양쪽에 올려봤자 안올렸을 때의 dp와 같으므로 문제없다. (같은걸 두번 더하거나 두번뺄때가 아니면 결과 집합은 같다.) import sys input = sys.stdin.readline chu_N = int(input()) chu_list = list(map(int,input().split())) glass_ball_N = int(input()) ball_list = list(map(int,input().split())) dp_chu = {i:False for i in range(sum(ch..

n = int(input()) lst = list(map(int, input().split())) # 원소 제외 없는 결과, 원소 하나 제외한 결과 dp = [[0, 0] for _ in range(n)] # 초깃값 : 나자신 or 나를 제외한 경우. dp[0] = [lst[0], -999999999] for i in range(1, n): # 끊고 출발하거나 이전에꺼에 덧붙히거나. dp[i][0] = max(dp[i - 1][0] + lst[i], lst[i]) # 이전까지의 합에 나를 제외한 경우.(+0이 생략된 값을 이어붙힘), 이전까지의 합에 나를 붙힌경우(생략x) # => 앞에서 -가 생략이 됐고 그게 최적이라면 dp[i-1][1]+lst[i]가 더 커야하고 아니라면 # 앞의 생략이 최적이 아니..