dp3 DP DP의 유래동적 계획법(dynamic programming)이라는 말은 최적화 문제을 연구하는 수학 이론에서 왔고, 전산학 전반에서 일반적으로 사용하는 동적, 혹은 프로그래밍이란 단어와는 아무련 관련이 없습니다. 즉, dynamic programming은 동적 프로그래밍이 아닌, 동적 계획법입니다. 중복되는 부분 문제동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미합니다.이 방식도 처음 주어진 문제들을 더 작은 문제들로 나눈 뒤 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문입니다. 동적 계획법과 분할 정복의 차이가 발생하는 부분은 문제를 나누는 방식입니다.동적 계획법에서는 어떤 부분 문제는 2개 이상의 문제를 푸는 데 사용될 수 있기 때문에, 이 문제의 답을 .. 2025. 4. 25. [개념 정리] DP DP가 뭘까요? 이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다. DP문제를 해결하기 위해 문제를 작은 하위 문제로 나누고, 그 결과를 저장해 동일한 하위 문제를 반복해서 풀지 않는 알고리즘 기법입니다.DP를 사용하기 위해서 충족되어야 하는 조건이 존재합니다. 조건은 다음과 같습니다. DP를 사용하기 위해 어떠한 조건들이 충족되어야 할까요? DP의 조건 1. 참조 투명성을 가져야 합니다.참조 투명성은 입력을 제외한 외적요소에 결과값이 영향을 미치지 않고, 동일한 입력에 대해 동일한 출력을 가지는 것을 의미합니다. 2. Optimal Substructure(최적 부분 구조)하위 문제들을 해결한 결과를 이용해서 전체 문제의 최적 해답을 구성할 수 .. 2025. 3. 11. [프로그래머스] Lv3. 산 모양 타일링 문제 풀이 방법 만든 모양을 정삼각형 또는 마름모 타일로 빈 곳이 없도록 채우는 경우의 수를 10007로 나눈 나머지를 return 하도록 solution 함수를 완성해 주세요. 문제에서 제공해준 아래의 예시를 통해 한단계씩 접근 해보겠습니다. 정삼각형 또는 마름모 타일로 빈 곳이 없도록 채워야 하는 모양은 다음과 같습니다.이 모양을 두 부류로 나누면 아래와 같습니다.삼각형 4개로 이루어진 큰 삼각형 모양과 삼각형 3개로 이루어진 사다리꼴 모양이 있습니다. 각 모양을 채울 수 있는 갯수는 몇개가 존재할까요? 먼저, 삼각형 4개로 이루어진 큰 삼각형 모양을 채우는 방법은 총 4가지 방법이 존재합니다. 다음으로 삼각형 3개로 이뤄어진 사다리꼴 모양을 채우는 방법은 총 3가지 방법이 존재합니다. 먼저, 위.. 2025. 3. 3. 이전 1 다음
