프로그래밍 일지

problem 문제링크: https://www.acmicpc.net/problem/11726 알고리즘 : 다이나믹 프로그래밍 입력 - n solution 2*n 크기의 직사각형을 2*1 의 타일로 채우는 경우의 수는 n+1 번째의 피보나치수와 같다. dp[] 배열의 1, 2번째에 피보나치수 1, 1 을 할당해둔다. n까지 피보나치 수를 구해 10007로 나눈 나머지 값을 dp의 i 번째에 넣는다. n+1 까지 피보나치 (수 % 10007) 을 한 값을 구하고 dp[n]을 출력한다.[ [code] n = int(input()) dp = [1, 1] for i in range(2, n + 1): dp.append((dp[i - 1] + dp[i - 2]) % 10007) print(dp[n])

Problem 문제링크: www.acmicpc.net/problem/2231 알고리즘 : 브루트포스 입력 - N(1 ≤ N ≤ 1000000) 출력 - 가장 작은 생성자 solution 1부터 N 까지 탐색을 하는 방법도 있지만 N - 9(각 자릿수가 가질수 있는 최댓값) * 자릿수 부터 N 까지만 조사하는 방법이 더욱 빠르다. N = int(input()) start = max(N - (len(str(N)) * 9), 0) result = 0 for i in range(start, N+1): case = i + sum(list(map(int, str(i)))) if case == N: result = i break print(result)

Problem 문제링크: www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 알고리즘 분류: 수학, 조합론, 백트래킹, 재귀 Solution 이 문제는 하나의 집합(N) 속에서 6개의 숫자로 이루어진 모든 조합을 구하는 문제이다. python 의 "itertools" 라이브러리에서 지원하는 *combinations 함수를 사용하면 쉽게 구할 수 있다. Code import itertools while 1: N = list(map(int, input()..