첫 번째에 이렇게 제출을 하였는데 TLE가 발생하였습니다.
그래서 그냥 cpp로 짜면 통과하겠지 하고 책에 나온 풀이를 먼저 보았는데,
책의 풀이는 제 풀이와 조금 달랐습니다. 저는 다음 것을 포함할지 말지 결정하는 방법으로 풀었고, 책에선 현재 것을 포함할지 말지 결정하는 방법으로 풀려있었습니다
책의 풀이가 더 마음에 들어 이걸 다시 Python으로 옮겨 제출하였는데 통과하였습니다. https://algospot.com/judge/submission/detail/234063
실제로 얼마나 시간차이가 있는지 측정을 해보았는데
100개의 물건으로 실험했을 때에는 20배 (0.09, 1.53),
1000개의 물건으로 실험했을 때에는 200배 차이가 났습니다(1.08, 208)
제 생각엔 첫번째 풀이와 두번째 풀이가 시간복잡도가 같을 것 같았는데 결과적으로 다르더군요. 왜 다를까 한참을 생각해 보았는데 제 머리로는 답이 안나옵니다.. range를 xrange로 바꾸고, 아이템 리스트 구하는 부분을 제거해도 시간차이는 줄지 않았습니다. 두 풀이가 실제로 시간복잡도가 다른가요? 다르다면 왜 다른지 알려주시면 감사하겠습니다.
cache[]에 들어가는 한 개의 값을 채우기 위해서 두번째는 get_max를 한 번만 호출하지만, 첫번째는 남은 물건의 개수만큼 호출하지요. 따라서 O(NW)와 O(N^2W)로 시간복잡도가 다릅니다. 메모이제이션이 아니라 반복형 동적계획법으로 바꿔서 생각해 보시면 이해가 좀더 잘 되실 수도 있고요 ㅎㅎ
항상 친절하게 답변해주셔서 감사합니다.
책의 설명과 첫번째 풀이의 get_max의 각 인수 범위가 같고, 따라서 부분문제 갯수가 같으니 같은 시간복잡도인줄 알았는데 부분문제 하나 구하는데의 복잡도가 달랐군요. 계속 고민중이였는데 답변 감사드립니다.
질문이 조금 더 남았는데요.. 아직 시간복잡도에 대해 감이 잘 안와서 그러는데, 혹시 첫번째 풀이의 시간복잡도가 어떻게 N^2W가 나오는지 조금 자세히 설명해 주실 수 있으신가요?
vio
https://algospot.com/judge/submission/detail/234092
첫 번째에 이렇게 제출을 하였는데 TLE가 발생하였습니다.
그래서 그냥 cpp로 짜면 통과하겠지 하고 책에 나온 풀이를 먼저 보았는데,
책의 풀이는 제 풀이와 조금 달랐습니다. 저는 다음 것을 포함할지 말지 결정하는 방법으로 풀었고, 책에선 현재 것을 포함할지 말지 결정하는 방법으로 풀려있었습니다
책의 풀이가 더 마음에 들어 이걸 다시 Python으로 옮겨 제출하였는데 통과하였습니다.
https://algospot.com/judge/submission/detail/234063
실제로 얼마나 시간차이가 있는지 측정을 해보았는데
100개의 물건으로 실험했을 때에는 20배 (0.09, 1.53),
1000개의 물건으로 실험했을 때에는 200배 차이가 났습니다(1.08, 208)
제 생각엔 첫번째 풀이와 두번째 풀이가 시간복잡도가 같을 것 같았는데 결과적으로 다르더군요. 왜 다를까 한참을 생각해 보았는데 제 머리로는 답이 안나옵니다.. range를 xrange로 바꾸고, 아이템 리스트 구하는 부분을 제거해도 시간차이는 줄지 않았습니다. 두 풀이가 실제로 시간복잡도가 다른가요? 다르다면 왜 다른지 알려주시면 감사하겠습니다.
10년 전