일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- 코딩테스트
- 못그리지만
- Flutter
- BAEKJOON
- 이진탐색
- DP
- 자료구조
- programmers
- BFS
- 삼성sw역테
- 구현
- 프로그래머스
- JS
- c#
- 동적 프로그래밍
- 백준
- DART
- sort
- JavaScript
- 카카오
- 그래프 탐색
- 알고리즘
- 파이썬
- 스터디
- 문자열 파싱
- 쓰셨잖아
- Java
- 자바스크립트
- 코드트리
- Algorithm
- Today
- Total
목록DP (5)
Algo 쓰자
▶ 문제 : https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net => 기존 백준 문제를 Javascript를 이용해 풀이하였었는데, 입출력관련해서 맞게 풀어도 틀리다 나오는 경우가 있어서 백준의 경우는 python을 사용해서 풀이하기로 결정하였다. ▶ 코드 : # https://www.acmicpc.net/problem/9095 # 백준 1, 2, 3 더하기 T = int(input()) testCase = [] for t in range(T): testCase.append(int(input())) maxNum = max(testCase) dp ..
▶ 문제 : https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net ▶ 코드 : const input = require('fs').readFileSync('BaekJoon/testcase.txt').toString().trim().split('\n'); let n = Number(input[0]); const dp = Array(50001); dp[0] = 0; dp[1] = 1; for(let i = 1; i < ..
▶ 문제 : http://acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net ▶ 코드 : let input = require('fs').readFileSync(`BaekJoon/testcase.txt`).toString().split('\n'); const [N, ...temp] = input; const stairs = temp.map(n => Number(n)); const dp = Array(N).fill(0); dp[0] = stairs[0]; dp[1] = Math.max..
▶ 문제 : 더보기 https://www.acmicpc.net/problem/1463 ▶ 코드 : num = int(input()) data = {1:0} i = 2 while True: if i == num+1: break data[i] = data[i-1] + 1 if i % 3 == 0: data[i] = min(data[i], data[i//3] + 1) if i % 2 == 0: data[i] = min(data[i], data[i//2] + 1) i += 1 print(data[num]) ▶ 문제 풀이 : 1. DP 방식을 사용해서 풀이하는 문제이다. 2. 초기 값 1을 제외한 이후 숫자(2) 부터 반복을 진행한다. 3. 해당 숫자에서 1을 뺀 경우(이 경우는 이전 결과값에 1을 더함) 3으로..
▶ 문제 더보기 https://www.acmicpc.net/problem/1003 import sys n = int(sys.stdin.readline().rstrip()) data = {i : 0 for i in range(41)} # 숫자의 최대값이 40 result = [[0, 0] for i in range(41)] result[0][0] = 1 result[1][1] = 1 def fibo(n): if n == 0: return 0 elif n == 1: return 1 elif data[n] > 0: return data[n] else: data[n] = fibo(n-1) + fibo(n-2) result[n][0], result[n][1] = result[n-1][0] + result[n-2]..