분할 정복 검색 결과

해당 글 2건

하노이탑 이동 순서 (boj.kr/11729)

하노이탑 이동 순서 (boj.kr/11729) 문제 해설 및 주의사항 - 하노이 탑의 최소 이동 순서를 출력하는 프로그램을 작성하자. - 첫 번째 장대에 쌓인 원판의 개수 N 이 주어진다. 해설 적용한 레시피 / 방법론 + 접근법 풀이 1. 규칙을 찾아보자. - m 개의 원판을 3번째 장대로 옮긴다고 해보자. 그렇다면, 1. 먼저 위의 m - 1개의 원판을 2번째 장대로 옮기고 ( a_(m-1) ) 2. 남은 1개의 원판을 3번째 장대로 옮기고 ( + 1) 3. 2번째 장대의 m - 1 개 원판을 3번째 장대로 옮긴다. ( a_(m-1) ) 최단 이동 횟수의 점화식은 a_n = 2a_(n - 1) + 1 이 될 것이다. 2. 함수의 구현 - 재귀를 호출 할 때 달라지는 것은 무엇일까 a. 목적지 장대 (..
ps/분할 정복 2021. 10. 14. 23:07

종이의 개수 (boj.kr/1780)

종이의 개수 (boj.kr/1780) 문제 해설 및 주의사항 N x N 종이의 각칸에는 -1 0 1 이 저장되어 있다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고(divide), 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. -1로 만 채워진 종이. 0으로만. 1로만 채워진 종이의 개수를 구해내자. 해설 적용한 레시피 / 방법론 + 접근법 풀이 1. 브루트 포스? - N 의 최대 크기는 3^7 = 2,187개 이다. 정사각형 최대 크기는 4,782,969. 전체 정사각형에서, 종이에 써있는 수가 같은 수 임을 알기 위해 반복하는 최대 갯수는 N / 9 * 9 (1번째 분할) + N / 81 * 9 (2번째 분..
ps/분할 정복 2021. 10. 14. 22:09