반응형 동적 계획법22 백준 #1648 격자판 채우기(동적 계획법) 이번 문제는 플래티넘으로 등급이 매겨진 문제입니다. 격자판의 크기가 주어지면, 2x1 미노로 격자판을 채우는 것입니다. 빈 곳이 있으면 안되고, 꽉 채우는 경우의 수를 계산하는 프로그램입니다. 일견 어려워보일 수 있겠지만, 동적 계획법을 잘 사용하면 쉽게 풀 수 있습니다. 2x1 미노를 세로 또는 가로로 채우는 문제이기 때문에 한줄을 다 채웠을 경우 다음줄에는 말끔하지 않게 되어 있을 수가 있습니다. 예를 들어서 3x6 격자판을 채운다고 해보죠. 첫줄을 채우는 방법은 다음의 두가지입니다. 두번째 줄의 모양에 따라서 안 채워진 곳은 0, 채워진 곳은 1이라고 한다면, 위의 두 패턴은 001과 100이 됩니다. 초기 패턴은 000이라고 할 수 있습니다. 그러면 우리는 점화식으로 다음과 같이 놓을 수 있습니다.. 2022. 9. 21. [C/C++] 백준 #1646 피이보나치 트리(동적 계획법) 피이보나치 트리 문제는 일견 어려워보일 수 있지만, 조성 방법이 정해져 있기 때문에, 그것을 이용해서 푸시면 됩니다. 정답자가 현재 90명정도로 적은 편의 문제입니다. 구현 자체가 어려워서라기보다는 문제 자체가 어려워서인 듯 합니다. N이 주어졌을 때, 루트는 최고층(가장 높은 레이어)에 위치하며 가장 먼 노드까지는 N-1번이면 도착하게 됩니다. 왼쪽 트리는 N-2에 대한 루트이고, 오른쪽 트리는 N-1에 대한 트리입니다. 이것을 이용하면 전체 트리에 대한 노드의 갯수 \(ft_N\)을 구할 수 있습니다. \[ ft_0 = 1, ~ ft_1 = 1 \] \[ ft_n = ft_{n-2} + ft_{n-1} + 1 \] 위의 점화식을 이용하면 우리는 손쉽게 노드의 갯수를 구할 수가 있습니다. 이제 이것을 .. 2022. 9. 18. #1492 합 이번 문제는 Platinum II로 꽤 높게 책정된 문제입니다. 문제 자체는 상당히 쉽습니다. 1부터 n까지 \(n^k\)의 합을 구하라는 문제입니다. 여기서는 파스칼의 삼각형과 연관된 이항계수에 대해서 먼저 알고 있어야 합니다. 이항 계수는 n개에서 r개를 고르는 경우의 수를 나타내는 것으로 \( _nC_r \)로 표현됩니다. 이항 계수를 바로 구할 수도 있겠지만, 저는 프로그램에서는 파스칼의 삼각형을 이용했습니다. n이 최대 51까지밖에 안 되기되문에 크게 문제가 없습니다. 더 크다면 이항 계수를 구하기 위해서는 별도의 방법을 이용해야 합니다. 다음 코드는 파스칼 삼각형을 이용해서 주어진 n에 대해서 이항계수를 구하는 것입니다. 사실 그냥 for 루프를 이용해서 작성할 수 있겠지만, 여기서는 동적 계.. 2022. 8. 21. #1309 동물원(Dynamic Programming) 이번 문제는 Silver I 문제입니다. 이 문제를 풀기 위해서는 적절한 식을 세워야 하는데, 이것이 어느정도 훈련이 되지 않으면, 어렵습니다. 동적 프로그래밍은 점화식이 주어지지 않는 경우가 많습니다. 사실 동적 프로그래밍 뿐만 아니라 분할정복 관련된 문제들이 대부분 그렇습니다. 문제에서 식을 유도하고, 그 식을 수학적으로 정리하는 것이 필요합니다. 문제 난이도는 높지 않지만, 수학적으로 식을 유도하고, 정리하는 것이 필요해서 그 과정을 설명하고자 합니다. 2xN 동물원에 사자를 배치하는데, 가로와 세로로 연달아 배치 못하게 하는 경우의 수는 얼마인가가 문제입니다. 2칸씩 N개가 세로로 배치되는 것이니까, 2칸에 대해서 나올 수 있는 상태는 사자가 하나도 없는 경우, 사자가 왼쪽에 있는 경우, 사자가 .. 2020. 1. 19. 이전 1 2 3 4 다음 728x90
