Inflearn Community Q&A
asked
8-F 유형의 문제를 풀 때 어려운 점
Written on
·
27
0
안녕하세요 큰돌님.
8-F처럼 톱니바퀴나 다이얼을 돌려서
특정한 상태로 만드는 데 필요한 최소 횟수를 구하는 문제를 풀 때 어려운 점이 있습니다.
이런 문제의 풀이는 주로 왼쪽 아니면 위쪽부터 탐색을 진행해 답을 찾습니다.
하지만, 저는 내심 이런 불안감이 듭니다.
'만일 최적의 횟수가 맨 위가 아니라, 중간이나 맨 하단에서 다이얼을 돌리는 방법에서 비롯된 거면 어떡하지'.
'현재 위치 N에서 다이얼을 맞추지 않고, 그 다음의 위치에 있는 다이얼을 먼저 맞춘 후, 다시 위치 N으로 돌아와서 다이얼을 맞추는 게 최적일 수도 있지 않을까.'
위와 같이 다양한 가능성을 염두하니, 풀이법을 떠올리는 데 어려움이 많습니다.
제가 문제를 접근하는 방식이 어디가 잘못되었는지, 어떻게 고쳐야 하는 지 궁금합니다
Answer 1
0
안녕하세요 레고님 ㅎㅎ
그렇게 최적의 경우의 수를 생각하는 것자체는 너무 좋습니다. ㅎㅎ
다만 순서를 좀 조정하는게 좋을 것 같아요. 무식하게 모든 경우의 수 -> 그 다음 그게 안된다면 -> 최적 이렇게 순서만 정하면 더 좋아질 것 같습니다.
사실 그리고 다음의 생각을 볼까요?
'만일 최적의 횟수가 맨 위가 아니라, 중간이나 맨 하단에서 다이얼을 돌리는 방법에서 비롯된 거면 어떡하지'.
-> 맨하단에서 다이얼을 돌리는 것은 있을 수 없습니다.
문제 지문을 보시면... 다음과 같습니다
현재 자물쇠의 상태와 세준이의 비밀번호가 주어질 때, 자물쇠를 최소 몇 번 돌려야 풀 수 있는지 구하는 프로그램을 작성하시오.
즉, 현재 자물쇠의 상태로부터 -> 돌리기 때문에 갑자기 자물쇠의 끝 0부터 돌린다거나 9부터 돌린다거나는 있을 수 없습니다.
'현재 위치 N에서 다이얼을 맞추지 않고, 그 다음의 위치에 있는 다이얼을 먼저 맞춘 후, 다시 위치 N으로 돌아와서 다이얼을 맞추는 게 최적일 수도 있지 않을까.'
-> 이부분은 간단한 예시를 통해 반례를 찾아야 합니다. 이런 생각이 들지만 -> 어? 반례는 없을까? 하고 생각하는 로직이 습관화 되어야 합니다.
예를 들어
aaa -> bbb 로 가야 한다고 해볼게요.
aaa -> abb -> bbb 로 가는 것보다.
aaa -> bbb로 가는게 자명합니다.
즉, 현재위취에서 다이얼을 맞추는게 최적임을 간단한 예시로 어느정도 증명한 것을 볼 수 있습니다. (실제 증명은 이것보다 복잡하지만 간단하게 이렇게 반례 들면서 어느정도 타당한지를 가늠해봐야합니다.)
순서, 그리고 반례생각만 더 하시면 좋아지실겁니다. ㅎㅎ
감사합니다.
안녕하세요 ㅎㅎ
다이얼을 맞추는 최적의 방법이 j를 먼저 맞추고, i를 맞춘 다음에 ... 마지막으로 k를 맞추는 것입니다.
-> 혹시 예시 좀 더 자세히 들어주실 수 있으실까요?
네 예시를 들어드리겠습니다.
세준이의 자물쇠 크기 N=7
현재 상태: 1234567
목표 비밀번호: 1764532
✅ 최소 회전 순서 설명:
먼저 가운데 세 개 (2~4번)를 -2만큼 반시계로 돌려서
1234567→1132347
(2~4번:234→012)그 다음 앞의 세 개 (1~3번)를 +1만큼 시계 방향으로 돌려서
1132347→2242347
(1~3번:113→224)마지막으로 뒤쪽 세 개 (5~7번)를 -1만큼 반시계로 돌려서
2242347→1764532
(5~7번:347→532)
안녕하세요 레고님 ㅎㅎ
1234567
->
1132347
이거 예시가 잘못된 것 같습니다.
차이를 보면 0, -1, 0,-2,-2,-2,0 입니다. 한번돌려서 이렇게 나올 수 없습니다.
감사합니다.
감사합니다, 큰돌님.
그런데, 첫번째 질문을 제가 잘못 드린 것 같습니다.
제가 여쭙고 싶은 건 다음과 같습니다.
다이얼의 인덱스 i < j < k 순으로 있다고 할 때(실제로는 앞의 3개보다 더 많은 다이얼 존재),
다이얼을 맞추는 최적의 방법이 j를 먼저 맞추고, i를 맞춘 다음에 ... 마지막으로 k를 맞추는 것입니다.
이 경우, 왼쪽부터 다이얼을 맞추는 알고리즘을 사용할 경우, 중간부터 맞추지 않았음에도 불구하고 어떻게 최적의 수를 구할 수 있는지 궁금합니다.