728x90 DP3 [백준_11049] 다이나믹 프로그래밍(DP), 행렬 곱셈 순서 [백준_11049] 다이나믹 프로그래밍(DP), 행렬 곱셈 순서 행렬 곱셈 순서에 따라 곱셈의 횟수가 달라진다. 행렬이 주어졌을 때 다이나믹 프로그래밍(DP)를 이용하여 곱셈 횟수의 최솟값을 구하는 문제이다. 뭔가 어려운 포인트들이 많아 한 번 정리해두면 좋은 문제이다. https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 문제 풀이 생각 포인트 이 문제에서 중요한 포인트는 3가지 정도 있다. i 번 째 행렬의 행은 i-1 번 째 행렬의.. 2021. 9. 1. [백준_9252] 다이나믹 프로그래밍(DP), LCS 최장 공통 부분 문자열 [백준_9252] 다이나믹 프로그래밍(DP), LCS 최장 공통 부분 문자열 다이나믹 프로그래밍 대표 문제인 LCS 문제를 풀어봤다. LCS(Longest Common Subsequence)는 최장 공통 부분 문자열로 다이나믹 프로그래밍의 대표적인 문제이다. 문자열 출력까지 포함하는 9252번 문제를 풀어보았다. https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 풀이 생각 포인트 다이나믹 프로.. 2021. 8. 27. [WEEK04] 알고리즘_다이나믹 프로그래밍(DP) [WEEK04] 알고리즘_다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 특징 하나의 문제는 단 한 번만 풀도록 하는 알고리즘 메모이제이션(Memoization, 이미 계산한 결과는 배열에 저장함. Memorization이 아님)을 통해 동일 계산시 저장된 값을 단순히 반환하여 시간을 줄임 -> 메모리를 적절히 사용하여 수행 시간을 굉장히 단축시킨다. 일반적으로 탑다운(하향식, 재귀함수 이용), 바텀업(상향식) 두가지 방식으로 구현한다. 보통 바텀업이 전형적인 형태이다. 다이나믹 프로그래밍 사용 조건 최적 부분 구조(Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 통해 큰 문제를 해결 가능한 구조 중복 부분 문제(Overlapping Subproblem.. 2021. 8. 27. 이전 1 다음 728x90
