홈 > 강의소개
이산수학
이명숙 교수
연세대학교 대학원 수학과 석사과정
연세대학교 대학원 수학과 박사졸업
연세대학교 대학원 수학과 석사과정
연세대학교 대학원 수학과 박사졸업
연세대학교
현) 유니와이즈 전임교수
AI가 이끄는 스마트한 학습 경험, AI 튜터와 함께 더 빠르고, 더 깊게 학습하세요.
긴 강의 내용을 AI가 핵심만 요약하여 복습 시간을 단축시킵니다.
강의에서 가장 중요한 키워드와 개념을 자동으로 추출해 제공합니다.
학습한 내용을 바탕으로 AI가 생성한 퀴즈를 풀며 이해도를 점검합니다.
모르는 부분을 24시간 언제든 AI 튜터에게 질문하고 답변을 받습니다.
총 0개 챕터, 9강으로 구성되어 있습니다.
| 제목 | 강의시간 | 상세내용 |
|---|---|---|
|
[1강] 선택과 배열 (1)
|
1:
23:
12
|
|
|
이산수학 선택과 배열(1): 합·곱의 법칙, 순열·조합, 중복조합 핵심 정리
• 경우의 수 기본 원리: 이산집합과 경우의 수 개념, 합의 법칙·곱의 법칙을 통한 복합 사건 계산 구조 정리 • 순열·조합·중복조합: 순열·같은 것 포함 순열·중복순열·원순열·염주순열, 조합과 파스칼 항등식·부분집합 수, 중복조합과 $nH_r$ 공식 체계화 • 조합론 응용 모델: 도로망 최단경로, 함수 개수, 물건 나누기 함수 f(n,m), 방정식·부등식 정수해 계산 등으로 대표적 문제 유형 구조화 |
||
|
[2강] 선택과 배열 (2)
|
1:
19:
12
|
|
|
Summary Content: 이항정리·다항정리, 자연수·집합의 분할, 포함배제, 비둘기집 원리 핵심 정리 요약
• 이항정리·다항정리·항등식: 이항·다항계수 정의와 전개공식, 반데르몽 항등식, 계수합·가중합·중복조합을 이용한 항 개수·계수 계산 구조 정리 • 자연수·집합 분할과 분할수: 자연수 분할·분할수 p(n), 점화식 p(n,r)=p(n-1,r-1)+p(n-r,r), 분할–선형 방정식 해 대응, 집합 분할·다항계수 기반 분배 공식 체계화 • 포함배제·전사함수·교란순열·비둘기집: 포함배제 일반식과 서로소 개수·전사함수·교란순열 공식, 비둘기집 원리와 일반화·평균 원리를 통한 최소·최대 보장형 조합론 문제 해결 원리 정리 |
||
|
[3강] 점화관계식과 알고리즘 (1)
|
1:
15:
55
|
|
|
점화식과 알고리즘: 점화관계, 풀이, 응용 정리
• 점화식 개념·기본 수열: 점화식·초기조건 정의, 등차·등비수열, 조합적 점화(01·02 패턴, 계단 오르기·직선 영역·하노이 탑·“111 금지” 등), 피보나치 수열과 합·제곱합 등 핵심 성질 • 선형 점화식 이론: k차 선형 동차 점화식과 특성다항식, 서로 다른 근·중근에 따른 일반해 구조, 선형 비동차 점화식의 동차해+특수해 원리와 상수·다항식·지수형 비동차항에 따른 특수해 선택 및 보정 규칙 • 응용·심화 알고리즘: 수열 극한·부분합 계산, 표·배열·계차수열을 통한 일반항 도출, 이진수 표현과 트리 공통 경로, 거듭제곱 나머지의 순환 패턴 등 기출·조합·수론 상황에 점화식 모델링·해결 전략 적용 |
||
|
[4강] 점화관계식과 알고리즘 (2)
|
1:
06:
17
|
|
|
생성함수, 알고리즘, 정렬·탐색, 복잡도 핵심 정리
• 생성함수·지수생성함수: 수열을 형식적(지수)생성함수로 대응해 합·시프트·곱·부분합 규칙, 계차·다항수열 생성함수, 제한된 정수해·분배·중복배열 계산에 적용하는 기법 정리 • 알고리즘과 정렬·탐색: 알고리즘·순서도 개념과 에라토스테네스의 체·소수 판정 절차, 버블·선택·병합정렬의 동작 구조와 성능, 선형탐색·이진탐색·이진탐색트리의 탐색 원리와 활용 조건 비교 • 알고리즘 복잡도와 Big-O: 시간·공간 복잡도 정의, Big-O 수학적 정의와 다항식·로그·계승 함수의 점근적 비교, 선형탐색 평균 비교 횟수 도출과 O(n) 복잡도 분석 정리 |
||
|
[5강] 그래프와 그래프의 활용 (1)
|
1:
06:
43
|
|
|
그래프 이론 기본 개념과 오일러·해밀턴·평면그래프 정리 요약
• 그래프 구조와 유형: 꼭짓점·변·차수·인접성, 단순·다중·유향·비유향그래프, 동형그래프·부분그래프·완전그래프·이분·완전이분그래프의 정의 및 차수 합 정리·홀수 차수 정점 성질 정리 • 평면그래프와 오일러 이론: 평면그래프·면·면의 차수·오일러 공식(v−e+f=2)과 e≤3v−6, e≤2v−4, 차수 ≤5 정점 존재 정리, K₅·K₃,₃ 비평면성, 부분분할그래프와 쿠라토프스키 정리에 의한 평면성/비평면성 판정 구조 제시 • 경로·회로와 가중그래프 응용: 경로·회로·연결그래프·오일러 경로·오일러 회로·해밀턴 회로 정의와 오일러 경로/회로 필요충분조건·해밀턴 회로 충분조건, 쾨니히스베르크 다리 문제, 정다면체와 그래프의 관계, 가중그래프에서 최단/최장 경로 및 작업 일정(critical path) 최적화 모델링 정리 |
||
|
[6강] 그래프와 그래프의 활용 (2)
|
1:
22:
43
|
|
|
수형도·생성수형도·채색·인접행렬 핵심 정리 요약
• 수형도·생성수형도·탐색·MST: 수형도 정의(e=v-1·유일경로·변제거 단절 동치), 루트·이진·이진탐색수형도 구조, 생성수형도와 DFS·BFS 탐색, Prim·Kruskal·Greedy 알고리즘을 통한 최소생성수형도 구성, Cayley 공식 n^{n-2}로 라벨드 수형도 개수 계산 • 그래프 채색·채색다항식: 채색수 χ(G)와 평면그래프 사색정리, 완전그래프·완전이분그래프의 채색수 범위, 채색다항식 P_G(k) 정의와 χ(G)와의 관계, 분리합의 곱정리와 삭제-수축 공리 P_G(k)=P_{G-e}(k)-P_{G/e}(k)를 이용한 채색다항식 계산 구조 • 인접행렬·Matrix-Tree 정리·근접행렬: 인접행렬 A(G)의 정의와 A^p의 (i,j) 성분을 통한 길이 p 경로 수 계산, 차수행렬 D·라플라시안 L=D-A(G) 구성과 Matrix-Tree 정리에 따른 생성수형도 수의 여인수(코팩터) 표현, 꼭짓점–변 관계를 나타내는 근접행렬 B(G)의 구조와 단순그래프에서의 제약조건(0–1 성분·열합 2·열 중복 불가) |
||
|
[7강] 게임이론
|
1:
19:
03
|
|
|
이산수학 게임이론·공평분배·선거이론 핵심 정리
• 2인 제로섬 게임·안장점·혼합전략: 성과행렬·최소최대·최대최소전략과 행 최소·열 최대 안장점을 통한 결정게임 판정, 안장점 부재 시 혼합전략·기대성과·게임의 값으로 최선 전략 도출 • 공평한 분배 알고리즘: 케이크 나누기·재산·상속 분할에서 주관적 가치 평가를 이용한 2인·3인 공평분배 절차, 현금 조정·지분 조정 방식을 통한 각자의 최소 공정 몫 이상 보장 구조 • 선거 방식과 공정성 정리: 다수결·과반수·Borda·Hare·상호선호 비교 방식의 절차와 당선자 차이, 공정성 기준(MC·CC·MOC·IIA)과 Arrow의 불가능정리를 통한 집단 의사결정 제도 설계 한계 정리 |
||
|
[8강] 교원임용 기출문제
|
0:
46:
03
|
|
|
이산수학 기출: 조합·중복조합·점화·그래프와 인접행렬 핵심 정리
• 중복조합·부정방정식 해법: 같은 물건 분배, 부정방정식·선형 디오판틴 방정식의 정수해를 중복조합 공식과 변수 치환으로 구조적으로 계산 • 점화식·계차수열 분석: 계차수열·특성방정식·로그 치환을 사용해 수열 점화식의 일반항·극한 및 다항식 형태를 도출하고 수 배열·구슬 배열 규칙을 해석 • 그래프 색칠·인접행렬 거듭제곱: 선형 그래프의 색칠다항식·색수 산출과 인접행렬·그 거듭제곱을 통한 경로 수·도달 가능성 판정으로 그래프 구조를 분석 |
||
|
[9강] 수학능력시험 기출문제
|
1:
08:
23
|
|
|
2005~2009 수능 이산수학 그래프·조합·알고리즘 핵심 정리
• 그래프 이론 핵심 개념: 완전그래프·수형도·생성수형도·채색수·MST·프로젝트 네트워크·평면그래프 분할·인접행렬을 통한 경로/차수 분석 및 생성수형도·최소 작업시간·최소비용 구조 도출 절차 정리 • 조합·분할·배열 모델링: 서로소 부분집합·자연수 분할·사탕 분배·홀수 분할·문자열 배열을 별·막대기·분할/배열 구분·포함배제·영역 분할·조건 치환으로 표준 조합 공식에 연결하는 방법 정리 • 점화식·수열 및 이진 구조: 피보나치형·선형 점화식 일반항·부분합 계산, 세 항 합 일정 수열, 문자열 개수 점화식, 완전 이진수형도와 2진 표현을 이용한 공통 경로/노드(M(a,b)) 분석 절차 정리 |
||
이명숙 교수님
이산수학
