안녕

문제

백준 11444 피보나치 수 6

풀이

우선 피보나치 문제를 행렬 곱으로 계산해야 한다. 즉, 이전 피보나치수를 나타내는 행렬에서 다음 피보나치 수를 나타내는 행렬을 만들어야 한다.

나는 다음과 같은 방법을 생각했다.

$\begin{bmatrix}f_n & f_{n+1}\\ 0 & 0 \end{bmatrix} \times SOME \ MATRIX=\begin{bmatrix}f_{n+1} & f_{n+2}\\ 0 & 0 \end{bmatrix}$

이는 다시 쓰면 아래와 같다.

$\begin{bmatrix}f_n & f_{n+1}\\ 0 & 0 \end{bmatrix} \times SOME \ MATRIX=\begin{bmatrix}f_{n+1} & f_{n}+f_{n+1}\\ 0 & 0 \end{bmatrix}$

이를 만족하는 SOME MATRIX를 구해보면 다음을 찾을 수 있다.

$\begin{bmatrix}f_n & f_{n+1}\\ 0 & 0 \end{bmatrix} \times \begin{bmatrix}0 & 1\\ 1 & 1 \end{bmatrix} =\begin{bmatrix}f_{n+1} & f_{n}+f_{n+1}\\ 0 & 0 \end{bmatrix}$

( 한번 계산해 보면 어렵지 않게 찾을 수 있다 ! )

그러면 N번째 피보나치 수는

$\begin{bmatrix}1 & 1\\ 0 & 0 \end{bmatrix} \times \begin{bmatrix}0 & 1\\ 1 & 1 \end{bmatrix} ^{N-1}=\begin{bmatrix}f_{N} & f_{N+1}\\ 0 & 0 \end{bmatrix}$

이므로 1번째 행의 1번째 열 값으로 알 수 있다. ( $f_1 = 1,\ f_2=1$ )

그러면 위의 식을 어떻게 구현해야 할까? 행렬 곱하기를 구현해서 N-1 번의 행렬 곱하기를 진행 할 수 도 있지만, 그렇게 되면 행렬 곱 연산에서 너무 많은 시간을 할애하여 시간초과가 날 것이다. 그래서 분할 정복을 이용한 거듭제곱이라 불리는 알고리즘을 사용할 것이다.

분할 정복을 이용하면 $O(N)$ 만큼 걸리던 거듭제곱을 $O(logN)$만큼으로 줄일 수 있는데 방법은 다음과 같다.

$C^n=\begin{cases} C^{n/2}\cdot C^{n/2} \ \ \ \ n\mathrm{\ is\ even} \\ C^{n/2}\cdot C^{n/2} \cdot C\ \ \ \ n\mathrm{\ is\ odd}\end {cases}$

$C^{n/2}$의 연산 결과를 알면 반복하지 않고 그 결과를 한 번 더 곱해주기만 하면 되므로, 연산량이 엄청 줄어들게 된다.

이 알고리즘을 사용해서 $\begin{bmatrix}0 & 1\\ 1 & 1 \end{bmatrix} ^{N-1}$을 구하고 후에 $\begin {bmatrix} 1 &1 \\ 0 & 0 \end{bmatrix}$와 곱하여 계산하였다. 행렬곱의 결합법칙 (combination law) 에 의해서 뒷 행렬의 거듭 제곱을 먼저 연산하여도 문제 없다.

전체 코드

## 행렬 곱 구현
def matrix_multiple(A, B):
    R00 = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % 1000000007
    R01 = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % 1000000007
    R10 = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % 1000000007
    R11 = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % 1000000007

    result_matrix = [[R00, R01],
                     [R10, R11]]
    return result_matrix

## 분할 정복을 이용한 거듭제곱
def n_square(n, matrix):
    if n == 1:
        return matrix

    sqrt_matrix = n_square( n//2, matrix)

    result_matrix = matrix_multiple(sqrt_matrix, sqrt_matrix)
    if n % 2 == 1: ## n이 홀수인 경우
        result_matrix = matrix_multiple(result_matrix, matrix)

    return result_matrix

if __name__ == "__main__":
    N = int(input())

    initial_matrix = [[1, 1],
                      [0, 0]]

    factor_matrix = [[0, 1],
                     [1, 1]]

    factor_matrix_n = n_square(N, factor_matrix)
    print(factor_matrix_n)
    result = matrix_multiple(initial_matrix, factor_matrix_n)
    print(result[0][0])

문제

백준 4386 별자리 만들기

풀이

모든 별이 이어져 있는 최단 경로를 구하는 문제이므로 Prim 알고리즘을 사용하면 간단하게 풀 수가 있다. 단, 별과 별 사이의 거리를 구해서 직접 그래프를 구해줘야 하는 차이점이 있다.

전체 코드

from sys import maxsize
import heapq
import sys

def get_input():
    input = sys.stdin.readline
    N = int(input())
    star_list = [tuple(map(float, input().split())) for _ in range(N)]
    return N, star_list

def dist(A, B):
    a1, a2 = A
    b1, b2 = B
    return ( (a1 - b1) ** 2 + (a2 - b2) ** 2 ) ** (1/2)

def make_adjency_matrix(N, star_list):
    adjency_matrix = [[0] * N for _ in range(N)]

    for ii in range(N):
        for jj in range(ii+1, N):
            cost = dist(star_list[ii], star_list[jj])
            adjency_matrix[ii][jj] = cost
            adjency_matrix[jj][ii] = cost
    return adjency_matrix

def prim():
    visited = [False] * N
    heap = []
    total_cost = 0

    ## 0으로 시작하자 ~
    visited[0] = True
    for ii in range(1, N):
        heapq.heappush( heap, (adjency_matrix[0][ii], ii) )

    while(heap):
        cost, star = heapq.heappop(heap)
        if visited[star]:
            continue
        visited[star] = True
        total_cost += cost
        for ii in range(1, N):
            if visited[ii]:
                continue
            heapq.heappush( heap, (adjency_matrix[star][ii], ii))
    print(total_cost)

## graph만들고 prim하면 되지 않을까
if __name__ == "__main__":
    N, star_list = get_input()

    adjency_matrix = make_adjency_matrix(N, star_list)

    prim()

문제

백준 2342 Dance Dance Revolution

풀이

나는 처음에 문제 이해가 막막해서 되게 복잡한 방법으로 풀었지만, DP구조만 잘 이해하면은 되게 간단하게 풀 수 있다.

우선 기본 아이디어부터 생각해보자. 지시 사항이 1~4중의 숫자로 주어졌을 때 두 발 중 한 발은 지시한 숫자를 밟고 있어야 한다. 다른 한 쪽 발은? 같은 칸에만 있지 않는다면 어디든 둘 수 있다. 예를들어, 지시 사항이 1이라면 발의 위치는 다음 중 하나가 될 수 있다. { (1,0), (1,2), (1,3), (1,4) }

그러면 이제 dp를 어떻게 짜야할 지 어렴풋이 감이 올 것이다. 이 이전 상태에서의 각각 최솟값을 알고 있을 때, 다음 상태로의 최솟값을 찾으면 되는 것이다. 그러면 이 최솟값은 어떻게 찾아야 할까?

이전 상태에서 다음 상태로 간다는 것은 발 하나를 옮겨( 혹은, 유지하여) 지시 사항에 맞는 발의 위치를 가진다는 것이다. 그러면 이전 지시사항의 발을 이번 지시사항으로 옮기거나, 이전 지시사항의 발이 아닌것을 이번 지시사항으로 옮기는 경우만 생각하면 된다.

예를 들어 이전 지시사항이 1이었고 이번 지시사항이 2일 때, 1에 있는 발을 2로 옮기거나, 1에 있지 않은 발을 2로 옮기는 경우만 있다.

dp를 dp[지시사항][지시사항 아닌 쪽 위치] 로 만들어 진행하였다.

아래의 코드가 핵심이라 볼 수 있다.

for n, now_instruction in enumerate(instruction_list[1:-1], 1):
    ## prev_instruction 발을 now_instruction으로 옮기기
    for ii in range(5):
        dp[n][ii] = min(dp[n][ii],dp[n-1][ii] + change_cost(prev_instruction, now_instruction))

    ## prev_instruction이 아닌 발을 now_instruction으로 옮기기
    for ii in range(5):
        dp[n][prev_instruction] = min(dp[n][prev_instruction], dp[n-1][ii] + change_cost(ii, now_instruction))

전체코드

from sys import maxsize

def get_input():
    return list(map(int, input().split()))

def change_cost(A,B):
    offset = abs(A -B)
    ## 0에서 움직이는 경우
    if A == 0:
        return 2
    ## 안 움직이는 경우
    elif offset == 0:
        return 1
    ## 반대편으로 가는 경우
    elif offset == 2:
        return 4
    ## 옆으로 움직이는 경우
    else:
        return 3

# 지시사항이 주어졌을 때 가질수 있는 state는 3개
        # ex)   지시사항 = 1
        #       가질 수 있는 state = {(1,0), (1, 2), (1, 3), (1, 4)}
        # 이걸로 dp짜면 되겠다.
if __name__ == "__main__":
    # 입력 받기
    instruction_list = get_input()
    N = len(instruction_list) - 1
    dp = [[maxsize] * 5 for _ in range(N)]

    if not N: ## 지시사항이 없는 경우
        print(0)
    else:
        ## 첫번째 거 처리
        prev_instruction = instruction_list[0]
        dp[0][0] = 2
        #print(prev_instruction, dp[0])
        for n, now_instruction in enumerate(instruction_list[1:-1], 1):
            ## prev_instruction 발을 now_instruction으로 옮기기
            for ii in range(5):
                dp[n][ii] = min(dp[n][ii],dp[n-1][ii] + change_cost(prev_instruction, now_instruction))

            ## prev_instruction이 아닌 발을 now_instruction으로 옮기기
            for ii in range(5):
                dp[n][prev_instruction] = min(dp[n][prev_instruction], dp[n-1][ii] + change_cost(ii, now_instruction))
            #print(now_instruction, dp[n])
            prev_instruction = now_instruction
        print(min(dp[N-1]))

처음으로 백준 풀이 적은거라서 이해가 잘 안될 수 있을거 같다...