python

1. 다이나믹 프로그래밍 큰 문제를 작은 문제로 나눠서 푸는 방법 작은 문제를 해결하고 해결한 결과를 저장함으로써 큰 문제를 계산할 때 연산 횟수를 줄인다. 이 때 n번째 값에 대응될 수 있는 $a_{i}$의 점화식을 찾아내는것이 다이나믹 프로그래밍의 핵심이다. 2. 2×n 타일링 (백준 11726번) www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제: 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의..

1. 그리디 알고리즘(Greedy Algorithm) 탐욕 알고리즘이라고도 불리며 이후의 결과를 예상하지 않고 그 순간에서 최적의 결과만을 선택하는 알고리즘이다. 상황에 따라 효율이 떨어지는 알고리즘일 수도 있다. 대표적으로 거스름돈 문제가 있다. 2. 거스름돈 문제(백준 5585번) www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사� www.acmicpc.net 문제: 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔,..