알고리즘

피사노 주기 [백준 9471] - python

import sys input = sys.stdin.readline def solution(num): answer = 1 mod1, mod2 = 1, 2 while True: if mod1 % num == 1 and mod2 % num == 1: break answer += 1 mod1, mod2 = mod2, (mod1 + mod2) % num return answer def BOJ9471(): P = int(input()) for _ in range(P): N, M = map(int, input().split()) answer = solution(M) print(f"{N} {answer}") BOJ9471() 접근 방법: 1. 여러가지 성질이 문제에 주어져있어 이것들도 고려해야 하나 생각이 들었던 문..

피보나치 수 3 [백준 2749] - python

import sys input = sys.stdin.readline target_num = 1e6 def find_routine() : routine = 1 m1, m2 = 1, 2 while True : if m1 == 1 and m2 == 1 : break m1, m2 = m2, (m1 + m2) % target_num routine += 1 return routine def BOJ2749(): routine_length = find_routine() n = int(input()) fibonacci = [0, 1, 1] + [0] * int(routine_length) for i in range(3, routine_length): fibonacci[i] = int((fibonacci[i-2] % ta..

앱 [백준 7579] - python

import sys input = sys.stdin.readline def BOJ7579(): N, M = map(int, input().split()) bytes = list(map(int, input().split())) costs = list(map(int, input().split())) total = sum(costs) result = total dp = [[0 for _ in range(total+1)] for _ in range(N + 1)] for i in range(1, N+1) : byte, cost = bytes[i-1], costs[i-1] for j in range(total + 1) : if j < cost : dp[i][j] = dp[i-1][j] # 코스트가 현재 앱의 끄는 ..

곱셈 [백준 1629] - python

import sys input = sys.stdin.readline def BOJ1629() : def pow(a, b, c) : if b == 1 : return a % c elif b % 2 == 0 : return (pow(a, b // 2, c) ** 2) % c else : return (pow(a, b // 2, c) ** 2) * a % c A, B, C = map(int, input().split()) print(pow(A, B, C)) BOJ1629() 접근 방법: 1. 쉽게 보았는데 크게 데였다. A, B, C의 범위가 매우 크고 시간 제한은 0.5초, 메모리 제한도 128MB여서 A의 B제곱을 구한 후 모듈러 연산을 통해 답을 구할순 없었다. 2. a^4 = a^2 ** 2 a^5 =..

행렬 제곱 [백준 10830] - python

import sys input = sys.stdin.readline def BOJ10830() : N, B = map(int, input().split()) def matrix_mul(a, b) : result = [[0 for _ in range(N)] for _ in range(N)] for i in range(N): for j in range(N): for k in range(N): result[i][j] += (a[i][k] * b[k][j]) % 1000 for i in range(N) : for j in range(N) : result[i][j] %= 1000 return result def divide(a, count) : if count == 1 : return a tmp = divide(..

이항계수 [백준 11401] - python

import sys input = sys.stdin.readline prime = 1_000_000_007 def BOJ11401(): def factorial(n): ans = 1 for i in range(1, n+1): ans = (ans * i) % prime return ans def pow(a, b): if b == 1: return a elif b % 2 == 0: return (pow(a, b//2) ** 2) % prime else: return (pow(a, b//2) ** 2) * a % prime N, K = map(int, input().split()) A = factorial(N) B = (factorial(K) * factorial(N-K)) print((A % prime * ..

신나는 함수 실행 [백준 9184] - python

import sys input = sys.stdin.readline def BOJ9184() : dic = {} def w(a,b,c) : if (a,b,c) in dic : return dic[(a,b,c)] if a 20 : return w(20, 20, 20) if a < b and b < c : dic[(a,b,c)] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) return dic[(a,b,c)] else : dic[(a, b, c)] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) return dic[(a, b, c)] while True : a,b,c = map(int, input(..

피보나치 함수 [백준 1003] - python

import sys input = sys.stdin.readline def BOJ1003() : T = int(input()) dp = [0] * 41 dp[0] = [1, 0] dp[1] = [0, 1] dp[2] = [1, 1] for i in range(3, 41) : temp = [] for a, b in zip(dp[i-1], dp[i-2]) : temp.append(a+b) dp[i] = temp for i in range(T) : print(*dp[int(input())]) BOJ1003() 이 문제에 대해 포스팅을 하는 것은 zip과 array spread에 대해서 서술하고 싶어서 였다. a = [1, 2, 3] b = [100, 200, 300] c = [4, 5, 6] for i, j,..

치킨 배달 [백준 15686] - python

import sys from itertools import combinations def BOJ15686() : N, M = map(int, sys.stdin.readline().split()) graph = [] for _ in range(N) : graph.append(list(map(int, sys.stdin.readline().split()))) chiken_store_list = [] house_list = [] for x in range(N) : for y in range(N) : if graph[x][y] == 1 : house_list.append([x+1, y+1]) elif graph[x][y] == 2 : chiken_store_list.append([x+1, y+1]) chiken_..

이분 그래프 [백준 1707] - python

from collections import deque import sys def BOJ1797() : def bfs(start) : bi[start] = 1 queue = deque() queue.append(start) while queue : curr = queue.popleft() for i in graph[curr] : if bi[i] == 0 : bi[i] = -bi[curr] queue.append(i) else : if bi[i] == bi[curr] : return False return True k = int(sys.stdin.readline()) for _ in range(k) : global graph global flag global bi global queue flag = "YES..