cyclone472   2년 전

한 번 연산을 취할 때마다 D / S / L / R중 하나씩을 고른다면 연산을 n번 했을 때 탐색하는 분량은 O(4^n)만큼이 되는 것 아닌가요?

이만큼 연산을 수행하는데도 돌아가려면 n이 아무리 커도 10~15를 넘어가면 힘들 것 같은데

그만큼의 횟수만에 모든 경우에서 해답을 만들 수 있는 이유를 잘 모르겠습니다.

구글링을 해봐도 풀이를 찾지 못해서 질문드립니다.

djm03178   2년 전

브루트포스로 해결이 안 됩니다. 그래서 알고리즘 분류에 나와있는 알고리즘을 써야 합니다.

hellogaon   2년 전

미로 탐색과 같은 BFS문제를 푸셨으니 BFS에 대한 개념을 아신다고 생각하고 답변드릴게요!

이 문제는 완전탐색(브루트포스)이라기보다는 BFS를 사용해야하는 문제입니다!

이 문제는 A에서 B로 변환하기 위해 필요한 최소한의 명령어를 나열하는 문제입니다. 이 때 A, B를 포함한 레지스터에 저장 된 수는 '네 자릿수'입니다!

이를 이용해서 말씀하신 시간복잡도보다 빠르게 문제를 수행할 수 있지요.


한 번 연산을 취할 때마다 D,S,L,R 중 하나씩을 고르지만

예를 들어 1234에서 시작한다고 했을 때

D 연산 시 -> 2468

S 연산 시 -> 1233

L 연산 시 -> 2341

R 연산 시 -> 4123 이 되게 됩니다! 이 숫자들은 1234에서 한 번의 변환만을 거쳐 만들 수 있는 숫자이지요.

D의 연산 결과로 나온 2468에 대해서 보면

D 연산 시 -> 4936

S 연산 시 -> 2467

L 연산 시 -> 4682

R 연산 시 -> 8246

이 되겠지요. 이 수들은 이제 1234에서 두 번의 변환만을 거쳐 만들 수 있는 숫자라는 것을 알 수 있습니다.

이 과정을 모두 보게 된다면 시간복잡도가 매우 크겠지만

우리가 알고싶은 과정은 어떤 네자리 수를 만드는 데 필요한 최소한의 명령어입니다.

즉 우리가 더 적은 횟수로 만들 수 있다고 저장을 해놓았다면 더 이상 볼 필요가 없는 것이겠지요.

예를 들어 1234에서 L연산으로 한 번만에 만들 수 있는 2341에 대하여

1234에서 D연산을 수행한 뒤, (2468) 여러 번의 S연산을 수행하여 2341을 만들 수도 있지만 우리가 원하는 2341을 만들 수 있는 최소한의 명령어는 한 번이겠지요.

이를 좀 더 잘 생각해보면 최악의 경우 0000 ~ 9999만큼만 탐색한다는 것을 알 수 있습니다!

이미 탐색했던 숫자이면 멈추고, 탐색을 하지 않았던 숫자이면 DSLR을 수행해보는 과정을 반복하기에

10000번이상 탐색하지는 않겠지요.

이런 식으로 접근하면 되는 문제입니다!

cyclone472   2년 전

아 이제 제대로 이해가 되었습니다.

자세하고 친절한 답변들 정말 감사드립니다! ㅎㅎ

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