나름 개발자의 IT블로그

얼마 전에 ChatGPT를 사용할 일이 있어서 가지고 놀다가 우연히 소수판정 알고리즘을 알려달라고 했는데 다음과 같은 코드를 뱉어냈다. def is_prime(num): if num

사전지식 (정수론) 유클리드 호제법 합동 페르마 소정리 중국인의 나머지 정리 오일러 피 함수 분할정복을 이용한 거듭제곱 대칭키 시스템 Key $p$ : 큰 소수 $e$ : 암호화 키 (홀수) $d$ : 복호화 키 (홀수) $ed \equiv 1 \mod p-1$ $\gcd(e, p-1) = 1$ 이렇게 3개의 키를 사용한 암호화 알고리즘을 사용한다. $p$는 큰 소수이기 때문에 홀수임이 자명하다. $C \equiv m^e \mod p$으로 암호화된 $C$를 구할 수 있다. ($m$은 원본 데이터) 반대로 $m \equiv C^d \mod p$로 복호화할 수 있다. $m = C^d = (m^e)^d = m^{ed} = m$임을 사용한 심플한 알고리즘이다. 문제점은 메시지를 보내는 sender와 그 메시지를..

이번에 4솔을 하여 민트로 복구할 수 있었다. 코드포스가 있던날 백준, 앳코더도 함께 진행해서 좀 힘든하루였다.(백준 4시간, 앳코더 1시간, 코드포스 2시간..) A - Min Or Sum [Solved!] 배열 $a$에서 서로 다른 원소 $a_i, a_j$를 뽑아 $a_i|a_j = x|y$를 만족하면서 $a_i = x, a_j = y$인 연산을 반복할 때 가능한 배열의 합의 최솟값을 찾는 문제이다. $x = a_i|a_j, y = 0$으로 두면 위 조건을 만족한다. 이 연산을 반복해서 하나의 원소에 적용하면 결국 배열은 $a_1|a_2| \dots | a_n, 0,0, \dots , 0$모양이 될 것이다. 이 때가 최소가 된다. B - Avoid Local Maximums [Solved!] 배열의 ..

피보나치 수는 많은 성질을 가지고 있다. 이 포스트에서 소개하고자 한다. 여기서 살펴볼 피보나치수열은 다음과 같다. $F_1 = 1, F_2 = 1, F_n = F_{n-1} + F_{n-2} \ (n\ge3)$ 1. $\sum_{k=1}^n F_k = F_{n+2} - 1$ 정의에 따라 $F_1 = F_3 - F_2$ $F_2 = F_4 - F_3$ ... $F_n = F_{n+2} - F_{n+1}$ 이다. 그럼 식을 다음과 같이 변형할 수 있다. $F_1+F_2+...+F_n$ $= (F_3-F_2)+(F_4-F_3)+...+(F_{n+2}-F_{n+1})$ $= F_{n+2} - F_2$ $= F_{n+2} - 1$ 이를 통해 $\sum_{k=a}^b F_k $ $= \sum_{k=1}^b F_k..