목록분류 전체보기 (317)
지나가던 개발자
분할 정복(Divide and Conquer)은 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트나 병합정렬이 있다. 나무위키에서 인용했다. 거듭제곱 또한 분할 정복 알고리즘을 활용하여 빠르게 계산이 가능하다. 임의의 수 C에 대하여 Cⁿ을 구할 때는 C를 n번 곱하므로 시간 복잡도가 O(n)인 반면, 분할 정복을 활용하여 계산하면 O(logn)의 시간 복잡도로 계산이 가능하다. 훨씬 빨라지는 것이다. 분할 정복을 활용하여 거듭제곱을 계산하는 것은 다음과 같은 아이디어로부터 출발한다. $$ C^{n} = \begin{cases} ..
[Algorithm] 오일러 피 함수(Euler's phi function) | 서로소인 자연수의 개수 구하기 | Python
오일러 피 함수(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과의 서로소의 개수의..
[Python] 백준 4355번(서로소) 문제 풀이
def power(A, n): res = 1 while n: if n % 2 != 0: res *= A A *= A n //= 2 return res def factorization(x): d = 2 factorization = [] while d
[Python] 백준 6992번(Arithmetic Sequence) 문제 풀이
for i in range(int(input())): sequence = list(map(int, input().split()))[1:] if len(sequence) == 0: continue if len(sequence) == 1: print("The next 5 numbers after [" + str(sequence[0]) + "] are: [", end="") for i in range(1, 6): if i == 5: print(str(sequence[0]+i) + "]") continue print(str(sequence[0]+i) + ", ", end="") elif len(sequence) == 2: print("The next 5 numbers after [" + str(sequence[..
[Python] 백준 1546번(평균) 문제 풀이
input() grade = list(map(int, input().split(" "))) m = max(grade) for i in range(len(grade)): grade[i] = grade[i]/m*100 print(sum(grade)/len(grade))
[Mathematics] 삼각형의 한 변과 양 끝각을 알 때의 넓이 구하기
삼각형이 결정될 때, 일반적으로 그 결정조건을 가지고 넓이를 구할 수 있다. 예를 들어, 삼각형의 세 변을 알 때는 헤론의 공식을 사용하고, 삼각형의 두 변과 그 끼인각을 알 때에는 삼각비를 활용하여 넓이를 구한다. 그런데 삼각형의 한 변과 양 끝각을 알 때에는 그 넓이를 어떻게 구할까? 그 공식을 알아내 보도록 하자. 다음과 같은 삼각형에서 a와 각B, 각C를 알고 있다. 삼각형의 내각의 합은 180도이므로 각A 또한 결정된다. 여기서 다음과 같은 사인법칙은 자명하다. $$ \overline{BC} = a $$ $$ \overline{AC} = b $$ $$ \overline{AB} = c $$ $$ \frac{a}{sinA} = \frac{b}{sinB} = \frac{c}{sinC} $$ a와 B,..
[Python] 백준 10769번(행복한지 슬픈지) 문제 풀이
message = input() if message.count(":-)") == 0 and message.count(":-(") == 0: print("none") elif message.count(":-)") == message.count(":-("): print("unsure") elif message.count(":-)") > message.count(":-("): print("happy") else: print("sad") 파이썬은 PS 치트다...
