ddss21   7년 전

처음엔 배열 전체를 반복문으로 탐색하게 했더니 7%에서 시간초과가 나왔고, 나름 메모이제이션(?) 방식으로 설계하여 BFS방식으로 접근했는데 21%에서 시간초과가 나네요..


시간 초과에 관해 제가 고려하지 못한 측면에 대하여 조언해주시면 감사드리겠습니다..

kesakiyo   7년 전

큐에 삽입하기 전에 방문 처리를 해 주세요.

그렇지 않다면 똑같은 좌표가 큐에 여러번 들어갈 수 있습니다.

그리고 visited체크를 해주는것은 메모이제이션과 관련이 없습니다.

메모이제이션은은 동일한 계산을 계속해서 반복해야할 때 한번 계산 한 뒤 이를 메모리에 저장해둔뒤 다시 사용하는 최적화 기법중 하나로

다이나믹 프로그래밍과 밀접한 연관이 있습니다.

ddss21   7년 전

중복 참조될 수 있는걸 구현안했었네요 감사합니다!

아~ 그렇군요! 경로를 반복하여 탐색할것을 다음에 탐색해야할 부분만 큐에 저장하는 것으로 생각하여 메모지에이션 이라고 생각했었습니다. 가장 삼각형 숫자 큰값찾기(?)나 높은 점수로 계단오르기 할때랑 비슷한거라고 생각했었는데 아닌가보군요.. 아직 한참 멀었나봅니다ㅜㅜㅎㅎ 아무쪼록 조언해주셔서 감사합니다! 복받으세요!

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