나름 개발자의 IT블로그

이항연산(binary operation) 어떤 집합 $S$에서 이항연산 $*$가 $S \times S \rightarrow S$인 사상이다. 순서쌍 $(a,b)\in S \times S$에 대해 $S$의 원소 $*((a,b))=a*b$로 나타낸다. 이를 우리가 평소 하던 실수 덧셈에 대입해 보자면 $S = \mathbb{R}, *=+$ 가 된다. 이항연산에서 핵심은 순서쌍의 집합과 연산 결과의 집합이 같아야 한다는 것이다. 이를테면 다음은 이항연산이 아니다. $S = \mathbb{Z^+}, *=-$ $a=1, b=3$을 선택할 경우 $a-b=-2$가 되어 $\mathbb{Z^+}$에 포함되지 않기 때문이다. 유도된 연산(induced operation) $*$가 $S$위에서 이항연산이고 $H \subs..

우리가 늘 하던 덧셈과 곱셈은 두개의 항을 가지고 연산을 한다. 그래서 우리는 이 연산을 이항연산이라고 부른다.(코딩할때와 비슷한 개념같다.) $ x + x = a \space (a \in \mathbb{R})$ 인 경우 $ x = \frac{a}{2}$ 라는 것을 안다. 하지만 $ a

평소에 수학을 좋아하기도 하고 알고리즘 문제를 풀며 상당히 많은 개념이 현대대수에 들어있는 것 같다. 휴학이기도 하고 개발도중에 기분전환으로 수학 한번 해보고 싶어 취미로 공부해보려고 한다. (수박 겉핥기가 되겠지만...) 비전공자이지만 알아두면 언젠가는 쓸모 있을 것 같아 블로그로 정리하기로 했다. 유튜브와 Fraleigh 책으로 공부할 예정이다. (포스트하며 틀린 내용이 있을 수 있습니다. 그런 경우 댓글로 남겨주세요..)

알고리즘을 풀며 쌓아온 꿀팁 아닌 꿀팁을 정리하고자 한다. 1. (파이썬) 여러개의 변수 입력받기 # 여러개의 변수 a,b,c = map(int, input().split()) # 1 2 3 # 한줄로 입력받는 리스트 arr = list(map(int, input().split())) # 1 2 3 4 5 6 7 8 9 # 여러줄을 입력받는 리스트 arr = [int(input()) for _ in range(n)] # 1 # 2 # 3 # 4 # 2차원 배열 arr = [list(map(int, input().split())) for _ in range(n)] # 1 2 3 # 4 5 6 # 7 8 9 2. (파이썬) 배열 초기화 # 1차원 배열 a = [0]*n # 2차원 배열 a = [[0]*n f..

알고리즘 문제를 풀다 보면 "답이 커질 수 있으니 $1,000,000,007$로 나눈 나머지를 출력하시오" 이런 문장이 많이 보인다. 오늘은 이런 나머지연산에 대한 이야기를 하고자 한다. 피보나치 수 7 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제를 한번 보자 단순히 문제에서 제시한대로 구현한다면 이런 코드가 나올것이다. n = int(input()) a, b = 0, 1 for i in range(n): a,b = b, a+b print(a%1000000007) 하지만 이렇게 제출하게 되면 시간초과 또는 틀렸습니다를 받는다. 그 이유는 계산 과정에서 a, b의 값이 매우 커지기 때문이다. 이를 ..

피보나치 수는 많은 성질을 가지고 있다. 이 포스트에서 소개하고자 한다. 여기서 살펴볼 피보나치수열은 다음과 같다. $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..

이전 글에서 피보나치 수를 구하다가 빠른 거듭제곱이 나와 따로 글로 남기게 되었다. 거듭제곱을 위해 다음 코드를 작성하면 $O(N)$의 시간이 필요하다. def pow(a,n): r = 1 for _ in range(n): r *= a return r 위 코드는 거듭제곱을 $a^n=a^{n-1} \times a$ 방식으로 구한다. 이것을 빠르게 해 보자! $n$이 짝수이면 $a^n = a^{n/2} \times a^{n/2}$ $n$이 홀수이면 $a^n = a^{n/2} \times a^{n/2} \times a$ 가 된다. 이제 이것을 재귀적으로 계산하면 된다. 예를 들어 $3^{60}$을 계산해보자 $3^{60} = 3^{30} \times 3^{30}$ $3^{30} = 3^{15} \times 3..

피보나치 수열은 다음 조건을 만족하는 수열이다. $F_0=1, F_1=1, F_n=F_{n-1}+F_{n-2} \ (n \gt 2)$ $1,1,2,3,5,8,13...$ (경우에 따라서 $F_0=0$이 되기도 함) 위 식을 사용해서 구하면 시간 복잡도가 $ O(N) $이기 때문에 $N