알고리즘

알고리즘

[백준] 9095번 - 1, 2, 3 더하기 (Python)

설명 1) DP 테이블 정의 d[i] = N 정수 i를 1, 2, 3의 합으로 나타내는 경우의 수 2) 점화식 찾기 (1부터 채워나감) 1. d[1] - 1가지 1 2. d[2] - 2가지 1 + 1 2 3. d[3] - 4가지 1 + 1 + 1 1 + 2 2 + 1 3 4. d[4] - 7가지 3) 점화식 작성 d[i] = d[i-1] + d[i-2] + d[i-3] 코드 1. Top-down 풀이방식 (재귀) Top-down은 Bottom-up보다 성능은 좋지 않지만 메모리와 가독성에 이점이 있습니다. import sys input = sys.stdin.readline nums = [int(input().rstrip()) for _ in range(int(input().rstrip()))] def l..

알고리즘

[백준] 1182번 - 부분수열의 합 (Python)

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 전형적인 백트래킹 문제입니다. 설명 # 백트래킹 이용 - 원소의 개수가 N개인 리스트의 부분집합 개수는 2^N, - 공집합 빼면 2^N-1개의 부분집합에 대해 합이 S와 일치 하는지 확인 1) 함수의 정의 : func(cur, total): - 현재 부분집합의 개수 cur, 현재까지의 전체 합 total 2) base condition if cur == N: #..

상단으로

티스토리툴바