dp

👷‍♀️ 타일 장식물 문제 풀어보기 😃 나의 코드 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) 동적 계획법의 접근 방식은 분할 정복과 같습니다. 주어진 문제를 더 작은 문제로 나눈 뒤 이 문제의 답을 계산하고, 이 답을 토대로 원래 문제의 답을 도출해가기 때문입니다. 하지만 분할 정복과 문제를 나누는 ..

👨‍🏫 정수 삼각형 문제 풀어보기 😃 나의 코드 def solution(tri): m_lst = [] for row in tri: lst = [] if len(m_lst) == 0: lst.append(row[0]); else: for idx, num in enumerate(row): if idx == 0: lst.append(m_lst[-1][idx] + num) elif idx == len(row)-1: lst.append(m_lst[-1][-1] + num) else: lst.append(max(m_lst[-1][idx-1],m_lst[-1][idx]) + num) m_lst.append(lst) return max(m_lst[-1]) DP(Dynamic Programming, 동적계획법)을 이용해..

N으로 표현 문제 설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. 제한사항 N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다. 최솟값이 8보다 크면 -1을 return 합니다. 😃 나의 풀이 dic = {0:1..