나를 위한 기록

https://www.acmicpc.net/problem/1655 문제 접근 이 문제를 접근할 때 가장 단순하게 생각하면 리스트에 숫자를 넣으면서 Sorting 후 중간값을 출력하면 된다고 생각할 것이다. 하지만 제한 시간은 0.1초이고 파이썬 정렬의 시간 복잡도는 O(NlogN)이므로 시간 초과가 나올 것이다. 또 생각했던 방법은 중간값을 저장하는 변수 Center를 두고 Left, Right라는 리스트를 통해 Center보다 작으면 Left에 크면 Right에 넣는 방법을 생각했었다. 하지만 그렇게 되면 중간값을 갱신할 방법이 없었고 다른 사람의 풀이를 통해 Left와 Right를 단순 리스트가 아닌 Heap을 이용하면 중간값을 갱신할 수 있는 솔루션이 될 수 있었다. 따라서 Left를 Max Hea..

https://www.acmicpc.net/problem/12865 문제 접근 처음 이 문제를 봤을 때는 BackTracking을 이용해 해당 물건을 넣는 경우와 안 넣는 경우를 모두 구하려고 시도했다. 그렇게 되면 시간 복잡도가 O(2^N)이 되므로 최대 2^100번 연산을 해야 하므로 시간 초과가 날 수 밖에 없었다. 검색을 통해 이 문제는 다이나믹 프로그래밍을 통해 해결해야 했고 Knapsack 문제라고 불리는 아주 유명한 문제였다. 풀이 과정 N은 물품의 수이고 K는 배낭 무게이다. 물건을 하나씩 넣는 경우와 안 넣는 경우를 배열에 저장하면서 처리하면 된다. 그렇게 되면 O(NK)이 되고 최대 연산량은 10,000,000이므로 제한 시간을 통과할 수 있다. DP 점화식을 표현하면, dp[i][j]..