본문 바로가기

전체보기

 (448)
[440] 조합(combination) 큰 수 계산하기(모듈러) - 파이썬 1. 조합 계산 코드(파이썬)n = 1000000r = 500000MOD = 1000000007facto = [1]*(n+1)inv_facto = [1]*(n+1)for i in range(2, n+1): facto[i] = facto[i-1] * i % MODinv_facto[n] = pow(facto[n], MOD-2, MOD) # 페르마의 소정리for i in range(n-1, -1, -1): inv_facto[i] = inv_facto[i+1] * (i+1) % MODdef nCr(n, r): return facto[n] * inv_facto[r] % MOD * inv_facto[n-r] % MODprint(nCr(5, 3))# 10print(nCr(10, 4))# 210prin..
[439] 모듈러 연산의 나눗셈(확장 유클리드 알고리즘, 페르마 소정리) 1. 모듈러 연산의 기초예전에  모듈러 연산과 관련된 포스팅을 올린 적이 있습니다.모듈러 연산의 분배 법칙을 알아보았지만, 나눗셈의 분배 법칙은 키워드 정도만 안내하고 넘어갔습니다.\((a+b) \text{ mod } c  = \big((a \text{ mod }{c}) + (b \text{ mod }{c})\big) \text{ mod }{c} \)\((a-b) \text{ mod }{ c } = \big((a \text{ mod }{c}) - (b \text{ mod }{c})\big) \text{ mod }{c} \)\((a \times b) \text{ mod }{ c } = \big((a \text{ mod }{c}) \times (b \text{ mod }{c})\big) \text{ mod ..
[438] 팰린드롬 부분 문자열(Manacher's algorithm)(파이썬 코드) 1. Manacher's algorithm우리말로는 마나커, 마나허, 매내처 등으로 불리는 알고리즘입니다.어떤 문자열에서 팰린드롬인 모든 부분 문자열을 \(\mathbf{O(n)}\)만에 찾을 수 있는 알고리즘입니다.코드는 다음과 같습니다.def manacher(S: str): S = "*"+ "".join([c+"*" for c in S]) length = len(S) radius = [0] * length old_center = 0 old_radius = 0 for center in range(length): if old_center+old_radius = 0 and \ center+radius[center]+1 2. 동작 원리먼저 팰린..
[437] 팰린드롬 판별 & 부분 문자열 중 팰린드롬 찾기 1. 팰린드롬?팰린드롬(palindrome)은 우리말로 회문(回文)이라고도 합니다.거꾸로 읽어도 바르게 읽은 것과 같은 문장이나 단어를 뜻합니다.팰린드롬과 관련된 다양한 알고리즘을 알아봅시다.2. 팰린드롬 판별하기(문자열 비교)문자열을 거꾸로 만들어 원래의 문자열과 비교합니다.단순하고 직관적인 방법입니다.파이썬으로 문자열을 거꾸로 만들 때는 slicing의 step을 -1로 사용하면 쉽습니다.def is_palin(S): if S == S[::-1]: return True return Falseprint(is_palin("abcda"))# Falseprint(is_palin("abcba"))# True 조금 더 생각해보면 굳이 문자열 전체를 비교할 필요가 없다는 것을 알 수 있습니..
[436] 피보나치 수열을 구하는 여러 가지 방법(파이썬 코드) 1. 피보나치 수열?다음 문제들을 살펴보고 공통점을 생각해봅시다. 한번에 한 칸 또는 두 칸의 계단을 올라갈 수 있습니다.이 때, n칸을 올라가는 경우의 수는 몇 가지일까요? n개의 육각형이 두 줄로 그림과 같이 배치되어 있습니다.인접한 칸으로 이동이 가능하고, 현재 칸보다 숫자가 더 큰 칸으로 이동할 수 있습니다.1에서 n까지 이동하는 경우의 수는 몇 가지일까요? 첫번째 달에는 어린 암수 토끼 한 쌍이 있습니다.어린 암수 토끼 한 쌍은 한 달이 지나면 다 큰 암수 토끼 한 쌍이 됩니다.다 큰 암수 토끼 한 쌍은 한 달이 지나면 어린 암수 토끼 한 쌍을 낳습니다.n번째 달에는 토끼가 몇 쌍일까요? 문제는 모두 다르지만, 모든 문제의 공통점은 n번째의 수가 (n-1)번째와 (n-2)번째를 더한 수가 된다는..
[435] 에라토스테네스의 체(소수 구하기) (파이썬 코드) 1. 에라토스테네스의 체(소수 구하기) (파이썬 코드)n = 50p = [True] * (n+1)p[0], p[1] = False, Falsefor i in range(2, int(n**0.5)+1): if p[i]: for j in range(i*2, n+1, i): p[j] = Falseprint([i for i in range(n+1) if p[i]])# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]풀어볼 문제: 소수 구하기(https://www.acmicpc.net/problem/1929)2. 소수(Prime Number)1 보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 말합니다.3. 소수 판..
[434] 유클리드 호제법(파이썬 코드) 1. 유클리드 호제법(파이썬 코드)a, b = 490, 350while b: a, b = b, a%bprint(a)# 70풀어볼 문제: 최대공약수와 최소공배수(https://www.acmicpc.net/problem/2609)2. 유클리드 호제법이란?유클리드 호제법은 두 수가 서로(互 서로 호) 0이 될 때까지 덜어내면(除 덜 제) 최대공약수를 찾을 수 있는 알고리즘입니다.기원전 3세기에 고대 그리스 수학자 유클리드가 집필한 에 명시되어 있습니다.이는 명시적으로 기술된 가장 오래된 알고리즘으로도 알려져 있습니다.3. 최대공약수를 구하는 과정 비교490과 350의 최대공약수를 구하는 과정을 코드로 작성해봅시다. 단순하게 1씩 증가시켜가며 두 수를 동시에 나눌 수 있는 수(공약수)의 최대값을 찾습니다...
[433] 8주차 재귀, 백트래킹 1. 재귀프로그래밍에서 재귀란 한 함수가 자신을 호출해 반복적으로 실행되는 것을 뜻합니다.이러한 함수를 재귀 함수라고 합니다. 예를 들어 다음과 같은 함수가 있다고 해봅시다.import timedef func(): print("바트가 호머가 들고 있는 그림을 보고 있어요.") print("호머가 들고 있는 그림 속에는...") time.sleep(1) func()func()# 바트가 호머가 들고 있는 그림을 보고 있어요.# 호머가 들고 있는 그림 속에는...# 바트가 호머가 들고 있는 그림을 보고 있어요.# 호머가 들고 있는 그림 속에는...# 바트가 호머가 들고 있는 그림을 보고 있어요.# 호머가 들고 있는 그림 속에는...# 바트가 호머가 들고 있는 그림을 보고 있어요.# 호머가..

티스토리툴바