동적 계획법

👷‍♀️ 타일 장식물 문제 풀어보기 😃 나의 코드 def solution(N): rad_array = [1,1] for i in range(2,N): rad_array.append(rad_array[-1] + rad_array[-2]) answer = (rad_array[-2] + rad_array[-1]*2)*2 return answer DP(Dynamic Programming, 동적계획법)을 이용해 해결한 문제입니다. DP의 계획에 따라 전체 문제를 작은 부분으로 나누겠습니다. 최종적으로 구할 직사각형의 둘레는 마지막으로 구한 정사각형과 그 전 정사각형의 변의 길이를 통해 구할 수 있기 때문에 변을 구하는 문제로 치환해서 풀겠습니다.가장 작은 정사각형부터 구하면 마지막으로 구한 정사각형의 한 변과 그..

👉 동적계획법 DP(동적 계획법)이 뭔가요? DP는 알고리즘 문제로 자주 나오는 디자인 패러다임 중 하나입니다. Dynamic Programming이라는 말은 고안자인 벨만이 dynamic이라는 단어가 멋있어서(…) 선택한 단어라고 합니다. 따라서 이 방법은 전산학 전반에서의 동적(dynamic) 혹은 프로그래밍(programming)이라는 단어와는 관련이 없습니다. DP의 한글 번역도 동적 프로그래밍보다는 동적 계획법으로 번역됩니다. 👉 특징 부분 문제(overlapping subproblems) 동적 계획법의 접근 방식은 분할 정복과 같습니다. 주어진 문제를 더 작은 문제로 나눈 뒤 이 문제의 답을 계산하고, 이 답을 토대로 원래 문제의 답을 도출해가기 때문입니다. 하지만 분할 정복과 문제를 나누는 ..