개구리의 개발 블로그 개구리의 개발 블로그

냅색 분류인 것을 보고 풀었기 때문에 일단 2차원 배열을 만들어야겠다는 생각을 했다. 풀긴 했지만 코드가 깔끔하지도 않고 시간도 꽤나 오래 걸렸다. 1106번 문제를 풀기 전에 1차원 배열을 이용해 평범한 배낭 문제를 풀이하는 방법을 알아보자. 0. 일반적인 냅색 문제 풀이(1차원 / 2차원 배열 이용) 12865번 평범한 배낭 문제를 기준으로 설명하겠습니다. https://www.acmicpc.net/problem/12865 2차원 배열에서 dp[i][j]에 i번째 보석까지 j 무게를 사용했을 때 얻을 수 있는 최대 가치를 저장한다. 모든 보석에 대하여 1에서 최대 용량까지 반복문을 실행하며 dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost]+ benefit)로 갱신한다. 2차..

백준 15681번 트리와 쿼리 파이썬 문제 링크 - https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 반례를 찾는 것이 중요하다. 문제의 로직을 세울 수 있는 것만큼이나 중요한 것 같다. 쉬운 문제였지만 쉬운 반례를 찾지 못해 한참을 헤맸다. 1. 코드 #트리와 쿼리 (tree + dp ) 220503 #dp[node] = 1 이후에 #if len(tree[node]==1) : ret..

백준 1102번 발전소 파이썬 문제 링크 -https://www.acmicpc.net/problem/1102 1102번: 발전소 첫째 줄에 발전소의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 발전소 i를 이용해서 발전소 j를 재시작할 때 드는 비용이 주어진다. i줄의 j번째 값이 그 www.acmicpc.net 오랜만에 재밌는 DP 문제였다. 처음에는 문제를 보자마자 백트래킹으로 풀어야겠다고 생각했다. 그런데 생각해보면 A발전소를 고칠 수 있는 모든 발전소에 대한 경우를 탐색하기 때문에 가지치기가 불가능한 상황이다. 현재 상황에서 정상 작동하고 있는 모든 발전소가 A개이고 정상 작동하지 않는 모든 발전소가 B개라면 총 A*B개의 발전소를 고치는 조합이 존재한다..

백준 1182번 부분수열의 합 파이썬 문제 링크 - https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 부분수열은 연속할 필요 없이 주어진 수열에서 원소를 중복 없이 선택하면 된다. 즉, 주어진 수열의 순서가 바뀌어도 똑같은 답을 갖게 된다. 처음에는 백트래킹으로 시도했다. 전체 수열에서 원소를 선택하는 경우와 선택하지 않는 경우를 나누어 탐색한다. 하지만 DFS 도중에 가지치기 되는 경우가 없기 때문에 사실상 ..

백준 2213번 트리의 독립집합 파이썬 출처 - https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 트리에서 DP를 사용하는 문제였다. 독립집합의 크기를 구하는 것은 쉽게 생각할 수 있었다. 백준 트리DP 알고리즘 분류에서 가장 위에 있는 SNS 문제와 거의 유사했다. 경로를 구하기 위해서 따로 추적을 하는 함수를 작성했는데 간단하게 만드는 방법도 존재할 것 같다. 1. 풀이 1. 최대값 구하기 트리의 독립집합에 포..

백준 2208번 보석줍기 파이썬 출처 - https://www.acmicpc.net/problem/2208 2208번: 보석 줍기 화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1 ≤ N ≤ 100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득 www.acmicpc.net 까다로운 DP를 풀어보고 싶어서 검색해서 풀었는데 생각보다 쉽게 풀렸다. 투 포인터 생각도 났는데 최댓값을 구해야 되는 문제이기 때문에 일단 구간합부터 구하고 시작했다. 1. 풀이 보석은 반드시 M개 이상 연속해서 주워야 한다. 즉 길이가 M이상인 구간합 중 최대를 찾으면 된다. dp[i][0]에는 현재 보석을 선택하지 않았을 때 최대 구간합을 ..

백준 21757번 나누기 파이썬 문제 링크 - https://www.acmicpc.net/problem/21757 21757번: 나누기 $N$개의 정수 수열 $A_1, A_2, \dots , A_N$이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또, 각 부분의 합은 모두 같아야 한다. 즉, 어 www.acmicpc.net 누적합과 dp를 활용하여 풀어야 했는데 dp 점화식을 세우는 것이 생각보다 쉽게 떠오르지 않아서 당황했다. 현재 풀이보다 dp부분을 좀 더 깔끔한 코드로 작성할 수 있을 것 같다. 처음 시도할 때는 구간합 배열에서 크기가 같은 구간이 되도록 나누어주는 divide 함수를 구현하여 풀고자 했다. 즉, 구간합 배열을 2등분..