728x90 전체 글74 다이나믹 프로그래밍 - 백준 9095 [Python] Problem) https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net Solution) D[N] = D[N-1] + D[N-2] + D[N-3] 의 결과가 된다. 이때, D[0] 을 살펴봐야하는데, D[0]을 정의해야 편하게 코딩할 수 있다. 수를 0개 사용하는 경우는 합이 없는 경우 이므로 아무것도 사용하지 않는 경우, 1가지 이다. 따라서 D[0] = 1로 정의한다. Answer) d = [0]*11 d[0] = 1 for i in range(1, 11): if i-1 >= 0: d[i] += d[i-1] if i-2 >= 0: d[i] += .. 2021. 8. 4. 다이나믹 프로그래밍 - 백준 11726 [Python] Problem) https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net Solution) D[N] = D[N-1] + D[N-2] 이라는 점화식을 세워 해결하면 된다. Answer) n = int(input()) d = [0]*1001 d[1] = 1 d[2] = 2 for i in range(3,n+1): d[i] = d[i-1] + d[i-2] d[i] %= 10007 print(d[n]) 2021. 8. 4. 다이나믹 프로그래밍 - 백준 1463 [Python] 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다. Overlapping Subproblem Optimal Substructure 모든 문제를 풀어야 하고, 모든 문제는 1번만 풀어야 한다는 것을 생각하고 해결해야 한다. 따라서 시간 복잡도는 문제의 개수 * 문제 1개를 푸는 시간이 된다. 구현에는 Top-down (재귀), Bottom-up (반복문) 방식으로 구성되어 있다. 점화식을 구성한 다음 문제를 작게 만들 수 있는 방법을 찾아야 한다. Problem) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmi.. 2021. 8. 3. 브루트 포스 - 백준 15650 [Python] 재귀함수로 풀 수 있는 브루트 포스 순서 : N가지가 있을 때 M를 순서대로 뽑을 경우 O(N!) 선택 : N가지에 대해서 선택/선택하지 않는 것 O(2^N) Problem) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net Solution) 재귀 : 어떤 위치에 올 수 있는 수를 결정해 주는 것 선택 : 그 위치에 있는 것을 선택할지 말지 결정하는 것 Answer) import sys n,m = map(int,input().split()) c.. 2021. 7. 29. 이전 1 ··· 12 13 14 15 16 17 18 19 다음 728x90