12094번 - 2048 (Hard)
이 문제를 분기한정법(브랜치앤 바운드)을 사용해 풀었는데, 우선순위 큐에다가 'Package 구조체'를 매번 큐에 삽입하니 다른 사람들보다 아득하게 큰 메모리 사용량이 나왔습니다.
물론 512mb에 맞춰서 제작했기 때문에 메모리 초과는 발생하지 않았지만 대체 다른분들은 어떻게 메모리 3000KB내의 코드로 한 걸까요?
분기한정법을 쓰면서도 말판의 상태를 훨씬 적은 메모리크기로 상태를 캐싱하는 방법이 있는 것인지?
아니면 제가 세운 분기한정법에 최소 준하는 수준의 백트래킹 알고리즘으로 푼 것인지? 궁금합니다.
++ 분기한정법은 메모리를 많이 쓸 수밖에 없는 방법인지도 궁금합니다.
저는 현재 보드에서 아무리 답을 키워도 기존의 답을 갱신할 수 없는 경우를 제외하고는 백트래킹으로 전수탐색했습니다.
아하!
생각해보니 그렇네요...
댓글을 작성하려면 로그인해야 합니다.
jaboazagil 1년 전
이 문제를 분기한정법(브랜치앤 바운드)을 사용해 풀었는데, 우선순위 큐에다가 'Package 구조체'를 매번 큐에 삽입하니 다른 사람들보다 아득하게 큰 메모리 사용량이 나왔습니다.
물론 512mb에 맞춰서 제작했기 때문에 메모리 초과는 발생하지 않았지만 대체 다른분들은 어떻게 메모리 3000KB내의 코드로 한 걸까요?
분기한정법을 쓰면서도 말판의 상태를 훨씬 적은 메모리크기로 상태를 캐싱하는 방법이 있는 것인지?
아니면 제가 세운 분기한정법에 최소 준하는 수준의 백트래킹 알고리즘으로 푼 것인지? 궁금합니다.
++ 분기한정법은 메모리를 많이 쓸 수밖에 없는 방법인지도 궁금합니다.