bjchae9627   10달 전

안녕하세요, 최대한 스스로 해결해보려다가 4연속 메모리 초과로 멘탈도 같이 터져서 질문드립니다.

나름 계속 최대한 메모리를 덜 사용하게 코드를 구현을 해보았는데, 어떤 부분에서 메모리가 초과하게 되는지 알려주시면 감사하겠습니다.

질문 게시판의 대부분 테스트 케이스를 돌려보니 답은 제대로 나오는 것 같던데 메모리 초과만 4번 연속이라서 멘탈이 많이 나가네요..ㅠㅠ

evenharder   10달 전

알고리즘은 맞지만, 시간/메모리 측면에서 비효율적입니다.

첫 두 줄을 다음과 같이 바꾸기만 해도 (제 컴퓨터의 Python 3.6에서 실행해봤을 때) 메모리가 1.5GB 이상 필요하고 결국 Python이 MemoryError를 뱉었습니다.

최악의 경우 O(2^N)개의 원소가 possible에 저장되기 때문입니다. 원소가 오름차순일 때 그렇습니다)

possible이 현재 (지금까지의 길이, 마지막 원소)를 담고 있는 것 같은데, 다음과 같이 크기 N 정도의 배열로 접근해보시기 바랍니다.

possible[i] = (i번째 원소를 맨 마지막 원소로 하면서 가장 긴 증가하는 부분 수열의 길이)

bjchae9627   10달 전

덕분에 해결하였습니다! 거의 1시간 가까이 고민했던 것 같은데 정말 감사합니다!

알고리즘 문제 요즘 공부하기 시작한 학생인데 DP 문제가 많이 익숙하지 않네요!ㅠㅠ

메모리와 시간 사이에서 어떤 값을 저장해야 메모리를 효과적으로 사용할 수 있을지,

for문을 최소한으로 사용할지가 아직 익숙하지 않은 것 같습니다ㅠ

앞으로 DP 문제를 풀 때 메모리 역시 최악의 케이스를 고려하도록 해야겠네요.

정말 감사합니다!!

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