본문 바로가기

이산수학65

[이산수학]최소신장 트리란?/ 최소신장 트리 구하는 알고리즘 [이산수학]최소신장 트리란?/ 최소신장 트리 구하는 알고리즘(프림,크루스칼) ■ 신장 트리(Spanning Tree)란? 그래프 G의 꼭짓점을 모두 노드로 포함하는 트리 T ■ 최소신장 트리(Minimal Spanning Tree)란? 그래프 G의 꼭짓점을 모두 노드로 포함하면서 비용을 최소로 하는 트리 T 최소신장 트리를 구하기 위해서는 노드와 노드를 연결하는 변에 가중치가 부여된 그래프가 있어야 합니다. 또한 비용이 최소인 트리로 만들기 위한 알고리즘도 필요합니다. ■ 최소신장 트리 구하는 알고리즘 프림 알고리즘(Prim Algorithm) 그래프 G의 변 중 비용이 가장 낮은 변들을 가지로 연결시켜서 트리로 만드는 알고리즘 ▶프림 알고리즘 설명 더 보러가기 크루스칼 알고리즘(Kruskal Algor.. 2020. 8. 30.

[이산수학]최소신장 트리 구하는 크루스칼 알고리즘(Kruskal Algorithm) 이란? [이산수학]최소신장 트리 구하는 크루스칼 알고리즘(Kruskal Algorithm) 이란? 크루스칼 알고리즘은 프림 알고리즘과 마찬가지로 그래프 G의 변들 중 비용이 가장 낮은 변들을 가지로 연결시켜 트리를 만드는 알고리즘입니다. 프림 알고리즘은 이미 연결되 노드에 근접하는 가지 중 최소 비용을 갖는 가지를 선택했지만, 크루스칼 알고리즘은 연결 여부와 상관없이 가장 비용이 낮은 가지를 연결해갑니다. ▶프림 알고리즘에 대해 더 알고 싶다면 ■ 크루스칼 알고리즘(Kruskal Algorithm) 그래프 G의 변 중 비용이 가장 낮은 변들로 트리를 구성하는 알고리즘 (1) 가중치가 가장 작은 변을 차례로 선택하여 노드들을 연결 (2) 가중치가 같은 변은 임의로 선택 (4) 선택된 변에 대해 회로가 형성되는 경.. 2020. 8. 29.

[이산수학]최소신장 트리 구하는 프림 알고리즘(Prim Algorithm)이란? [이산수학]최소신장 트리 구하는 프림 알고리즘(Prim Algorithm)이란?_예제포함 최소신장 트리(Minimal Spanning Tree)란 '그래프 G의 꼭짓점을 모두 노드로 포함하면서 비용을 최소로 하는 트리 T'입니다. 그래서 최소신장 트리를 구하기 위해서는 다음 두 가지 요소가 있어야 합니다. 1. 노드와 노드를 연결하는 변에 가중치에 부여된 그래프 2. 비용이 최소인 트리로 만들기 위한 알고리즘 2번의 알고리즘에는 프림 알고리즘(Prim Algorithm)과 크루스칼 알고리즘(Kruskal Algorithm)이 있습니다. 이 글에서는 프림 알고리즘에 대해 알아보겠습니다. ■ 프림 알고리즘(Prim Algorithm) 그래프 G의 변 중 비용이 가장 낮은 변들로 트리를 구성하는 알고리즘 (1.. 2020. 8. 28.

[이산수학]이진 탐색 트리란?_예제포함 [이산수학]이진 탐색 트리의 정의(예제포함) 탐색(Search): 어떤 원소를 찾아가는 과정 키(key): 탐색에서 기준이 되는 값 ■ 이진탐색트리(Binary Search Tree)란 노드가 가지는 데이터의 크기에 따라 노드의 위치를 탐색할 수 있는 트리 1. 트리에서 탐색되는 모든 원소는 서로 다른 유일키를 갖는다. 2. 왼쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 작다. 3. 오른쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 크다. 루트 15를 기준으로 왼쪽 서브 트리는 15보다 작은 값들로 구성되고, 오른쪽 서브 트리는 15보다 큰 값들을 구성됩니다. 즉 15는 탐색되는 모든 원소들의 유일키가 됩니다. 왼쪽 서브 트리를 보면 12를 기준으로 12보다 작은 값은 왼쪽 버스 트리를 .. 2020. 8. 27.

[이산수학]이진트리 순회표기법의 종류(전위표기, 중위표기, 후위표기)_예제포함 [이산수학]이진트리 순회표기법의 종류(전위표기, 중위표기, 후위표기)_예제포함 ■ 순회표기 이진 트리는 수식을 표현하는 방법에도 사용할 수 있습니다. 예를 들어 (a + b) × (c - d)를 표현하면 아래와 같은 트리가 됩니다. 이와 같이 식을 이진 트리로 표현할 수 있는 것처럼 식을 순회방식으로 표기할 수 있습니다. ■ 전위표기 위 이진트리를 전위표기로 나타내면 × + ab - cd 로 연산자가 피연사자보다 앞에 옵니다. ■ 중위표기 위 이진트리를 전위표기로 나타내면 a + b × c - d 로 연산자가 피연사자들의 중간에 옵니다. ■ 후위표기 위 이진트리를 전위표기로 나타내면 ab + cd - × 로 연산자가 피연사자들의 뒤에 옵니다. 예제 식 (x / y) + (w - z) × v를 전위표기, .. 2020. 8. 26.

[이산수학]이진트리의 순회(전위순회, 중위순회, 후위순회) [이산수학]이진트리의 순회(전위순회, 중위순회, 후위순회) 모든 노드의 데이터를 처리할 수 있도록 한 번씩 방문하는 방법을 순회(Traversal)라고 합니다. 서브 트리에서 루트 노드(P)를 언제 방문하느냐에 따라 전위순회, 중위순회, 후위순회가 있습니다. 먼저 노드를 방문하는 순서를 확인하겠습니다. ■ 노드를 방문하는 순서 1 항상 루트에서 시작합니다. 즉, 트리의 레벨 0에서 시작합니다. 2 서브 트리에 대한 순회의 순서는 항상 왼쪽에서 오른쪽으로 이루어집니다. 3 데이터를 읽기 전에 왼쪽, 혹은 오른쪽 노드가 있는지 확인하는 작업을 합니다. 그럼 각 순회는 어떤 방식으로 이루어지는지 보겠습니다. ■ 전위순회(Preorder Traversal) 루트 노드 - 왼쪽 노드 - 오른쪽 노드 순으로 방문하.. 2020. 8. 26.

[이산수학]배열로 구현한 이진 트리 [이산수학]배열로 구현한 이진 트리 ■ 배열로 구현한 완전 이진 트리 - 각 노드 변호를 인덱스로 하여 1차원 배열로 구현할 수 있습니다. - 노드 번호는 1부터 시작하므로 배열에서 인덱스가 0인 자리는 비워두고, 인덱스가 1인 자리부터 노드 값을 저장하면 됩니다. ■ 배열로 구현한 편향 이진 트리 - 노드 인덱스는 완전 이진 트리처럼 왼쪽 자식 노드 인덱스는 2n, 오른쪽 자식 노드 인덱스는 2n+1입니다. - 편향 이진 트리를 구성하는 각 노드의 인덱스에 해당하는 배열의 영역에 노드 값이 들어갑니다. - 그래서 메모리 공간의 낭비가 발생합니다. ■ 이진 트리에서 각 노드의 인덱스 규칙 - 레벨 1의 노드 인덱스 2번과 3번은 부모 노드인 1번의 2배 또는 2배에 1를 더한 것입니다. - 즉, 노드 인.. 2020. 8. 26.

[이산수학]연결리스트로 구현한 이진 트리 [이산수학]연결리스트로 구현한 이진 트리 배열로 편향 이진 트리를 구현하면 메모리의 낭비가 발생합니다. 이런 문제는 연결리스트로 해결할 수 있습니다. ■ 연결리스트로 구현한 이진 트리 연결리스트는 부모 노드와 자식 노드를 주소로 연결하기 때문에 연속된 메모리 영역이 아니더라도 부모와 자식 노드를 연결할 수 있습니다. 연결리스트는 왼쪽 노드와 오른쪽 노드를 가리키는 포인터 영역과 데이터를 저장하는 데이터 영역으로 구성됩니다. 하지만 잎 노드의 경우 자식 노드를 갖기 않기 때문에 자식 노드 주소가 null로 채워집니다. ■ 연결리스트로 구현된 완전 이진 트리 / 편향 이진 트리 연결리스트는 부모 노드와 자식 노드 간에 주소(포인터)로 연결되어 있기 때문에 편향 이진 트리라 하더라도 메모리를 낭비하지 않고 구.. 2020. 8. 25.

[이산수학]이진 트리의 정의 및 종류(완전, 포화, 편향) [이산수학]이진 트리의 정의 및 종류(완전, 포화, 편향) 부모 노드가 몇 개의 자식 노드를 가졌느냐에 따라 트리의 종류가 달라집니다. n개의 노드일 때, 즉 트리의 최대 차수가 n인 경우를 n항 트리(n-ary tree)라고 합니다. 이진 트리(또는 이항 트리)는 최대 차수가 2인 트리입니다. 즉, 최대로 가질 수 있는 자식 노드가 두개인 트리입니다. ■ 이진 트리(Binary Tree) 트리 T를 구성하는 부모 노드가 갖는 자식 노드의 수가 최대 2개인 트리 자식 노드가 하나도 없거나, 하나 혹은 두 개를 갖는 트리 모두 이진 트리에 속합니다. 최대 차수가 2로 제한되기 때문에 이진 트리는 왼쪽 서브 트리와 오른쪽 서브 트리를 구분합니다. 이진 트리는 완전 이진 트리와 편향 이진 트리로 나눌 수 있습.. 2020. 8. 25.

[이산수학]노드와 변에 대한 정리/트리에 대한 정리_예제포함 [이산수학]노드와 변에 대한 정리/트리에 대한 정리 ■ 노드와 변에 대한 정리 트리에서 노드의 개수를 v, 변의 개수를 e라고 하면, e = v - 1 입니다. 예제 (1) 노드의 수가 16개인 트리에 존재하는 변의 수는? (2) 변의 수가 24개인 트리에 존재하는 노드의 수는? 풀이 더보기 예제풀이 (1) 15개 (2) 25개 ■ 트리에 대한 정리 n개의 꼭짓점을 갖는 연결 그래프T에 대해 다음은 동치입니다. 1. T는 트리다 2. T의 변의 수는 n - 1개다. 3. T에서 변 하나를 제거하면 연결 그래프가 아니다. 4. T에 속하는 서로 다른 꼭짓점 w, v에 대해, w에서 v로 가는 유일한 경로가 존재한다. 수학으로 이해하는 디지털 논리 이산수학 359p 참고 --------------------.. 2020. 8. 25.

[이산수학]트리(Tree)의 정의와 관련 용어 정리(노드, 차수, 레벨, 숲 등)_예제포함 [이산수학]트리(Tree)의 정의와 관련 용어 정리(노드, 차수, 레벨, 숲 등) ■ 트리(Tree) - 트리 T는 비순환, 연결 그래프 - 루트(Root)라고 불리는 노드가 반드시 하나 있어야 함 - 트리 T를 구성하는 꼭짓점 v, w 간에, v에서 w로 가는 단순 경로가 있음 ▶ 선형과 비선형, 순환과 비순환의 뜻은? ■ 서브 트리(Sub Tree) - T를 구성하는 꼭짓점 v를 루트로 하는 트리 예제 다음 중 트리인 것은? 풀이 더보기 예제풀이 (1) A가 루트며 그래프를 구성하는 꼭짓점 A부터 G 사이에는 단순 경로만 존재하므로 트리다. (2) A-B-D 간에 순환 경로가 존재하고, A-B-D와 C-E가 연결되지 있지 않으므로 비연결 그래프다. 그러므로 트리가 아니다. 아래 트리(Tree)로 관련.. 2020. 8. 24.

[이산수학]선형과 비선형, 순환과 비순환의 차이는? [이산수학] 선형과 비선형, 순환과 비순환의 차이/개념/예 ■ 선형과 비선형(Linear vs. Nonlinear) - 선형: 직선의 형태를 가지며, 1차 방정식을 선형방정식이라고 합니다. 1차 방정식 y = ax + b는 출력되는 y에 대응되는 입력 x가 반드시 하나 존재합니다. 따라서 값을 예측가능하면 '선형적'이라고 합니다. - 비선형: 선형의 반대말입니다. 곡선의 형태를 가지며 결과를 예측할 수 없는 경우를 '비선형적'이라고 합니다. ■ 순환과 비순환(Cycle vs. Acyclic) - 순환: 시작점과 끝점이 같은 경로 - 비순환: 시작점과 끝점이 다른 경로 수학으로 이해하는 디지털 논리 이산수학 353p 참고 ----------------------------------- 이산수학 총정리 목록.. 2020. 8. 24.

[이산수학]부분순서관계란? (비교가능/비교불가능/완전순서) [이산수학]부분순서관계란? (비교가능/비교불가능/완전순서)_예제포함 관계는 순서쌍으로 표현합니다. 순서쌍은 원소 나열에 의미가 있음을 말합니다. (a, b)와 (b, a) 같이 a와 b의 나열에 따라 서로 다른 원소가 됩니다. 관계 중에는 그 성질이 무엇이냐에 따라 모든 원소가 부분적인 순서관계를 갖는 경우가 있습니다. ■ 부분순서관계(Partial Order) 부분순서관계가 되려면 반사관계, 반대칭관계, 추이관계가 성립해야 합니다. 이때 부분순서관계는 꼭 반대칭관계가 성립해야 합니다. 반대칭관계는 (a, b) ∈ R이고, a ≠ b 일 때는 (b, a) ∉ R 이어야 성립합니다. 그래서 원소 a와 원소 b사이의 순서관계가 확실할 수밖에 없습니다. ■ 비교가능(Comparable)/비교불가능(Noncom.. 2020. 8. 21.

[이산수학] 추이폐포와 연결관계 ■ 추이폐포(Transitive Closure) 집합 A에 대해, 관계 R를 포함하면서 추이관계를 갖는 관계 S 추이페포를 구하는 과정에서 새로운 순서쌍이 생기기 때문에 앞서 다룬 반사폐포나 대칭폐포를 구하는 것보다 복잡합니다. 예를 들어 집합 A = {1, 2, 4} 집합 A에 대한 관계 R = {(1,1),(1,4),(2,1),(4,2)} 위의 두 요건을 이용해 추이페포 S를 구해보겠습니다. (2,1)이 관계 R에 존재하고, (1, 4) 또한 존재합니다. 추이폐포가 되기 위해서는 (2,1)의 앞의 원소 2와 (1,4)의 뒤의 원소인 4으로 만들어진 순서쌍 (2, 4)이 추가되어야 합니다. 이제는 (2, 4)에 대해서도 추이폐포가 되도록 순서쌍을 추가해야 합니다. 즉 관계 R에 (2,4)도 있고, (4.. 2020. 8. 21.

[이산수학]꼭짓점, 변, 면과의 관계는? (오일러 공식에 대한 정리, v-e+s=2) 오일러 공식에 대한 정리 연결된 평면 그래프 G에서 꼭짓점 수를 v, 변의 수를 e, 면의 수를 s라고 할 때 다음 오일러 공식이 성립합니다. v - e + s = 2 증명 위의 공식을 증명하기 위해서는 변이 하나인 그래프와 둘 이상인 그래프를 나누어 고려해야 한다. (1) 변이 하나인 그래프는 다음과 같이 두 종류이다. 1) v = 1, e = 1. s = 2 로 v - e + s = 1 - 1 + 2 = 2 ∴ 오일러 공식이 성립한다. 2) v = 2, e = 1. s = 1 로 v - e + s = 2 - 1 + 1 = 2 ∴ 오일러 공식이 성립한다. (2) 둘 이상의 변으로 구성된 그래프는 수학적 귀납법을 이용해 증명한다. e = 1일 때, v - e + s = 2 - 1 + 1 = 2므로 오일러.. 2020. 8. 13.

[이산수학]그래프에서 차수란?(외차수, 내차수 구하는 예제 포함) ■ 차수(Degree) 꼭짓점 v에 근접하는 변의 수 홀수점(Odd Vertex): 차수가 홀수인 꼭짓점 짝수점(Even Vertex): 차수가 짝수인 꼭짓점 예제 풀이 더 보기를 클릭하세요 더보기 예제풀이 d(a) = 2 d(b) = 2 d(c) = 4 ■ 외차수(Out-degree) / 내차수 (In-degree) 방향 그래프에서 - 외차수: 꼭짓점 v를 시작으로 하는 화살표의 수 [out - d(v)] - 내차수: 꼭짓점 v를 끝으로 하는 화살표의 수 [in - d(v)] 예제 풀이 더 보기를 클릭하세요 더보기 예제풀이 out - d(a) = 1 in - d(a) = 0 out - d(b) = 2 in - d(b) = 0 out - d(c) = 0 in - d(c) = 2 out - d(d) = 1.. 2020. 8. 12.

[이산수학]최단경로 문제, 깊이 우선 탐색, 너비 우선 탐색이란? (예제포함) 그래프의 활용: 최단경로 문제, 깊이 우선 탐색, 너비 우선 탐색 ■ 최단경로 문제(Shortest Path Problem) |E| > 0 인 그래프 G = (V, E)에서 꼭짓점 a, b ∈ V 간의 가장 짧은 거리의 경로를 찾는 문제 출발점(Source): 경로의 시작점 도착점(Destination): 경로의 목적지 최단경로를 구할 때는 출발점부터 도착점까지 경로에 포함되는 꼭짓점들을 나열하고, 각 변 혹은 화살표에 부여된 가중치를 더하여 가장 적은 가중치의 합을 갖는 경로를 선택합니다. 이 때 다익스트라 알고리즘을 사용할 수 있습니다. 다익스트라 알고리즘은 시작점으로부터 최단경로를 갖는 점들을 차례로 탐색해가는 알고리즘입니다 . 다음과 같은 가중치 그래프를 예로 들어보겠습니다. ■ 깊이 우선 탐색(.. 2020. 8. 10.

[이산수학]인접행렬, 인접리스트로 그래프 표현하기 그래프의 표현: 인접행렬, 인접리스트 ■ 인접행렬(Adjacency Matrix) 인접행렬은 그래프를 행렬 형태로 표현하는 방법입니다. 그래프를 구성하는 꼭짓점을 행렬의 각 원소로, 꼭짓점에 근접하는 변을 1 또는 0으로 표기하여 그래프로 표현합니다. 그래프 G = (V, E) 에서 |V| = n일 때, n × n 행렬로 나타내는 방법입니다. 그래서 그래프 G = (V, E) 에서 |V| = 3일 때, 그래프 G를 인접행렬로 표현하면 3 × 3 행렬이 됩니다. 그리고 꼭짓점에 근접하는 변이 두 꼭짓점 사이에 존재하면 행렬에 해당하는 원소의 값이 1, 꼭짓점 간에 변이 존재하지 않는다면 행렬에 해당하는 원소의 값이 0이 됩니다. 위 그래프를 인접행렬로 표현해보겠습니다. G = (V, E) V = {a, b.. 2020. 8. 10.

[이산수학]그래프의 종류2(연결 그래프, 완전 그래프, 정규 그래프, 이분 그래프) 이산수학_그래프의 종류2(연결 그래프, 완전 그래프, 정규 그래프, 이분 그래프) 예제로 이해하기 ■ 연결 그래프(Connected Graph) 그래프 G = (V, E) 내에 있는 임의의 꼭짓점 u, v 간에 경로가 있는 그래프 예제 다음 중 연결 그래프인 것과 아닌 것을 구분하라. 풀이 더보기 예제풀이 (1) 그래프 안에 있는 모든 꼭지점 간에 경로가 존재한다. 예를 들어 e에서 d로 가는 경로는 e - b- c - a- f - b - d다. ∴ 연결그래프다. (2) 그래프의 꼭짓점들 중 a, b, c, d 와 e 혹은 f 간에는 경로가 존재하지 않는다 . ∴ 연결그래프가 아니다. ■ 완전 그래프(Complete Graph) 그래프 G = (V, E) 내에 있는 모든 꼭짓점 u, v 간에 변이 있는 .. 2020. 8. 9.

[이산수학]그래프의 종류1(부분 그래프, 부분신장 그래프, 동형 그래프, 평면 그래프) ■ 부분 그래프(Subgraph) 그래프 G = (V, E)가 있을 때, V' ⊆ V 이고 E' ⊆ E인 그래프 G' = (V', E') 어떤 그래프 G가 있을 때 그래프에 포함되는 일부 꼭짓점과 변으로만 그린 그래프를 부분 그래프라고 합니다. ■ 부분신장 그래프(Spanning Graph) 그래프 G = (V, E)가 있을 때, V' = V 이고 E' ⊆ E인 그래프 G' = (V', E') 부분 그래프 중에서 그래프 G의 꼭짓점을 모두 포함한 부분 그래프를 부분신장 그래프라고 합니다. 예를 들어 그래프 G가 다음과 같이 정의되고 있다고 하면, G = (V, E) V = {(A, B, C, D)} E = {(A, B), (A, D), (B, C), (C, D), (D, B)} G 그래프, G의 부분 그.. 2020. 8. 9.

[이산수학]다중그래프, 방향그래프, 가중치그래프란?(예제포함) ■ 다중 그래프(multi-graph) 그래프 G = (V, E) 중 서로 다른 두 꼭짓점 사이에 두 개 이상의 변을 허용하는 그래프 다중 그래프 변 집합에는 같은 순서쌍이 여러 개 존재할 수 있다. 꼭짓점에 근접하는 변을 두 이상 허용하기 때문입니다. 예를 들어 두 꼭짓점 a와 b에 근접하는 변이 세 개인 경우 변의 집합은 {(a, b), (a, b), (a, b)}를 부분집합으로 갖습니다. ■ 방향 그래프(Directed Graph) 변에 방향이 있는 그래프 뱡향 그래프를 순서쌍으로 표기할 때는 화살표가 시작하는 꼬짓점을 앞에, 화살표가 끝나는 꼭짓점을 뒤에 씁니다. 그러므로 꼭짓점에 근접하는 화살표가 둘 이상인 경우 화살표 방향에 따라 순서쌍의 꼭짓점 순서가 달라집니다. 즉 와 는 다릅니다. ■ 가.. 2020. 8. 9.

[이산수학]그래프 개념과 용어 정리(루프, 경로, 회로, 인접)/예제포함 그래프는 시작적 도구로써 복잡한 작업의 과정이나 구조를 표현하는 방법입니다. 현실 세계의 요소를 점의 집합과 그 점들 간의 선으로 표현합니다. 그래서 주요 도시를 연결하는 도로, 도시의 지하철 지도가 대표적인 예입니다. ■ 그래프(Graph) 그래프는 원소를 꼭짓점으로, 원소들 간의 관계를 변으로 표현합니다. 즉, 그래프는 꼭짓점과 변으로 구성되므로 꼭짓점의 집합과 변의 집합으로 표현할 수 있습니다. G - (V, E)는 "그래프 G는 꼭짓점 집합 V와 변의 집합 E로 구성된다"는 것을 의미합니다. ■ 인접(adjacent)과 근접(incident) 그래프 G = (V, E)에서 꼭짓점 u, v를 연결한 변 e가 있을 때 꼭짓점 u,v는 서로 인접하고, 변 e는 꼭짓점 u,v에 근접합니다. 그래프에서는 .. 2020. 8. 9.

[이산수학]함수의 종류(항등함수, 역함수, 상수함수, 특성함수, 바닥함수, 천정함수) ■ 항등함수(Identity Function) 집합 A에 대한 함수 f: A → A가 f(a) = a로 정의되는 관계 - 정의역과 공변역이 같고 입력한 정의역 원소의 값과 출력된 치역의 원소의 값이 같은 함수를 항등함수라고 합니다. - 그래서 항등함수는 정의역, 공변역, 치역이 모두 같습니다. - 정의역 원소가 서로 다를 때 그에 대응하는 결과도 서로 다르므로 단사함수입니다. - 공변역의 모든 원소 y가 f(x) = y를 만족하는 정의역 원소 x를 갖으므로, 전사함수이기도 합니다. - 단사함수이기도 하고, 전사함수이기도 하므로 항등함수는 전단사함수입니다. 항등함수와 다른 함수와의 합성은 다음과 같이 정리할 수 있습니다. ■ 역함수(Inverse Function) 전단사함수 f: A → B에 대해 B → .. 2020. 8. 8.

[이산수학]합성함수의 연산과 성질 ■ 합성함수의 연산 예제 두 함수에 대한 합성함수는 교환법칙이 성립하지 않습니다. 예제 두 함수 f:R → R, g:R → R에 대해 f(x) = x^3 + 2x, f(x) = x - 5일 때, 다음을 구하여라 (1) g ∘ f (2) f ∘ g 풀이 (1) g ∘ f = g(f(x)) = g(x^3 + 2x) = x^3+2x-5 (2) f ∘ g = f(g(x)) = f(x-5) = (x-5)^3 + 2(x-5) = x^3 -15x^2+77x-135 ■ 합성함수의 성질의 특징 집합 A,B,C가 있고, f: A →B, g: B→C에 대해 g ∘ f가 함성함수일 경우, (1) f와 g가 단사함수면 g ∘ f도 단사함수입니다. (1) f와 g가 전사함수면 g ∘ f도 전사함수입니다. (1) f와 g가 전단사.. 2020. 8. 8.

[이산수학]합성함수란? _개념 익히고 정의역, 공변역 구하기 ■ 합성함수란? (Composition Function) 두 함수를 합성한 함수 g º f = (g º f)(x) = g(f(x)), ∀x ∈ A 두 함수 f: A → B와 g:B → C가 있을 때, 집합 A의 각 원소를 집합 C의 원소에 대응하는 새로운 함수 합성함수는 표기를 주의해야 합니다. g º f라면 x를 함수 f에서 먼저 처리하고 그 결과를 함수 g에서 처리하여 결과를 얻습니다. 예제/풀이 ■ 합성함수의 정의역, 공변역 구하기 예제/풀이 (위 예제와 이어짐) 수학으로 이해하는 디지털 논리 이산수학 272p ----------------------------------- 이산수학 총정리 목록 보러가기 ----------------------------------- 2020. 8. 8.