인프런 커뮤니티 질문&답변
작성한 질문수
7-N 시간 복잡도 질문이 있습니다.
해결된 질문
작성
·
116
0
문제링크: https://www.acmicpc.net/problem/17136
이번 7주차 DP 하면서
자꾸 TLE 뜨다 보니깐 이게 완탐이나 백트래킹으로 가능한지 감이 잘 안잡혀요 ㅠㅠ
큰돌님은 이 문제 바로 백트래킹으로 접근해도 된다라는걸 어떻게 파악하신건가요?
예를 들어서 테스트케이스 7번
0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1가 있고 큰돌님의 코드를 돌려보면 [1,1] 위치에서 만들어 질 수 있는 정사각형의 최대 사이즈는 2이므로 [1,1] 위치에서 2 크기의 정사각형의 색을 칠하면서 탐색하는데 [1,1]의 위치에서는 2의 크기로 색칠하고 시작하면 답이 안된다는걸 사람의 눈으로는 파악이 돼죠 왜냐하면 [1, 2]를 기준으로 크기 4의 정사각형을 그릴 수 있다는걸 알기 때문에요.
그럼에도 불구하고 큰돌님은 위 상황을 인지한 상태에서 백트래킹으로 시도를 해보신건가요? 아니면 이게 백트래킹으로 풀린다는걸 아시고 푸신건가요?
답변 2
1
안녕하세요 희천님 ㅎㅎ
큰돌님은 이 문제 바로 백트래킹으로 접근해도 된다라는걸 어떻게 파악하신건가요?
>>
처음에는 저도 완탐생각했습니다. ㅎㅎ
그러나 완탐으로 해볼까 생각을 하자면..
얼핏보면 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점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다.
박희천님의 질문에 대하여, 백트래킹과 시간 복잡도 관련하여 큰돌님께서 다른 질문에 제공하신 답변이 도움이 될 수 있을 것 같습니다. 큰돌님께서 백트래킹을 이용하여 문제를 접근하는 판단 기준이나 방식에 대한 설명이 포함되어 있는 내용입니다.
7-V 질문 있습니다의 답변에서, 시간 초과의 원인과 백트래킹이나 동적 계획법(DP)의 풀이 방식에 대한 조언이 있습니다. 특히 백트래킹 풀이에서 메모이제이션(checking) 로직의 중요성과 올바른 접근 방법에 대해 설명하고 있습니다. 이 답변은 백트래킹을 사용하실 때 어떻게 시간 초과와 같은 문제를 해결해 나갈지에 대한 인사이트를 제공할 것입니다.
3-I 17071 문제 질문있습니다에서는 특정 문제에 접근할 때 필요한 데이터 구조의 차이(이 경우에는 배열의 차원수)를 설명하면서, 그 결정이 왜 중요한지에 대해 큰돌님께서 밝히고 계십니다. 이 답변 역시 문제 해결 방식을 선택할 때의 고려사항에 대한 이해를 돕습니다.
질문하신 문제 17136번: 색종이 붙이기는 백트래킹 방법을 사용해야 하는 경우들과 그런 방법을 선택할 때의 고려사항에 대한 좋은 예시입니다. 백트래킹으로 접근해도 되는지의 판단은 문제의 제한 사항, 가능한 상태 공간의 크기, 그리고 하위 문제들이 반복되는지 여부 등을 고려하여 결정되어야 합니다. 또한, 큰돌님의 답변에서 설명하듯이, 메모이제이션과 같은 기술을 활용하여 백트래킹의 성능을 향상시킬 수 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
도움이 되었습니다.
감사합니다!