지나가던 개발자

저번에 백준의 11723번 문제를 이 비트마스킹을 사용해서 풀었었습니다. https://developer-next-to-you.tistory.com/295 [Python] 백준 11723번(집합) 문제 풀이 import sys S = 0 for i in range(int(sys.stdin.readline())): command = sys.stdin.readline().split() if len(command) == 1: if command[0] == "all": S = (1 developer-next-to-you.tistory.com 비트마스킹이란 기본적으로 정말 간단한 개념입니다. 컴퓨터는 이진수로 생각하죠? 이진수는 0과 1로 이루어져 있습니다. 이 0과 1을 각각 False와 True로 생각하여 연..

분할 정복(Divide and Conquer)은 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트나 병합정렬이 있다. 나무위키에서 인용했다. 거듭제곱 또한 분할 정복 알고리즘을 활용하여 빠르게 계산이 가능하다. 임의의 수 C에 대하여 Cⁿ을 구할 때는 C를 n번 곱하므로 시간 복잡도가 O(n)인 반면, 분할 정복을 활용하여 계산하면 O(logn)의 시간 복잡도로 계산이 가능하다. 훨씬 빨라지는 것이다. 분할 정복을 활용하여 거듭제곱을 계산하는 것은 다음과 같은 아이디어로부터 출발한다. $$ C^{n} = \begin{cases} ..

오일러 피 함수(Euler's phi function, ϕ)은 임의의 양의 정수 n과 서로소인 자연수의 개수를 구하는 함수이다. 1. n이 소수일 때 n이 소수일 때 ϕ(n)은 항상 (n-1)의 값을 가진다. 왜냐하면 소수는 모든 자연수와 서로소이기 때문이다. $$ n = ab (a, b \in N, a 1 $$ $$ \phi (n) = n-1 $$ 2. n이 소수의 거듭제곱일 때 n이 소수 p의 거듭제곱일 때에, ϕ(n)은 다음과 같이 계산된다. $$ n = p^{k} $$ $$ p = ab(a, b \in N, a 1 $$ $$ \phi (n) = p^{k-1} (p-1) $$ 3. m과 n이 서로소일 때 m과 n이 서로소일 때, mn과의 서로소의 개수는 m과의 서로소의 개수와 n과의 서로소의 개수의..

PS를 할 때 빠른 곱셈과 빠른 거듭제곱은 정말로 중요하다. PS를 할 때 뿐만 아니라 그냥 코딩을 할 때에도 중요하다. 카라추바 알고리즘은 빠르게 곱셈을 할 때에 사용되는 알고리즘으로, 보통의 곱셈 알고리즘의 시간 복잡도가 O(n^2)인 데에 반해 카라추바 알고리즘의 시간 복잡도는 O(n^1.585)밖에 나오지 않는다. 혁신인 것이다! O(n^2)와 O(n^1.585)가 차이가 별로 안 난다고 생각할 지도 모르지만, n이 1부터 50까지 커질 때 O(n^2)와 O(n^1.585)의 차이를 보면 다음과 같다. for n in range(1, 51): print("When N is", n, "- O(n^1.585):", n**1.585, "O(n^2): ", n**2) n=2일 때는 약 3과 4 정도로밖에..

빅오 표기법, 개발을 시작한 지 일주일에서 한 달 정도 되었으면 누구나가 들어 보셨을 겁니다. 못 들어 봤더라도 O(n), O(n log n)과 같은 표기들은 분명히 보셨을 겁니다못 보셨어요? 그러면 문과 가세요. 그만큼 개발자들과 떼려야 뗄 수 없는, 마치 수영장과 물, 스키장과 눈(!) 같은 존재가 개발자들과 시간 복잡도입니다. 빅오는 그걸 나타내는 표기 중 하나이고요. 빅오는 상한을 의미합니다. 하한을 의미하는 빅오메가도 있고, 평균을 의미하는 빅세타도 있어요. 그런데 빅오를 쓰는 이유는 상한으로 표기해야지 틀리지 않기 때문이에요. 예를 들어 어떤 프로그램이 1초 안에 돌아가겠다고 예상한다면 0.5초 안에 돌아가든 0.3초 안에 돌아가든 상관이 없습니다. 그런데 0.5초나 0.3초 안에 돌아간다고 ..

저번에 백준의 8393번 문제를 풀며 이 공식에 관한 이야기를 잠시 했다. 오늘 그 이유를 증명해보고자 한다. 시작하기 앞서, 이 공식은 고등학교 수학I의 수열 단원에 나오며, 그 이름도 유명한 가우스가 사용했던 공식이라고 한다. 우선 공차가 1인 등차수열 A가 있다고 생각해보자. 첫째항이 a, 공차가 d인 등차수열의 일반항은 An = a + (n - 1)d 이므로, An = n 이다. 그렇다면 1부터 n까지의 이 수열은 {1, 2, 3, 4, 5, 6, 7, 8, ... , n-3, n-2, n-1, n} 이 될 것이다. 그렇다면 1부터 n까지의 합을 구하려면, 1부터 n까지 직접 더하는 방법이 있다. 그렇지만 이 방법은 너무나 비효율적이다. s = 0 n = int(input()) for i in r..