목록분할정복 (3)

슈뢰딩거의 고등어

[프로그래머스] 쿼드압축 후 개수 세기

https://programmers.co.kr/learn/courses/30/lessons/68936 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr [해결방법] 분할정복 분할한 맵의 크기가 1일 때까지 분할한다. 분할한 맵의 인자들이 모두 같은 수인지 확인하는 과정이 필요하다. #include #include #inclu..
알고리즘 2022. 3. 19. 16:52
[백준] 2163 초콜릿 자르기

https://www.acmicpc.net/problem/2163 2163번: 초콜릿 자르기 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿 www.acmicpc.net 분할 정복 문제 항상 최소가 되려면, 반으로 쪼개면 된다. [풀이] 1. 가로가 1이 아니라면 반으로 쪼개자 2. 가로가 1이고, 세로가 1이 아니라면 세로를 반으로 쪼개자 매번 쪼갤 때마다, count를 올려주자. divide_i : 세로쪼개기 divide_j : 가로쪼개기 #include #include using namespace std; int answer; void divide_i(..
카테고리 없음 2022. 2. 25. 18:32
[백준] 1074 Z 분할정복

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 분할 정복 문제이다. 각 블록에 번호를 매기는 식으로 단순 구현을 하려고 했지만, 시간 초과가 걸려서 분할정복 방법을 사용했다. 분할정복은 큰 문제를 쪼개 계산하는 방법을 말한다. DP (동적프로그래밍) 과 비교가 자주되고, 둘의 차이는 DP 는 식의 결과를 저장해놓고 반복해서 사용하는 방식으로 각 식은 한번씩만 계산이 된다. 하지만 분할 정복은 매번 식의 결과가 동일할 것이라는 보장이 ..
알고리즘 2022. 1. 19. 14:37
이전 Prev 1 Next 다음