Inflearn Community Q&A
asked
7-N 시간 복잡도 접근 질문드립니다.
Written on
·
230
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
단순히 한 자리에서 5번 호출, 영향을 받을 수 있는 지점 99개가 있으므로 최대 약 5^99 이라고 생각했거든요.
5x5의 색종이를 붙이니까 영향 받는 타일이 더 생략될 수는 있겠다 싶었지만 좀 그래도 좀 클 것이라고 생각했습니다.
혹시 선생님이 이 문제 어떻게 접근하셨는지 궁금합니다
Quiz
동적 계획법(Dynamic Programming)을 적용하기 위한 주요 조건은 무엇일까요?
탐욕적 선택 속성, 최적 부분 구조
최적 부분 구조, 중복되는 부분 문제
중복되는 부분 문제, 결정론적 결과
탐욕적 선택 속성, 메모이제이션
Answer 2
0
0
안녕하세요 ㅎㅎ
mch님이 질문하시는 것을 보면 실력이 늘어간다는 것을 간접적으로 느끼고 있습니다.
좋은 질문입니다. ㅎㅎ
얼핏보면 100개의 격자점에서 상태값은 총 5개이기 때문에 5^100이라고 생각할 수 있습니다.
그러나 문제 조건을 보시면.
1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.
색종의 갯수의 제한이 있습니다.
자 그러면.
이렇게 생각할 수 있습니다.
100개의 격자점에서 25개의 상태값을 순서와 상관없이 놓는 경우의 수죠.
100C25라고 생각이 듭니다.
근데 이것또한 큰 수입니다.
242,519,269,720,337,121,015,504 이죠.
그러나 꼭 이래야만 할까요?
5x5 짜리 색종이 4개면 100개의 격자점은 모두 채워지게 됩니다. 그리고 이 경우의 수는 한개밖에 없죠.
자 그러면...
100개의 격자점을 대충 4x4로 감싼다고 했을 때 거의 다 채워지기 때문에 4개정도가 들어가기 때문에
100C4이면 -> 격자점이 다 채워지는 구나 -> 100 C4는 3,921,225(400만) 수준이고 -> 물론 그 외의 격자점을 다른 색종이로 채워야 하겠지만.. -> 400만이면 충분하지 않을까?
그리고...
사실 이것보다는 더 작을 수 있겠다. 라고 생각하고 들어간 것입니다.
격자점은 0과 1로 이루어져있으며. (즉, 매번 100이 아니다.)
5x5로 채울 수 있는 경우의 수들또한 있으니까요.
그리고 100개의 격자점에 4x4가 아니라 사실은 4x4가 채워지면 채울 수 있는 영역 자체가 제한되기 때문에 더 적을 것이라고 생각했습니다.
처음에는 저도 5^100이라고 생각을 했습니다.
그러나 문제 조건을 보았을 때 10x10, 색종이의 갯수제한 5개를 보고 좀 더 작을 것이다. 라고 판단하고 어느정도 유추하고 -> 완탐 -> 줄일 수 있는 것은 줄여보자 -> 휴리스틱 -> 백트래킹 -> 이거 안되면 그리디로 해보자.
라고 했을 때 백트래킹 단계에서 푼 것 같습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.