반응형
문제: 외발뛰기
언어: 자바
난이도는 중 정도 되는 듯 하다. 실행 시간 제약이 있어서 사용하는 알고리즘에 주의를 해야 한다.
처음에 사용했던 방법은 (0,0) 위치를 Queue에 삽입하고
1) Queue에서 위치를 하나 꺼내서 (n-1,n-1)에 도달하였는지 확인한다.
2) 1)에서 도달하지 않았으면 해당 위치에서 이동할수 있는 다음 위치를 계산하여 그 위치를 Queue에 넣는다.
[1] 다음은 그 코드이다.
이 코드로 제출 하면 시간 초과가 발생한다. 최적화 할수 있는 방법이 없을까?
연산을 줄이려면, 다음 위치가 방문 했었는지를 판단해서 방문하지 않았을 경우만 Queue에 넣으면 된다. 즉 어떤 위치를 Queue에 넣을때 이 위치를 Queue에 넣은 적이 있는지 flag를 두고 Queue에 넣은 적이 있으면 다음번에는 Queue에 넣지 않는 것이다. Memoization 기법과 동일하다.
[2] 다음은 그 코드이다.
물론 다음처럼 Recursive 하게, 그리고 Memoization 기법을 이용해서 해결 가능하다.
[3] 다음은 그 코드이다.
위 코드 [2]의 실행 시간은 algospot 에서 실행 기준으로 616ms, [3]은 652ms 로 근소하게 차이가 난다. 아무래도 Recursive한 방법은 함수 호출에 따른 코스트가 따르는 것 같다.
물론 [1]의 경우 시간 초과가 발생한다.
반응형
