러닝머신 하는 K-공대생

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번째 관계를 이끌어냈다. 일단 점화식을 유도하긴 ..

아직 문제풀이 경험이 적어서 이진탐색 문제를 풀 때마다 매번 부등호의 등호를 결정하는 것이 헷갈린다. 이진탐색 관련 문제 풀이 경험을 늘려 이 점을 극복해야겠다 (혹시 이진탐색을 할 때 부등호 등호와 출력값을 정하는 팁이 있다면 댓글로 공유 부탁드립니다.!) 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 1에서부터 최대랜선길이를 각각 start,end로 시작해서 각 wire의 길이를 mid로 나눈 값의 합을 cnt라고 하였다. 아래 그림에서 보라색 영역은 가능한 랜선의 길이이며 ..