바닥공사 문제 2 X N의 바닥을 1 x 2, 2 x 1, 2 x 2 로 채운다고 할 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 구하시오. 바닥을 채우는 방법의 수를 796796으로 나눈 나머지를 출력할 것 제한사항 1

1로 만들기 문제 정수 x가 주어질 때 정수 x에 사용할 수 있는 연산은 다음과 같이 4가지이다. x가 5로 나누어떨어지면, 5로 나눈다. x가 3으로 나누어떨어지면, 3으로 나눈다. x가 2로 나누어떨어지면, 2로 나눈다 x에서 1을 뺀다. 정수 x가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 제한사항 1 1 Min(2, 1) = 1 4를 1로 만들 수 있는 횟수 최솟값? 4 - 1 = 3 => 3을 1로 만들 수 있는 횟수 + 1 = 2 4 / 2 = 2 => 2를 1로 만들 수 있는 횟수 + 1 = 2 Min(2, 2) = 2 일반화 해보면 dp[i] = min (dp[i - 1] + 1 , (dp[i //2] + 1 or dp[i ..

동적계획법 (Dynamic Programming) 동적 계획법이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 분할 정복과 다른 점은 문제들이 서로 영향을 미치고 있다는 점이다. 동적 계획법의 경우 한 번 해결한 문제를 다시금 해결한다는 점이 특징이다. 그렇기 때문에 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 가져다 쓰는 것이다. 동적 계획법은 다음 조건을 만족할 때 사용할 수 있다. 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 동적 계획법을 구현하는 방식에는 2가지가 있는데 탑 다운 방식과 바텀 업 방식이다. 탑다운 방식은 재귀 함수를 이용한다. 큰 문제를 해결하기 위해 작은 ..