다이나믹 프로그래밍

프로그래밍/백준
백준 11727: 2xn 타일링(2) 해설- python
✏️ 문제 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net ✏️ 풀이 2xn 타일링 문제에서 2x2타일이 추가된 형태의 문제로 점화식만 살짝 수정해주면 된다. 2xn 타일링 문제는 아래에서 다시 풀어보자 백준 11726: 2xn 타일링 해설- python ✏️ 문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acm duckracoon.tistory.com 이전의 문제에서는 점화식이 c..
→2022.01.23
프로그래밍/백준
백준 1463: 1로 만들기 해설- python
✏️ 문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net ✏️ 풀이 해당 풀이는 주로 동적계획법 (Dynamic Programming) 을 이용하는 것 같다. 동적계획법에 대한 설명은 아래글을 참고하자. [Python & Algorithm] Dynamic Programming(동적프로그래밍) ✏️ Dynamic Programming 큰 문제를 작은 문제로 나누어 푸는 문제를 이야기한다. 이름에 의미는 없다. 그냥 말이 멋있어서 이렇게 지었다고 한다. 1) 분할정복과의 차이 '작은 문제가 중복이 일어나 duckracoon.tistory.com 어떻게 시작해야할지 잘 모르겠으니 나는 임의의 X를 가지고 수가 어떻게 변하는지를..
→2022.01.23
프로그래밍/자료구조 & 알고리즘
[Python & Algorithm] Dynamic Programming(동적프로그래밍)
✏️ Dynamic Programming 큰 문제를 작은 문제로 나누어 푸는 문제를 이야기한다. 이름에 의미는 없다. 그냥 말이 멋있어서 이렇게 지었다고 한다. 1) 분할정복과의 차이 '작은 문제가 중복이 일어나는지 아닌지' 에 차이가 있다. 분할정복은 큰 문제를 해결하기 어려워서 단지 작은 문제로 나누어서 푸는 방법이다. 특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점이다. 하지만 동적프로그래밍은 작은 부분문제들이 반복되는 것을 이용해 문제를 풀어낸다. 2) 다이나믹 프로그래밍의 방법 모든 작은 문제들은 한번만 풀어낸다. 따라서 정답을 구한 작은 문제를 어딘가에 메모해둔다. 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다. 3) 다이나믹..
→2022.01.22

• 이전
• 1
• 다음