분할정복2 [Algorithm] Dynamic Programming(동적 계획법, 다이나믹 프로그래밍) Dynamic Programming(동적 계획법, 다이나믹 프로그래밍) 응용 수학자 리차드 벨만(Richard Bellman)이 1953년에 고안한 알고리즘 큰 문제를 간단한 여러 개의(작은) 문제(Overlapping Subproblem)로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘 즉, 이미 해결한 (작은) 문제의 결과는 저장해 두었다가 다시 계산하지 않도록 하는 알고리즘 부분 하위 문제(Overlapping Subproblem; 중복 부분 문제) 동일한 작은 문제를 반복적으로 해결 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결 Algorithm 특징 대표적인 문제 다이.. 2021. 12. 19. [백준(Baekjoon)] 2630 색종이 만들기 문제 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의.. 2021. 10. 28. 이전 1 다음
