jenlog

🚩 동적프로그래밍(DP) thinking 1. 규칙을 찾아보려 했으나 실패 -> 규칙 없음 ! 2. DP 접근 인풋숫자의 크기만큼 배열을 만들고, 계산횟수를 해당 인덱스에 입력 & 비교하면서 최소 연산값을 구하는 것이다. 앞에서 부터 계산을 해가면서 카운팅을 늘려나가는 것이 핵심이다 ! ◾ 점화식 : dp(N) = min ( dp(N//3)+1, dp(N//2)+1 , dp(N-1)+1 ) ◾ 시간복잡도 : {배열의 크기 x O(1)} => O(N) 코드 N = int(input()) dp = [0 for _ in range(N+1)] # 인덱스가 N이 되도록 N+1 크기의 배열을 만듦 for i in range(2, N+1): dp[i] = dp[i-1] + 1 # dp(N-1)+1 계산먼저 해주고 i..

🚩 동적프로그래밍(DP) thinking 1. 시간초과 난 코드 피보나치 수열 코드와 동일하게 짜되, n == 0 or 1 인 경우 0과 1의 호출횟수를 카운트하도록 함수를 구성했다. output은 맞게 나왔지만 시간초과 뜸 2. success 😀 0호출횟수와 1호출횟수를 리스트로 만들어 피보나치 수열처럼 n-1, n-2의 호출횟수를 더하는 방식으로 코드를 짬. n = 8 인 경우, cnt_0 = [1, 0, 1, 1, 2, 3, 5, 8], cnt_1 = [0, 1, 1, 2, 3, 5, 8, 13]가 되어 n번째 원소를 출력하면 된다 코드 (pass) T = int(input()) for tc in range(T): N = int(input()) cnt_0 = [1, 0] # 0 호출횟수 기록하는 리..