러닝머신 하는 K-공대생

정말 심심해져서 최근 교내 대회 문제를 업솔빙하고자 '바벨탑' 문제 를 풀다 세그먼트 트리가 기억이 안나서 다시 복습하고 재귀적 방식과 비재귀적 방식으로 구현해 보았다. 개인적으로 탑다운으로 짠게 직관적이고 레이지나 그 외 여러 확장적 측면에서 편한 것 같은데 Python으로 세그트리 문제들 풀어보면 성능적인 면은 확실히 Bottom-Up 방식이 유리한 것 같다. 1. 재귀적 방식 구현 class SegmentTree: def __init__(self, arr): self.n = len(arr) self.tree = [0] * (4 * self.n) self.build(arr, 1, 0, self.n - 1) def f(self, a, b): return min(a, b) def build(self, a..

1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net Abstract: 오늘 벡터 문제를 풀다가 집에 와서 백준에 벡터 관련된 문제가 없을까 풀어보았다. 벡터 정의만 알면 돼서 아이디어 떠올리는 것은 쉽고 어떻게 구현할지 고민을 많이 했다. 고민하다 백트래킹으로 조합을 계산했고 추가적으로 파이썬 내장 라이브러리인 itertools의 combination 함수를 이용하여 편하게 풀었다. 문제 접근 및 해설: 문제에서 중요한 것은 P에 속하는 모든 점은 한 번씩 쓰여야 하므로 각 벡터의 시작점과 끝점은 다른 ..

1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제자체가 매우 간단해보여서 리스트를 이용해 정렬한 후 중간값을 출력했는데 시간초과가 떴다. 정렬을 하는데 O(nlogn) 걸리고 이를 N번 반복한다고 하면 대충봐도 O(N^2)은 가뿐히 넘긴다. 여기서 N이 1보다 크거나 같고, 100,000보다 작거나 같으므로 시간초과가 뜨는 것은 당연하다. 따라서 매 입력이 들어올 때마다 O(nlogn) 보다 작은 시간복잡도를 가지는 방법으로 중간값을 찾아야 한다. 전혀 시간복잡도를 줄일 방법이 떠오르지 않..

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 일단 DP로 풀 수 있을 것 같아서 점화식부터 세우려고 시도했다. D(i,k)를 i번째 인덱스 이후 중, k이하의 무게 중 가치의 합의 최댓값 으로 두고서 생각을 했다. 보통 조합론적 증명을 할 때 처럼 자신을 포함시킬 때와 포함하지 않을 때 경우를 나누어 V[i] 를 i번째 인덱스의 가치, W[i]를 i번째 인덱스의 무게라고 했을 때 i번째와 i+1번째 관계를 이끌어냈다. 일단 점화식을 유도하긴 ..