나름 개발자의 IT블로그

순환군 $G$가 군이고 $a \in G$일때 $H=\{ a^n | n \in \mathbb{Z}\}$인 군 $H$는 $G$의 부분군이며 a에 의해서 생성되는 G의 순환 부분군(cyclic subgroup $\langle a \rangle$ of generated by $a$)이다. 또한 $H$는 $a$를 포함하는 $G$의 가장 작은 부분군이다. $a$는 $H$의 생성원(generator of $G$)이며 군 $H=\langle a \rangle$는 순환적(cyclic)이라고 한다. 순환군의 성질 1. 모든 순환군은 가환이다. 2. 순환군의 부분군은 순환적이다. 3. $G = \langle a \rangle$라 할때 $G$는 $\mathbb{Z}$나 $\mathbb{Z_n}$과 동형이다. 4. $G = \..

지금까지는 이항연산의 예를 들기 위해 $*$기호를 사용하였지만 앞으로는 기호를 다음과 같이 표기하기로 한다. 군(Group) 아벨군(Abelian group) $a*b$ $ab$ $a+b$ 항등원 $1$ $0$ 역원 $a^{-1}$ $-a$ $\overbrace{a*a*\cdots *a}^{\rm n}$ $ a^n = \overbrace{aa\cdots a}^{\rm n}$ $ na = \overbrace{a+a+\cdots +a}^{\rm n}$ 단순 덧셈, 곱셈기호같이 보이지만 실제로 덧셈, 곱셈의 역할을 하는 것은 아니다. 군에서의 이항연산을 표기만 저렇게 하는 것이다.(생각보다 편리한 부분이 많은 것 같다.) 위수 군$G$에 속하는 원소의 개수를 $G$의 위수(order) $|G|$라고 한다. 부..

군 군(Group) $\langle G, *\rangle $는 이항연산 $*$아래에 닫혀있고 다음 공리를 만족하는 집합 $G$이다. $\mathcal{G_1}$: 모든 $a,b,c \in G$에 대해 $(a*b)*c=a*(b*c)$을 가진다. (결합법칙) $\mathcal{G_2}$: 모든 $x \in G$에 대해 $e*x=x*e=x$인 $e \in G$가 존재한다. ($*$에 대한 항등원의 존재) $\mathcal{G_3}$: $a \in G$에 대응하는 $a'*a=a*a'=e$인 $a' \in G$가 존재한다.($a$의 역원 존재) 특히 군이면서 연산 $*$가 가환인경우 Abel군(Abelian group)이라고 한다. 즉 군이란 결합법칙, 항등원, 각 원소에 대한 역원을 가진 이항연산을 갖춘 집합이..

이항 대수적 구조 지금까지 "연산을 집합 $S$에 대하여 이항연산 $*$가 있을 때..."라고 표현을 했다. 앞으로 이를 간략화 하여 $(S, *)$로 표기하고 이항 대수적 구조(binary algebraic structure)라고 부른다. $(\mathbb{R},+)$같은 경우는 실수의 덧셈 연산에 대한 이항 대수적 구조라고 보면 된다. 동형 이항 구조 두 이항구조가 구조적으로 같기 위해서는 다음 조건을 만족해야 한다. 두 이항구조 $(S, *), (S', *'), x \in S, x' \in S'$에서 만약 $x \leftrightarrow x', y \leftrightarrow y'$이면 $ x*y \leftrightarrow x' *' y'$인 일대일 대응관계를 만족해야 한다. 여기서 $x \le..

이항연산(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..