I love brew

백준 2133 완전 탐색과 동적계획법 풀이 전략 : 1. 그림 그려서 풀기 2. 완전 탐색으로 풀기 3. 메모이제이션 4. 함수로 풀기 https://www.algorithmist.com/index.php/UVa_10918 1.그림 그려서 풀어보기 가장 간단하면서도 생각해내기가 어려울 수 있습니다. 이 방법으로 시도하면 정확히 경우의 수를 계산해내면 맞고 실수하면 틀리는 방법입니다. 개인적으로 선호하지는 않습니다. 살펴보면 4보다 큰 n에 대해서 3 x n 타일은 특수 케이스를 갖습니다. 특수 케이스란 크기가 3 x 2짜리인 타일을 연속해서 이어붙여서 만들 수 없는 경우를 말합니다. dp라는 배열을 가지고 점화식을 유도해 보면 dp(n) = dp(n - 2) * dp(2) + 2 여기서 2는 각 n마다 자기크기만큼을 가지는 특수케이스 2개를 세어준겁니다. j = n - 2, n - 4, …, 2까지 dp(n) += 2 * dp(j) 특수케이스를 더해줍니다. n = int ( input ( ) ) dp = [ - 1 ] * ( n + 1 ) dp [ 2 ] = 3 def three_tiling ( n ) : if n % 2 != 0 : return 0 if dp [ n ] != - 1 : return dp [ n ] dp [ n ] = three_tiling ( n - 2 ) * dp [ 2 ] + 2 special_cases = 0 for i in range ( 2 , n - 2 , 2 ) : special_cases += 2 * three_tiling ( i ) dp [ n ] += special_cases return dp [ n ] print ( three_tiling ( n ) ) 2. 완전 탐색으로...

TodayILearned : Day 7 모듈러 역원 Modulo Inverse TodayILearned : Day 7 모듈러 역원 Modulo Inverse 1. 지수승 빠르게 연산하기 exponential squaring n의 10000제곱을 구할 때 단순히 10000번 곱하는 방법은 시간복잡도 O(n), 꽤나 느린 편이다. 이를 극복하기 위해서 2^128 = 4^64 = 4 ^ 32 = 16 ^ 16 … = 2^128 * 1 128번 걸리던 연산을 계속해서 두 번 곱해주는 꼴로 바꿔주면 logn번만에 연산이 끝난다. # multiply O ( n ) n = 100000 ans = 1 for _ in range ( n ) : ans *= 2 # vs squaring # O(logn) n = 100000 ans = 2 ** n def fast_exponent ( x , n ) left_term = 1 while ( n > 1 ) : if n % 2 == 0 : x = x ** 2 n = n // 2 else : x = x ** 2 n = ( n - 1 ) // 2 # x^7 = x * ((x ^ 2)^3) # 나머지는 left_term에 곱해준다. left_term *= x result = x * left_term return result y = x ** 10 그렇지만 파이썬 사용자가 체감하지 못하는 이유는 무엇일까, 이미 파이썬의 ** 연산자가 O(logn)을 갖도록 설계되어 있기 때문일 거다. 2. modulo inverse 왜 필요한데? 문제의식 (3 x 10^201 x 70경 / 9000경 * 9000해 ) mod 1000000007 = 는 어떻게 구할수 있을까? 이 값을 실제로 계산해서 풀려고 하면 아무리 컴퓨터...