jintak0401   10달 전

처음에 이 문제를 풀려고 할 때 리스트를 이용해서 다이나믹 프로그래밍을 했으나 메모리 초과로 실패했습니다.  

그래서 리스트 대신 해시로 구현되어있는 딕셔너리로 문제를 해결하였습니다.


그래서 궁금한게 생겼습니다. 다이나믹 프로그래밍을 딕셔너리로 하여 키값으로 접근하는 것과 리스트로 하여 인덱스로 접근하는 것.

둘의 실행시간에서 차이가 많이 날 수 있는지 궁금합니다. 딕셔너리는 해시로 구현되어 있으므로 웬만해서 O(1) 로 접근하는 것으로 알고 있는데,

이 문제 뿐만 아니라 다이나믹 프로그래밍이 필요한 다른 문제들에서도 리스트 대신 딕셔너리를 이용해도 되는지 궁금합니다.

wider93   10달 전

top-down 방식이라면 모든 값을 저장하려고 애쓸 필요가 없기 때문에 딕셔너리가 더 좋을 이유는 많습니다.

댓글을 작성하려면 로그인해야 합니다.