반응형 분할정복2 [백준 10830] 분할정복을 이용한 행렬 제곱 - 파이썬(Python) 행렬 제곱 문제 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. 입력 첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000) 둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다. 출력 첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다. 예제 입력 2 5 1 2 3 4 예제 출력 69 558 337 406 행렬의 거듭제곱 행렬의 제곱은 아래와 같이 똑같은 정사각행렬을 내적시키는 것을 행렬의 제곱이라고 합니다. 그럴려면 벡터/행렬의 내적을 알아야.. 2023. 9. 24. 파이썬(Python) 분할정복 개념과 예제 - 백준 1629 분할정복 알고리즘이란? 분할정복은 여러 알고리즘 한번에 해결할 수 없는 문제를 잘게 쪼개서 해결할 만한 부분문제들로 만든다음에, 그 문제들을 해결하면서 정복해가며 문제를 해결하는 방법으로 보통 재귀함수로 구현합니다. 문제를 잘게 쪼개서 해결한다고 하니까 동적 계획법(DP, 다이나믹 프로그래밍)이랑 똑같은것이 아닌가? 라고 생각이 들것입니다. 확실히 DP의 하향식 접근법이랑 유사한 부분이 많지만 부분문제가 중복되지 않는 부분에서 차이가 있습니다. DP문제, 예를 들어 피보나치 수열 구하기 등은 부분문제가 중복돼서 다른 상위 문제를 푸는데 해결되기 때문에 메모리제이션 기법을 사용합니다. (예를 들어 a10을 구하기 위해서 부분문제를 a9 a8로 나눴을때, a8의 부분문제 a7은 a9를 해결하는데도 쓰이므로 .. 2023. 9. 24. 이전 1 다음
