인프런 커뮤니티 질문&답변
작성한 질문수
4 - B 질문있습니다.
해결된 질문
작성
·
21
0
다행히 강의를 듣고 문제를 풀긴 했습니다.
하지만 하나의 의문이 풀리지 않아 질문을 올려봅니다.
이 문제의 요점은 다음과 같다고 저는 생각합니다.
1. 결론적으로 우리가 보고싶은것은 BF를 통해 모든 행과 열을 순회하면서 뒤집을 때의 결과를 체크하고 최소값을 구하는 것이다. 하지만 이것은 2^40이기에 시간범위를 넘어선다.
2. 그러므로 2^40을 피하기 위해 모든 행들을 순회하면서 뒤집은 한 다음, 모든 열을 뒤집는 대신 T가 많은 열만 뒤집음으로서, 2^20 * 2^20 대신, 2^20 + @로 줄일 수 있다.
그런데 이렇게 할거면 행 역시 완전탐색인 2^20을 피하기 위해 T가 많은 행만 뒤집을 수 있지 않을까 라는 생각이 계속해서 드네요.
T가 많은 행 만을 뒤집었을때 답이 틀리게 나오는걸 보면 분명 무슨 이유가 있을건데, 반례가 떠오르지 않고 찝찝해서, 행과 열 둘다 T가 많은 것만 뒤집었을때 답이 틀리는 원인이 궁금해 질문을 올려봅니다.
>>
간단하게 생각하시면 됩니다.
-> THT 라는 상황을 가정해볼게요.
이 열 1, 2, 3 열에 대해 뒤집는 모든 경우의 수가 끝났습니다.
이제 경우의 수는 이 행 -> 을 뒤집느냐. 아니면 안뒤집느냐. 라는 경우의 수밖에 없죠?
이 때 어떤 경우의 수가 최적의 수일까요?
뒷면이 위를 향하는 동전 개수를 최소로 만드는 것이 가장 최적의 수 아닐까요?
커뮤니티를 봤을 때 비슷한 질문에서 이런 답을 보았는데 이걸 읽어도 이해가 안되네요ㅠㅠ.
감사합니다.
답변 2
0
안녕하세요 비스킷님 ㅎㅎ
그런데 이렇게 할거면 행 역시 완전탐색인 2^20을 피하기 위해 T가 많은 행만 뒤집을 수 있지 않을까 라는 생각이 계속해서 드네요.
-> 2^20 미만으로 나올수는 없습니다. 저기서 T가 많은 행을 뒤집는 것은 열로서의 모든 경우의수를 판단했고 행을 기반으로 뒤집는 경우의 수가 남았을 때 2가지 경우의 수 , 예를 들어 THT에서 뒤집으면 HTH가 되는 것과 안뒤집으면 현상유지가 되는 경우의 수밖에 없습니다. 이 때는 많은 것을 뒤집으면 정답이 되는 것이죠.
처음부터 T가 많은 행만 뒤집는것이 어떤 예제에서는 최적해가 될 수도 있지만 제가 생각했을 때 그걸 증명하기에는 어려운 것 같습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다.
비스킷님, 질문 주셔서 감사합니다. 이 문제의 핵심은 “동전 뒤집기의 최적화를 어떻게 접근할 것인가?“입니다. 특히 비트마스킹을 통해 모든 가능한 상황을 탐색하면서 최대한 계산을 줄이는 방법인데요, 행과 열을 모두 순회하며 최적의 결과를 찾는 과정에서 몇 가지 중요한 점이 있습니다.
문제의 핵심 정리:
** 전체 탐색의 복잡도 **: 말씀하신 대로 단순히 2^40의 모든 경우의 수를 탐색하는 것은 현실적으로 불가능합니다. 따라서 문제를 해결하기 위해서는 모든 행이나 열을 모두 거꾸로 세어보는 방식이 아닌, 몇 가지 전략을 사용해야 합니다.
** 최적화 아이디어 **:
- 한 번에 행이나 열을 완전히 뒤집는 것: 이는 결과적으로 특정 열이나 행의 일부를 뒤집어 순위를 최소화합니다. 하지만 이때, ‘열의 값이 많은 경우에만 뒤집기’의 접근은 문제 전체의 복잡성을 줄이는 핵심 중 하나입니다.
- 뒷면의 판별: X나 T가 많은 특정 상황에서 행 전체를 뒤집는 것과 같은 전략을 사용해 동전의 방향을 최대한 계속 바꾸는 것을 막는 것이 포인트입니다.
- 한 번에 행이나 열을 완전히 뒤집는 것: 이는 결과적으로 특정 열이나 행의 일부를 뒤집어 순위를 최소화합니다. 하지만 이때, ‘열의 값이 많은 경우에만 뒤집기’의 접근은 문제 전체의 복잡성을 줄이는 핵심 중 하나입니다.
질문 주셨던 부분 관련:
질문에서는 행도 열과 같은 방식으로 T가 많은 것만 뒤집으면 되는지에 대한 의문이 있었습니다. 이 경우에는 행에 어느 방향으로 뒤집는 것이 효율적인가에 대한 판단이 필요합니다.
행과 열을 둘 다 뒤집으면 여러 가지 조합으로 인해 전체 최적화가 틀어질 수 있습니다. T가 많은 열 뿐만 아니라 행도 같이 많이 뒤집으면, 엉뚱한 조합이 발생하여 뒤집기 조건이 서로 상쇄될 수 있기 때문입니다.
관련 답변 URL:
- 아래 링크에서 강사님의 답변이 전체적으로 이러한 질문을 해소하는 데 도움이 될 것입니다. 비슷한 원리에서 문제를 해석해주실 수 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.