본문 바로가기

행렬3

파이썬 행렬 곱셈, 거듭제곱 구하기 파이썬 행렬 알고리즘 문제를 풀 때 시간 복잡도를 줄이기 위해 행렬의 거듭제곱을 사용하는 경우가 있습니다. 대표적으로 피보나치 수열의 가장 빠른 시간 복잡도가 O(LogN)이 행렬로 구현할 수 있습니다. 피보나치와 행렬에 대한 내용은 자세한 내용은 아래 링크를 참조해주세요. [CS/알고리즘] - 피보나치 파이썬으로 구하는 3가지 알고리즘 피보나치 파이썬으로 구하는 3가지 알고리즘 피보나치 파이썬 3가지 알고리즘 피보나치 수열은 아래의 수식은 만족하는 수열입니다. 바로 이전 숫자와 그 전 숫자의 합을 연속해서 구하는 수열이고 아래와 같이 진행됩니다. 이번 글에서는 myjamong.tistory.com 이렇게 가끔씩 행렬의 곱셈을 사용하는데... 이게 자주 사용하지 않는 3개의 중첩된 for문을 사용하다보니.. 2021. 10. 21.

백준 1904 파이썬 - 01타일 - 동적 계획법, 행렬 백준 1904 파이썬 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 해당 문제는... "00" 타일과 "1" 타일로 만들 수 있는 이진수의 가짓수를 찾는 문제입니다. 이 문제도 결국 1타일과 00타일을 이전의 타입에 붙치는 문제이므로 메모이제이션을 이용한 동적계획법으로 풀 수 있다. 그런데... 직접 손으로 숫자의 패턴을 계산해보니 피보나치 수열과 완젼 동일한 숫자의 패턴을 갖고 있었습니다. 그래서 이 문제는 행렬 멱법을 사용해서 해결할 수 있었습.. 2021. 10. 8.

피보나치 파이썬으로 구하는 3가지 알고리즘 피보나치 파이썬 3가지 알고리즘 피보나치 수열은 아래의 수식은 만족하는 수열입니다. 바로 이전 숫자와 그 전 숫자의 합을 연속해서 구하는 수열이고 아래와 같이 진행됩니다. 이번 글에서는 시간 복잡도에 따른 피보나치 수열을 구하는 대표적인 3가지 알고리즘에 대해서 알아보도록 하겠습니다. 재귀함수 이용 - 시간복잡도 O(n^2) 동적 계획법 이용 - 시간복잡도 O(n) 행렬 멱법 이용 - 시간복잡도 O(log n) 재귀함수 이용 첫번 째 방법은 재귀함수를 이용하는 방법입니다. def fibo(n): if n in (1,2): return 1 return fibo(n-1) + fibo(n-2) print(fibo(8)) 가장 간단한 방법이지만... 재귀로 두개의 분기가 계속해서 생기기 때문에 시간복잡도가 O(.. 2021. 10. 8.

이전 1 다음

티스토리툴바