[Baekjoon,10830] 행렬 제곱
일단 행렬의 곱셈을 모른다면 winner blog : 행렬의 연산(곱셈)을 참고하자.
최근 포스트
[Baekjoon,10942] 팰린드롬?
무식하게 접근 어떻게 부분 문제로 나누어 동적 계획법을 적용할 수 있을 지 많이 고민했다. 처음 접근은 동적 계획법을 적용하지 않고 무식하게 해결하는 것이었다. 주어진 구간 [s,e]에 대해 수열 perm[]이 팰린드롬인지 한 칸 씩 인덱스를 가운데로 모으며 판단하는 것이다. ...
[Baekjoon,1420] 학교 가지마!
이 문제는 각 위치를 정점으로 하고 시작 위치를 소스, 도착 위치를 싱크라고 했을 때 최소 컷을 구하면 되므로 최대 유량 최소 컷 정리 에 따라 최대 유량을 구하면 된다. 그런데 무작정 칸들에 대해 최대유량을 구하면 벽이 칸들을 잇는 길에 놓일 수 있다. 이때 간선을 막는 것...
[Baekjoon,1520] 내리막 길
첫 시작위치에서 시작하여 상하좌우 방향으로 이동가능한 경우 이동하다가 도착지점에 도착할 수 있는 경로의 개수를 찾아야 한다. 중복되어 계산되는 부분이 많으므로 메모이제이션을 적용하여 해결하면 된다. 이때 부분 문제를 아래와 같이 설정하면 된다. getRouteNum(y,x) = ...
[Baekjoon,11049] 행렬 곱셈 순서
모든 구간 [0,N-1]에 대해 최소 비용을 얻기 위해 문제를 잘게 쪼개야 한다. 이를 위한 방법은 각 구간에 대해 재귀적으로 중간을 나누어 쪼개는 것이다. 이는 아래와 같은 부분 문제를 정의하면 쉽게 구현 할 수 있다. dp(lo,hi) = 구간 [lo,hi] 에서 행렬 곱셈...