PACKING문제 답안으로 짠 두개의 풀이의 시간복잡도에 대해 질문드립니다.

  • vio
    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년 전
4개의 댓글이 있습니다.
  • JongMan
    JongMan

    cache[]에 들어가는 한 개의 값을 채우기 위해서 두번째는 get_max를 한 번만 호출하지만, 첫번째는 남은 물건의 개수만큼 호출하지요. 따라서 O(NW)O(N^2W)로 시간복잡도가 다릅니다. 메모이제이션이 아니라 반복형 동적계획법으로 바꿔서 생각해 보시면 이해가 좀더 잘 되실 수도 있고요 ㅎㅎ


    10년 전 link
  • vio
    vio

    항상 친절하게 답변해주셔서 감사합니다.
    책의 설명과 첫번째 풀이의 get_max의 각 인수 범위가 같고, 따라서 부분문제 갯수가 같으니 같은 시간복잡도인줄 알았는데 부분문제 하나 구하는데의 복잡도가 달랐군요. 계속 고민중이였는데 답변 감사드립니다.
    질문이 조금 더 남았는데요.. 아직 시간복잡도에 대해 감이 잘 안와서 그러는데, 혹시 첫번째 풀이의 시간복잡도가 어떻게 N^2W가 나오는지 조금 자세히 설명해 주실 수 있으신가요?


    10년 전 link
  • Being
    Being

    대충 (부분문제 개수) * (부분문제당 시간복잡도) 로 생각하시면 많은 경우 맞습니다.


    10년 전 link
  • JongMan
    JongMan

    혹시 책이 있으시다면 214페이지에서 간단히 설명하고 있습니다.


    10년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.