공작소

이항 계수의 공식은 다음과 같다.$$\binom{n}{r} = \frac{n!}{(n-r)! , r!}$$하지만 모듈러 연산이 포함되어 있다. 이전에 배운 모듈러 역원을 이용해 다음과 같이 바꿔서 계산할 수 있다.$$\binom{n}{r}=n! \cdot ((n-r)!)^{-1} \cdot (r!)^{-1}\pmod{M}$$핵심은 다음 세 값을 빠르게 구하는 것이다.$n!$$((n-r)!)^{-1}$$(r!)^{-1}$어떻게 구할 수 있을까?팩토리얼 전처리먼저 모든 팩토리얼 값을 미리 구해 두자.$$fac[i] = i! \pmod{M}$$이제 각 팩토리얼의 모듈러 역원도 필요하다.$$inv[i] = (i!)^{-1} \pmod{M}$$가장 먼저 최댓값에 대한 팩토리얼의 역원을 구해보자.$M$이 소수라면 ..

알고리즘 문제를 풀다 보면 분수 형태의 값을 모듈러 연산 아래에서 계산해야 하는 경우가 자주 등장한다. 하지만 모듈러 연산에서는 일반적인 나눗셈을 그대로 사용할 수 없다.따라서 어떤 수 $b$로 나누는 대신, $b$의 모듈러 역원 $b^{-1}$을 곱하는 방식으로 계산한다.즉,$$\frac{a}{b} \pmod m$$를 직접 계산하는 대신,$$a \times b^{-1} \pmod m$$의 형태로 바꾸어 계산하는 것이다.모듈러 역원이란?어떤 정수 $a$에 대하여,$$a \times x \equiv 1 \pmod m$$을 만족하는 정수 $x$를 $a$의 모듈러 역원이라고 한다.예를 들어, $\pmod 7$에서 $3$의 모듈러 역원은 $5$이다.$$3 \cdot 5 = 15 \equiv 1 \pmod 7$$..

각 항의 역수가 등차수열을 이루는 수열을 조화수열이라고 한다. 조화수열과 연관이 있는 보조정리 Harmonic-Lemma 에 대해 알아보자.자연수 $n$에 대하여,$$a_i = \left\lfloor \frac{n}{i} \right\rfloor$$라는 수열이 있다고 가정해보자.실제로 값을 계산해보면, $1$부터 $n$까지 해당 값은 크게 변하지 않는 성질을 띤다.ex) n = 16floor(n/i) (i : 1..16)16, 8, 5, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1여기서 얻을 수 있는 또 다른 성질이 있는데, 해당 수열에서 서로 다른 수의 종류는 $2\sqrt{n}$개 이하라는 점이다.그 이유는? 해당 수열을 $\sqrt{n}$을 기준으로 나누어 살펴보자.1..

문제 링크 : https://www.acmicpc.net/problem/2263# 2263 : 트리의 순회import syssys.setrecursionlimit(int(1e5))input = sys.stdin.readlinen = int(input().rstrip())inorder = list(map(int, input().rstrip().split()))poorder = list(map(int, input().rstrip().split()))# 중위 순회가 주어지고# 후위 순회가 주어졌을 때# 전위 순회를 구해라.# 1. 요소를 하나씩 잡고, 그 요소가 다른 배열에 등장할 때까지를 구간으로 나누고,# [ 루트 ] - left - [ 루트 ] - left - [ 루트 ] 로 잡는다.# 2. 분할했..

문제 링크 : https://www.acmicpc.net/problem/2630풀이 과정분할 정복으로 풀이했다.합치는 과정에서, (1) 특정 색의 색종이가 4등분한 영역에서 각각 1개이고, (2) 다른 색의 색종이가 4등분한 영역에서 각각 0개라면, 특정 색의 색종이 1장으로만 해당 영역이 구성된 것으로 결과를 반환한다.전체 코드# 2630 : 색종이 만들기import sysinput = sys.stdin.readlinen = int(input().rstrip())arr = [list(map(int, input().rstrip().split())) for _ in range(n)]def func(i, j, size): if size == 1: return [1, 0] if arr[i]..

문제 링크 : https://www.acmicpc.net/problem/1764풀이 과정먼저, 듣도 못한 사람의 명단을 Dictionary 에 저장한다.그 다음, 보도 못한 사람이 Dictionary 에 존재한다면 정답 배열에 넣는다.정답 배열 요소들을 사전순으로 출력한다.전체 코드# 1764 : 듣보잡import sysinput = sys.stdin.readlinen, m = map(int, input().rstrip().split())dic = {}for _ in range(n): string = input().rstrip() dic[string] = 1ans = []for _ in range(m): string = input().rstrip() if dic.get(string..

문제 링크 : https://www.acmicpc.net/problem/1697풀이 과정수빈이의 위치를 정점으로, 3개의 이동하는 방법을 간선으로 인식하여 너비 우선 탐색을 이용해 풀이했다. 전체 코드# 1697 : 숨바꼭질import sysfrom collections import dequeinput = sys.stdin.readlinen, k = map(int, input().rstrip().split())queue = deque()queue.append(n)visited = [False for _ in range(100001)]visited[n] = Truetime = 0done = Falsewhile queue: size = len(queue) for _ in range(size): ..

문제 링크 : https://www.acmicpc.net/problem/1620풀이 과정파이썬의 Dictionary 자료형을 사용해 풀이했다.전체 코드# 1620 : 나는야 포켓몬 마스터 이다솜import sysinput = sys.stdin.readlinen, m = map(int, input().rstrip().split())poke = {}for i in range(1, n+1): string = input().rstrip() poke[string] = str(i) poke[str(i)] = stringfor _ in range(m): string = input().rstrip() print(poke[string])