본문 바로가기

🧩 Algorithm/다이나믹 프로그래밍2

다이나믹 프로그래밍 (Dynamic Programming) Goal 1. 다이나믹 프로그래밍 이해하기 2. Top-down과 bottom-up 방법 알아보기 다이나믹 프로그래밍(Dynamic Programing)이란? 다이나믹 프로그래밍이란 어떤 문제가 주어졌을 때 그 문제를 더 작은 단위의 문제들로 쪼개서 작은 문제부터 풀어나가는 방법이다. 더 작은 단위로 쪼개진 문제를 풀어서 얻은 결과로 원래 문제의 해답에 점점 더 가까워지는 방식이다. 이 알고리즘의 헛점은 문제를 작은 단위로 쪼갤 수 있을 때만 사용할 수 있다는 것이다. 다이나믹 프로그래밍 알고리즘을 사용하는 가장 흔한 예제가 바로 피보나치 숫자이다. 피보나치 숫자는 그 전에 오는 두 숫자를 계속해서 더해 나가기 때문에 n번째 숫자를 알아내기 위해선 처음부터 계속 더해오면 된다. 두 숫자씩 더하는 작은 단.. 2023. 6. 13.

[백준] 1463번: 1로 만들기 Hint 1. n에서 2나 3을 나누거나 1을 뺄 생각하지 말고 1부터 고려하는 코드로 짜야함 2. 1부터 n까지의 숫자를 각각 만들기 위해선 몇번의 연산 횟수가 필요한지 생각해봐야 함 3. Memoization 기법 활용 백준 1463번: 1로 만들기 (풀어보기) n = int(input()) ans = [0] * (n+1) # ans[i] = i가 1이 되기 위한 연산 횟수 for i in range(2, n+1): ans[i] = ans[i-1] + 1 # 디폴트로는 그 전 숫자에서 +1 한거니까 횟수도 그 전 숫자의 횟수에 +1 한것임 if i % 3 == 0: ans[i] = min(ans[i], ans[i // 3] + 1) # 디폴트와 x3 하기 전의 숫자의 횟수에서 +1 한거 중에 더 작은.. 2023. 2. 17.

이전 1 다음

티스토리툴바