Chapter 01 기본 개념 1.1 이산 수학(Discrete Mathematics) ... 2 객관식 연습 문제 ... 3 주관식 연습 문제 ... 3 1.2 이산수학 교육 내용 ... 3 1.3 이산수학의 전형적인 문제 ... 6 주관식 연습문제 ... 10 1.4 정수의 성질 ... 10 객관식 연습 문제 ... 14 주관식 연습 문제 ... 15 1.5 행렬(Matrix) ... 15 객관식 연습 문제 ... 28 주관식 연습 문제 ... 31 프로그래밍 문제 ... 33 프로그램 문제 풀이 ... 33 Chapter 02 수학적 모델과 논리 2.1 수학적 모델 ... 40 객관식 연습 문제 ... 41 주관식 연습 문제 ... 42 2.2 논리적 추론 ... 42 객관식 연습 문제 ... 62 주관식 연습 문제 ... 64 프로그래밍 문제 ... 67 프로그램 문제 풀이 ... 67 2.3 수학적 귀납법 ... 73 객관식 연습 문제 ... 76 주관식 연습 문제 ... 76 2.4 응용 : 지식 베이스 시스템 ... 77 주관식 연습 문제 ... 79 Chapter 03 집합 3.1 집합의 개념 ... 82 객관식 연습 문제 ... 87 주관식 연습 문제 ... 88 프로그래밍 문제 ... 90 프로그램 문제 풀이 ... 90 3.2 집합의 연산 ... 93 객관식 연습 문제 ... 96 주관식 연습 문제 ... 97 프로그래밍 문제 ... 98 프로그램 문제 풀이 ... 99 3.3 집합의 대수적 성질 ... 102 객관식 연습 문제 ... 106 주관식 연습 문제 ... 107 Chapter 04 관계(Relation) 4.1 곱집합(Product Set ; Cartesian Product) ... 110 객관식 연습 문제 ... 113 주관식 연습 문제 ... 113 4.2 관계와 관계 그래프 ... 114 객관식 연습 문제 ... 121 주관식 연습 문제 ... 121 4.3 경로(Path) ... 123 객관식 연습 문제 ... 127 주관식 연습 문제 ... 128 프로그래밍 문제 ... 129 프로그램 문제 풀이 ... 129 4.4 관계의 성질 ... 130 객관식 연습 문제 ... 140 주관식 연습 문제 ... 141 프로그래밍 문제 ... 144 프로그램 문제 풀이 ... 144 4.5 역관계와 합성 관계 ... 147 객관식 연습 문제 ... 155 주관식 연습 문제 ... 156 4.6 접속 관계와 Warshall의 정리 ... 159 객관식 연습 문제 ... 167 주관식 연습 문제 ... 167 프로그래밍 문제 ... 168 프로그램 문제 풀이 ... 168 Chapter 05 함수(Function) 5.1 함수(Function)의 정의 ... 174 객관식 연습 문제 ... 176 프로그래밍 문제 ... 176 프로그램 문제 풀이 ... 176 5.2 단사 함수, 전사 함수, 전단사 함수 ... 178 객관식 연습 문제 ... 180 주관식 연습 문제 ... 181 5.3 역함수와 합성 함수 ... 182 객관식 연습 문제 ... 184 주관식 연습 문제 ... 185 5.4 특수 함수 ... 185 객관식 연습 문제 ... 190 주관식 연습 문제 ... 190 프로그래밍 문제 ... 190 프로그램 문제 풀이 ... 190 5.5 순열(Permutation) ... 192 객관식 연습 문제 ... 196 주관식 연습 문제 ... 196 Chapter 06 반순서 관계와 부울 대수 6.1 반순서 관계 ... 200 객관식 연습 문제 ... 206 주관식 연습 문제 ... 207 6.2 반순서 집합의 상한과 하한 ... 209 객관식 연습 문제 ... 213 주관식 연습 문제 ... 215 6.3 격자 ... 217 객관식 연습 문제 ... 221 주관식 연습 문제 ... 222 6.4 특별한 형태의 격자 ... 223 객관식 연습 문제 ... 226 주관식 연습 문제 ... 227 6.5 부울 대수와 스위칭 대수 ... 228 객관식 연습 문제 ... 240 주관식 연습 문제 ... 240 6.6 응용 : 2비트 가산기 설계 ... 241 주관식 연습 문제 ... 244 Chapter 07 그래프 이론 7.1 그래프(Graph) ... 247 객관식 연습 문제 ... 254 주관식 연습 문제 ... 254 프로그래밍 문제 ... 255 프로그램 문제 풀이 ... 256 7.2 여러 가지 그래프 ... 258 객관식 연습 문제 ... 269 주관식 연습 문제 ... 270 7.3 평면 그래프(Planar Graph) ... 272 객관실 연습 문제 ... 277 주관식 연습 문제 ... 278 프로그래밍 문제 ... 278 프로그램 문제 풀이 ... 279 7.4 정점의 착색(Vertex Coloring) ... 280 주관식 연습 문제 ... 282 프로그래밍 문제 ... 283 프로그램 문제 풀이 ... 283 7.5 응용 : 전산망의 경로 배정 ... 286 주관식 연습 문제 ... 290 Chapter 08 트리(Tree) 8.1 트리(Tree) ... 292 객관식 연습 문제 ... 296 주관식 연습 문제 ... 296 8.2 레이블을 갖는 트리와 최소 스패닝 트리 ... 297 주관식 연습 문제 ... 303 프로그래밍 문제 ... 303 프로그램 문제 풀이 ... 303 8.3 탐색 트리와 트리 운행 알고리즘 ... 307 객관식 연습 문제 ... 309 주관식 연습 문제 ... 310 프로그래밍 문제 ... 311 프로그램 문제 풀이 ... 311 Chapter 09 컴비네토릭스와 확률 9.1 세기(Counting)의 기본 원리 ... 316 9.2 순열과 조합 ... 318 객관식 연습 문제 ... 323 주관식 연습 문제 ... 323 9.3 이항 정리와 다항 정리 ... 324 주관식 연습문제 ... 328 9.4 확률의 기초 및 조건부 확률 ... 328 주관식 연습문제 ... 338 Chapter 10 점화 관계(Recurrence Relations)와 알고리즘 10.1 점화 관계 ... 344 주관식 연습 문제 ... 348 10.2 알고리즘과 의사코드 ... 348 주관식 연습 문제 ... 353 10.3 알고리즘의 난이도 ... 355 주관식 연습문제 ... 360 10.4 여러 가지 알고리즘 ... 361 10.4.1 이차 방정식의 해를 구하는 알고리즘 ... 361 10.4.4 유클리드 알고리즘 : 최대공약수 구하기 ... 364 10.4.5 재귀적 알고리즘 ... 368 객관식 연습 문제 ... 372 주관식 연습 문제 ... 372 프로그래밍 문제 ... 373 프로그램 문제 풀이 ... 373 Chapter 11 형식 언어와 형식 시스템 11.1 형식 언어(Formal Language) ... 382 객관식 연습 문제 ... 387 11.2 문법과 의미 ... 387 객관식 연습 문제 ... 395 주관식 연습 문제 ... 396 ll.3 문법의 표기법 ... 397 객관식 연습 문제 ... 402 주관식 연습 문제 ... 403 11.4 정규 표현과 유한 오토마타 ... 403 객관식 연습 문제 ... 412 주관식 연습 문제 ... 412 프로그래밍 문제 ... 414 프로그램 문제 풀이 ... 414 11.5 응용 : 문제 풀기 ... 416 주관식 연습 문제 ... 417 프로그래밍 문제 ... 418 프로그램 문제 풀이 ... 418 Chapter 12 군과 정보의 전송 12.1 반군과 군 ... 428 주관식 연습 문제 ... 433 12.2 군의 곱과 몫 ... 435 주관식 연습 문제 ... 438 12.3 2진 정보의 전송 ... 438 주관식 연습 문제 ... 443 프로그래밍 문제 ... 444 프로그램 문제 풀이 ... 444 부록 A 이진 수학에서 사용되는 개념들의 표기법 ... 447 찾아보기 ... 453