뭘 배웠지?

이산수학 12강을 보며 배운내용 순열(Permutation) 순서를 고려해서 r개의 원소를 뽑는 경우의 수 P(n, r) = n! / (n - r)! 중복집합에서 순열 중복된 원소가 p개, q개, r개가 있을 때, n개를 일렬로 배열하는 경우의 수 n! / p! q! r! 이런 것도 풀 수 있다 노드 A에서 노드 B까지 최단 경로의 방법의 수 위로 4번, 오른쪽으로 6번가면 최단경로다 10개의 변을 지나는 것이니까 10! / 6! x 4! = 210 중복 순열 중복을 허용하고 순서를 고려해서 r개의 원소를 뽑는 경우의 수 ∏ (n, r) = nr 예시) S, A, N, T, A 문자 중 3개를 이용해서 만들 수 있는 단어 개수(중복 허용) ∏ (5, 3) = 53 = 125 만약 중복이 허용되지 않으면 ..

이산수학 11강을 보며 배운내용 트리 사이클이 없는 단순 연결 그래프를 트리(tree)라고 한다 루트 트리 루트 노드로부터 서브 트리가 나와있다 트리 주요 용어 부모(parent) 노드 자식(child) 노드 형제(sibling) 노드 차수(degree): 자식 노드의 수 전체 차수는 트리 차수 중 가장 큰 것을 말한다 리프(leaf) / 단말(terminal) 노드: 자식이 없는 노드 레벨(level): 루트에서 N까지 경로의 길이 높이(height) / 깊이(depth) 무게(weight): 리프 노드의 개수 닮은 트리: 트리의 구조는 동일하지만, 노드의 데이터가 다를 때 주요 정리 n개의 꼭지점을 갖는 트리는 n - 1개의 변을 가진다 이진 트리(Binary Tree) 공집합이거나, 모든 노드가 최..

이산수학 10강을 보며 배운내용 정리(TL;DR) 평면 그래프 모든 변이 교차하지 않는 그래프 오일러 사이클 모든 변을 한 번만 지나고, 시작점과 종점이 같다 해밀턴 사이클 모든 꼭지점을 한 번만 지나고, 시작점과 종점이 같다 가중 그래프 각 변에 가중치가 있는 그래프 최단 경로, 신장 트리 등에 이용 평면 그래프 그래프의 모든 변이 교차하지 않는 그래프 평면 그래프 예시 1 평면 그래프 예시 2 왼쪽의 이미지의 변을 옮기면 오른쪽처럼 되는데 겹치는 변이 없어서 평면 그래프다 오일러의 공식(Euler's Formula) 연결된 평면 그래프에서, 꼭지점의 수 v, 변의 수 e, 면의 수 f 라고 하면 v(꼭지점) - e(변의 수) + f(면의 수) = 2 4색 정리 지도의 인접한 구역을 서로 다른 색으로 ..

이산수학 9강을 보며 배운내용 한 붓 그리기 홀수 점이 없거나, 2개인 경우만 가능 그래프 용어를 정리하자 꼭지점(vertex)와 변(edge)로 구성 변: 두 꼭지점을 연결 인접(adjacent): 연결된 두 꼭지점을 인접한 꼭지점라고 한다 병렬변(parallel edge): 두 꼭지점 사이에 변이 여러 개 일때 루프(loop): 자기 자신을 가리키는 변 고립된 꼭지점(isolated vertext): 어떤 변이랑도 연결 안된 것 방향 그래프: 방향이 있는 그래프 무향 그래프: 방향이 없는 그래프 단순 그래프: 루프와 병렬변이 없는 무향 그래프 그래프에서 총 차수는 항상 짝수다! 변은 항상 2개의 꼭지점을 발생시키니까 그래프 탐색정의 그리고 워크, 트레일, 경로 기본 가정 정의 1 정의 2 워크 W의 ..

이산수학 8강을 보며 배운내용 디지털 논리회로 AND, OR 등 논리적인 연산을 하는 것을 논리회로 하는데, 컴퓨터 안에서 0과 1을 처리하는 것을 디지털 논리회로라고 부른다 기본 논리게이트 AND, OR, NOT 추가적인 게이트 NAND: AND 연산에 NOT 붙인 것 NOR: OR 연산에 NOT 붙인 것 그리고 베타합 XOR, 이에 NOT을 붙인 XNOR 부울대수 기본정리 부울함수의 보수 보수란 NOT을 붙여주는 것 인간이 하기 편한 드모르간 법칙, 혹은 기계가 편한 쌍대로 구할 수 있다 드모르간 법칙 부울함수의 대수적 간소화 간소화가 필요한 이유는 다음 그림을 보면 확실하다 밑의 두 논리회로는 같은 역할을 한다 두 번째를 쓰지 않을 이유가 있을까? 복잡한 부울함수를 대수 공식을 이용해서 부울함수를 ..

이산수학 7강을 보며 배운내용 함수 함수의 표시 중 하나 f: X -> Y X를 정의역, Y를 공역이라고 부른다 ❔ 함수끼리 상등하다는 것은 f: X -> Y, g: A -> B 이런 f,g 함수가 있을 때 X = A, Y = B f(x) = g(x) => f와 g는 같다(상등하다) 전/단사 함수를 배우는 이유는 역함수를 배우기 위해 전사함수(Surjective function) X의 값들이 Y의 값 모두를 가리키고 있을 때 다른 말로, 정의역(X의 원소)들이 치역(Y의 원소) 모두를 가리키고 있을 때 기호 논리를 이해하는 것이 중요 치역이 공의역 전체와 같으면 전사함수 단사함수(Injective function) 하나에 하나씩 대응되는 단사함수 전단사함수(Bijective function) X의 원소의..

이산수학 6강을 보며 배운내용 곱집합 A의 원소와 B의 원소의 모든 순서쌍의 집합 관계 집합 X에서 집합 Y로의 관계 R은 X × Y의 부분집합 xRy로 표시 여기서 관계는 이항 관계(binary relation) 관계의 표현 1. 화살표 도표 2. 방향 그래프 3. 부울행렬 관계의 성질 반사적 본인과의 관계 (a, a) 이런 관계가 모든 원소에 있다면 반사적 대칭적 (1, 2)가 있으면 (2, 1)도 있으면 대칭적 추이적 (1, 2)가 있고 (2, 3)가 추이적이려면, (1, 3)이 있어야 된다 관계의 종류 역관계 (a, b)를 (b, a)로 바꾼것 합성관계 관계 둘을 합친 것 동치관계 반사적, 대칭적, 추이적이면 동치관계라고 한다 동치류

이산수학 5강을 보며 배운내용 행렬은 뭐고? 어디에 쓰이나? 행과 열로 사각형 형태로 수를 배열 활용 분야 프로그래밍 언어 자료구조 컴퓨터 그래픽 패턴인식 로봇동작 인공지능 등 🔅 정의 m개의 행과 n개의 열로 구성된 직사각형 수 배열 A를 m x n 행렬이라고 한다 행벡터: 1 x n 열벡터: n x 1 영행렬 모든 원소가 0일 행렬 행렬의 기본 연산은 이렇구나 크기가 같은 행렬 A, B가 있고, k를 실수라 가정 🔅 행렬의 합과 차 각 자리들끼리 더해주거나 빼주면 된다 🔅 스칼라 곱 각 자리(원소)에 k를 곱하기 스칼라는 실수! 단어에 겁먹지 말자 아래의 연산 법칙 만족한다 교환법칙 결합법칙 항등원 합의 역원 스칼라 곱의 결합법칙 스칼라 곱의 분배법칙 🔅 행렬의 곱 A가 m x n 행렬, B가 n x..

이산수학 4강을 보며 배운내용 집합 {a, b} => 집합 {{a}, k} => 집합 {a, b, a, c} => 집합이 아니다 같은 원소가 있어서 부분집합(subset) A의 모든 원소가 B의 원소라면 A는 B의 부분집합, A ⊆ B 진부분집합(proper subset) A는 B의 진부분집합이란 말은 B가 A외에 더 있는거 상동(equal) A = B (A ⊆ B && B ⊆ A) 서로소(disjoint) A ∩ B = Ø 둘이 공유하는 원소가 없네 joint가 아니라는(dis) 말이네 분할(partition) A를 겹치지 않게 분할하고 어떤 부분도 Ø이 아닌거 A = {1, 2, 3, 4} {Ø, {1, 2}, {3, 4} } => 분할 아니다 Ø 때문에 { { 1 } { 2 } { 3, 4 } } ..

이산수학 3강을 보며 배운내용 KEYWORDS 공리(axiom) 다른 명제를 증명하려고 사용되는 기본적인 가정 증명 없이 참으로 이용하는 명제 증명(proof) 특정 공리들을 가정하고, 가정하에 제안된 명제가 참인지 입증하는 작업 정리(theorem) 공리로부터 증명된 명제 증명 방법 직접 증명법 공리, 정의 그리고 정리를 논리적으로 직접 연결 수학적 귀납법 자연수 n에 대한 명제의 성징을 증명하는데 유용하다 기본단계, 귀납가정, 귀납단계 이용 간접 증명법 증명하기 쉽게 변형해서 증명 예) 대우 증명법, 모순 증명법, 반례 증명법 등 직접 증명법(direct proof) 연역법(deduction)이라고도 한다 명제를 변형하지 않고 증명 주로 공리, 정의, 증명된 정리를 논리적으로 직접 증명한다 예) 두 ..