알고리즘/DP(Dynamic programming, 동적프로그래밍) (18) 썸네일형 리스트형 DP 기본문제인 막대기 자르기(백준에 없는문제) 코드&그림매칭 자식들간 비교를 하여 그 중 최대값을 반환하는 코드 1. 막대기 자르기 문제의 일반화 나누어지는 대상이 1차이로 나누어지고 각각의 값(길이)에 대한 가치 부여되는 문제라면 재귀의 기저사례로부터 올라오면서 차례차례 구할 수 있다. 좀더 일반화 나누어지는 대상이 n차이로 나누어지고 각각의 값(길이)에 대한 가치가 부여되는 문제라면 재귀의 기저사례로부터 올라오면서 차례차례 구할수 있다. Bottom-up 방식으로 해결: 반복문을 사용하여 값을 1부터 시작하여 1일때의 최대 가치, 2일 때의 최대가치를 차근차근 구하여 이전에 얻은 값을 다음에 얻을 값을 계산할때 이용한다. 값이 가장 작을 때 그 값을 구성할수 있는 경우는 오직 한가지 뿐임을 이용한것. 예를들어 숫자 50을 쪼개는 방법은 여러가지다.. 동적프로그래밍의 개념과 기본 개념을 잡아주는 피보나치 문제 동적 프로그래밍은 이름이 조금 이상한데요. 프로그래밍은 컴퓨터 프로그래밍이라는 뜻이 아니라 테이블을 만든다는 뜻입니다. 그리고 전혀 다이나믹하지도 않습니다. 그래서 어떤 서울대 교수님은 동적 프로그래밍 대신 기억하기 프로그래밍이라는 용어를 쓰기도 합니다. 재귀 호출 시, 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 나중에 재사용하는 방법입니다. 메모이제이션이 동적 프로그래밍 중 하나입니다. 알고리즘을 짤 때 분할정복 기법을 사용하는 경우가 많습니다. 큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법인데요. 작은 문제들을 풀다보면 같은 문제들을 반복해서 푸는 경우가 생깁니다. 그 문제들을 매번 재계산하지 않고 값을 저장해두었다가 재사.. 이전 1 2 3 다음
