5. Math
TL;DR
이 글은 2025년도 봄학기 KAIST 전산학부 대학원 면접을 준비하며, 면접 참고자료(이산수학, 확률, 통계)에 대한 대답을 정리한 글입니다.
문제에 대한 정답이 아니며, 제가 공부하며 생각한 바들을 정리한 것입니다.
후에 같은 목표로 면접을 준비하는 학우분들께 도움이 되기를 바랍니다.
이 풀이노트는 질문만 본 상태에서 답변한 내용에 대한 채점, 그리고 이 면접을 준비하며 이전에 한번 LLM과 함께 작성해본 답안이 이어져 있습니다.
문제
Program Verification
Loop Invariant란 무엇인가?
루프 불변성이란 반복문이 실행되는 동안 변하지 않는 조건들을 의미합니다.
루프 불변식(Loop Invariant)은 반복문이 실행되는 동안 항상 참인 조건을 의미합니다. 알고리즘을 증명하기 위해 사용되며, 반복문이 시작되기 전, 반복문이 실행되는 동안, 반복문이 종료된 후에도 항상 참이어야 합니다.
Partial correctness와 Total correctness의 차이는 무엇인가?
Partial correctness는 호어 논리에서 주어진 프로그램이 조건에 맞는 입력이 들어가고 정상적으로 종료할 때 조건에 맞는 출력이 나오는 것을 의미합니다. Total correctness는 이에 더해 프로그램이 항상 정상적으로 종료해야 합니다.
https://ko.wikipedia.org/wiki/%ED%98%B8%EC%96%B4_%EB%85%BC%EB%A6%AC 부분적 정확성(Partial Correctness)은 프로그램이 주어진 입력에 대해 올바른 출력을 생성하는 것을 의미합니다. 즉, 프로그램이 종료되면 올바른 결과를 반환해야 합니다. 전체적 정확성(Total Correctness)은 프로그램이 주어진 입력에 대해 올바른 출력을 생성하고, 프로그램이 반드시 종료되어야 한다는 것을 의미합니다.
Precondition과 Postcondition은 무엇인가?
호어 논리에선 correctness를 정의할 때 이용하는 것으로 알고 있습니다. Precondition에서 프로그램을 실행하면 Postcondition이 되는지 검증하곤 합니다.
전제 조건(Precondition)은 함수나 알고리즘이 실행되기 전에 만족해야 하는 조건을 의미합니다. 즉, 함수나 알고리즘이 올바르게 동작 하기 위해 필요한 입력 조건입니다. 후조건(Postcondition)은 함수나 알고리즘이 실행된 후에 만족해야 하는 조건을 의미합니다. 즉, 함수나 알고리즘이 올바르게 동작한 후 반환해야 하는 결과 조건입니다.
Relation
Relation의 정의는?
Relation은 두 집합의 원소의 순서쌍으로 정의됩니다. 정확히는 집합 A의 원소와 집합 B의 원소의 순서쌍 집합이 relation 입니다.
두 집합 A, B가 있을 때, A와 B의 관계를 정의하는 것을 의미합니다. 관계는 A의 원소와 B의 원소를 연결하는 순서쌍의 집합으로 표현됩니다.
∀a ∈ A, ∀b ∈ B 일 때 aRb <-> (a, b) ∈ R 이 뭔 뜻인지 설명하시오. 여기서 왼쪽 R와 오른쪽의 R이 같은 것인가, 다른 것인가? 다르다면 어떻게 다른가?
두 집합 A, B 간의 관계 R을 정의한 것입니다. 두 R은 동일합니다.
∀a ∈ A, ∀b ∈ B 일 때 aRb는 A의 모든 원소 a와 B의 모든 원소 b에 대해 a와 b 사이에 관계 R이 성립한다는 것을 의미합니다. 즉, A의 모든 원소와 B의 모든 원소 사이에 관계 R이 존재한다는 것입니다. (a, b) ∈ R는 순서쌍 (a, b)가 관계 R에 속한다는 것을 의미합니다 왼쪽의 R과 오른쪽의 R은 같은 관계를 나타냅니다. 즉, 왼쪽의 R은 A와 B 사이의 관계를 나타내고 오른쪽의 R은 A와 B의 원소들 사이의 관계를 나타냅니다.
Equivalence relation이란?
다음과 같은 조건을 만족하는 relation을 의미합니다. reflexitiy, stmmertry, transivity
집합 S가 있을 때, S의 binary relation R이 다음 세 가지 성질을 만족할 때, R은 S의 동치 관계(Equivalence Relation)라고 합니다:
- 반사성(Reflexivity): 모든 원소 a ∈ S 에 대해 aRa가 성립해야 합니다.
- 대칭성(Symmetry): 모든 원소 a, b ∈ S에 대해 aRb가 성립하면 bRa도 성립해야 합니다.
- 추이성(Transitivity): 모든 원소 a, b, c ∈ S에 대해 aRb와 bRc가 성립하면 aRc도 성립해야 합니다.
Partial order relation이란? Total order relation이란?
Partial order relation은 reflextiy, antisymmetricity, transivity를 만족해야 합니다. Total order relationd은 여기서 추가로 임의의 원소 쌍에 대해서도 relation이 정의되어야 합니다.
부분 순서 관계(Partial Order Relation)는 집합 S의 원소들 사이에 정의 된 관계로, 다음 세 가지 성질을 만족합니다:
- 반사성(Reflexivity): 모든 원소 a ∈ S 에 대해 aRa가 성립해야 합니다.
- 반대칭성(Antisymmetry): 모든 원소 a, b ∈ S에 대해 aRb와 bRa가 성립하면 a = b가 되어야 합니다.
- 추이성(Transitivity): 모든 원소 a, b, c ∈ S에 대해 aRb와 bRc가 성립하면 aRc도 성립해야 합니다.
전체 순서 관계(Total Order Relation)는 부분 순서 관계의 특수한 경우로, 집합 S의 모든 원소들 사이에 정의된 관계로, 다음 세 가지 성질을 만족합니다:
- 반사성(Reflexivity): 모든 원소 a ∈ S 에 대해 aRa가 성립해야 합니다.
- 반대칭성(Antisymmetry): 모든 원소 a, b ∈ S에 대해 aRb와 bRa가 성립하면 a = b가 되어야 합니다.
- 추이성(Transitivity): 모든 원소 a, b, c ∈ S에 대해 aRb와 bRc가 성립하면 aRc도 성립해야 합니다.
- 비교 가능성(Comparability): 모든 원소 a, b ∈ S에 대해 aRb 또는 bRa가 성립해야 합니다. 즉, 전체 순서 관계는 집합 S의 모든 원소들 사이에 비교 가능성이 있어야 합니다
Function
Bijection의 정의는?
전단사 함수는 두가지 조건을 만족해야 합니다. 먼저 전사함수로서 공역과 치역이 같아야 합니다. 그리고 단사함수로서 모든 정의역에 대해 서로 다른 인수에 대해 함숫값이 달라야 합니다.
전단사(Bijection)는 두 집합 A와 B 사이의 관계로, 다음 두 가지 조건을 만족하는 함수입니다:
- 전사(Surjective): A의 모든 원소가 B의 원소에 대응되어야 합니다. 즉, B의 모든 원소가 A의 원소에 의해 매핑되어야 합니다.
- 단사(Injective): A의 서로 다른 원소가 B의 서로 다른 원소에 대응되어야 합니다. 즉, A의 서로 다른 원소가 B의 서로 다른 원소에 매핑되어야 합니다. 즉, 정의역과 공역의 원소가 일대일 대응 관계를 이루는 함수입니다.
Bijective function은 반드시 total function인가?
네 맞습니다. 단사함수의 정의에 total function의 정의가 포함되어 있기 때문입니다.
먼저 total function의 정의를 살펴보면, total function은 정의역의 모든 원소가 공역의 원소에 대응되는 함수입니다. 즉, 정의역의 모든 원소가 공역의 원소에 매핑되어 있어야 합니다. 따라서, 전단사(Bijection)는 정의역의 모든 원소가 공역의 원소에 대응되므로, 전단사 함수는 반드시 전체 함수(Total Function)입니다.
Partial function과 total function의 정의를 말하고 그 예를 드시오.
Partial function은 정의역에 대응되는 함숫값이 전부 있지 않은 함수입니다. Total function은 모든 입력에 대응되는 함숫값이 있는 함수입니다. 예를들어 나눗셈은 partial funtion입니다. 덧셈은 total functio입니다.
부분 함수(Partial Function)는 정의역의 일부 원소만이 공역의 원소에 대응되는 함수입니다. 즉, 정의역의 모든 원소가 공역의 원소에 매핑되지 않을 수 있습니다. 예를 들어, f(x) = 1/x는 x가 0이 아닐 때 정의되는 부분 함수입니다. x = 0일 때는 정의되지 않으므로 부분 함수입니다. 전체 함수(Total Function)는 정의역의 모든 원소가 공역의 원소에 대응되는 함수입니다. 즉, 정의역의 모든 원소가 공역의 원소에 매핑되어 있어야 합니다. 예를 들어, f(x) = x + 1은 모든 실수 x에 대해 정의되므로 전체 함수입니다.
Mathematical Induction
Mathematical induction이란?
수학적 귀납법이란 초기 조건을 두고, 재귀적인 조건을 증명하여 명제가 성립함을 보이는 증명방법입니다. 보통 n=k일 때 참이라면 k+1에서도 성립함을 보입니다.
수학적 귀납법(Mathematical Induction)은 자연수에 대한 명제를 증명하는 방법입니다. 수학적 귀납법은 두 단계로 이루어집니다:
- 기초 단계(Base Case): 명제가 n = 1일 때 참임을 증명합니다.
- 귀납 단계(Inductive Step): 명제가 n = k일 때 참이라고 가정하고, 명제가 n = k + 1일 때도 참임을 증명합니다. 이 두 단계를 통해 명제가 모든 자연수에 대해 참임을 증명할 수 있습니다.
Mathematical induction의 한 종류로서 Strong induction은 무엇인가?
강한 수학적 귀납법은 n=1 ~ k가 성립할 때 n=k+1 에서도 귀납 조건이 성립함을 보입니다.
강한 귀납법(Strong Induction)은 수학적 귀납법의 변형으로, 명제가 n = k일 때 참이라고 가정하고, 명제가 n = k + 1일 때도 참임을 증명하는 방법입니다. 강한 귀납법은 기초 단계에서 n = 1부터 n = k까지의 모든 경우에 대해 명제가 참임을 증명합니다. 즉, 강한 귀납법은 n = k일 때 참이라고 가정하는 대신, n = 1부터 n = k까지의 모든 경우에 대해 참이라고 가정합니다. 이 방법은 명제가 더 복잡한 구조를 가질 때 유용합니다.
Recursive Definition
Structural induction이란?
구조적 귀납법은 자료구조를 정의할 때 수학적 귀납법처럼 기본조건과 귀납조건으로 정의하는것을 의미합니다. 리스트, 트리 등을 정의할 때 이용합니다.
구조적 귀납법(Structural Induction)은 수학적 귀납법의 변형으로, 재귀적으로 정의된 구조에 대한 명제를 증명하는 방법입니다. 구조적 귀납법은 다음 두 단계로 이루어집니다:
- 기초 단계(Base Case): 구조의 가장 간단한 경우(예: 빈 리스트, 단일 노드 등)에 대해 명제가 참임을 증명합니다.
- 귀납 단계(Inductive Step): 구조가 더 복잡한 경우(예: 리스트의 길이가 k + 1인 경우 등)에 대해 명제가 참이라고 가정하고, 구조가 k + 1인 경우에도 명제가 참임을 증명합니다. 이 두 단계를 통해 명제가 재귀적으로 정의된 구조에 대해 참임을 증명할 수 있습니다. 예를 들어, 이진 트리의 노드 수에 대한 명제를 증명할 때 구조적 귀납법을 사용할 수 있습니다.
Binary tree의 recursive 정의를 제시하시오.
먼저, 빈 트리는 이진 트리입니다. 재귀조건은 각 노드의 자식 노드는 최대 2개입니다.
이진 트리(Binary Tree)는 다음과 같이 재귀적으로 정의할 수 있습니다:
- 기초 단계(Base Case): 빈 트리는 이진 트리입니다.
- 귀납 단계(Inductive Step): 만약 T1과 T2가 이진 트리라면, T1의 루트 노드와 T2의 루트 노드를 연결하여 새로운 이진 트리 T를 만들 수 있습니다. 이때 T의 왼쪽 서브트리는 T1이고, 오른쪽 서브트리는 T2입니다
Counting
f: A->B 함수이며, |A| =n 이고 |B| =m일때, 몇개의 onto function 을 정의 할 수 있는가? Inclusion-Exclusion 원리를 이용해 공역의 모든 원소가 정의역에 대응되는 경우의 수를 계산하면, 𝑚𝑛 − 𝑚𝐶1 (𝑚 − 1)𝑛 + 𝑚𝐶2 (𝑚 − 2)𝑛 −… = 𝑘=0𝑚∑ 𝑚𝐶𝑘 (− 1)𝑘(𝑚 − 𝑘)𝑛
전사함수는 공역과 치역이 같아야 하기 때문에 B의 원소를 전부 사용해야 합니다. 포함배제 원리를 이용하면 m개의 인수를 임의의 n개 함수값에 매칭하면 m^n 여기서 1개의 함수값이 선택되지 않는 경우를 빼면 m^n - mC1 * m^(n-1) + .. 이런식으로 계산할 수 있습니다.
Discrete Probability
Random variable이 무엇인가?
확률변수란 확률공간에서 사건을 적절한 변수로 변환한 것입니다. 확률변수가 되지 위해선 중복된 사건이 매핑되면 안되고, 모든 사건을 커버해야 합니다.
확률 변수(Random Variable)는 확률 공간에서 정의된 함수로, 실수 값을 가지는 변수입니다.
Sample space란 무엇인가?
표본공간은 사건의 집합입니다.
표본 공간(Sample Space)은 확률 실험에서 가능한 모든 결과의 집합을 의미합니다. 즉, 확률 실험에서 발생할 수 있는 모든 결과를 포함하는 집합입니다. 예를 들어, 동전을 던지는 실험의 표본 공간은 {앞면, 뒷면}입니다.
Sample space가 갖는 조건이 무엇인가?
표본 공간은 모든 사건을 구분할 수 있어야 하고, 모든 사건이 포함되어 있어야 합니다. 그리고 충분히 세분화되어야 합니다.
표본 공간은 다음과 같은 조건을 만족해야 합니다:
- 상호 배타성(Mutually Exclusive): 표본 공간의 원소들은 서로 겹치지 않아야 합니다. 즉, 표본 공간의 두 원소가 동시에 발생할 수 없어야 합니다.
- collectively exhaustive: 표본 공간의 원소들은 모든 가능한 결과를 포함해야 합니다. 즉, 표본 공간의 모든 원소를 합치면 전체 확률 공간을 구성해야 합니다.
- right granularity: 표본 공간의 원소들은 충분히 세분화되어야 합니다. 즉, 표본 공간의 원소들이 너무 크거나 모호하지 않아야 합니다.
Exponential distribution이 무엇인가?
지수분포는 lambda * exp(-lambda) 꼴의 확률밀도함수를 가지는 연속확률분포입니다. 푸아송 분포에서 k값을 1로 두고 적분하여 얻을 수 있습니다.
지수 확률 분포는 푸아송 분포와 관련된 연속 확률 분포입니다. 푸아송 분포가 어떤 사건이 단위 시간 동안 k번 발생할 확률을 나타낸다면, 지수 분포는 처음으로 사건이 발생하는 시간 분포를 나타냅니다.
Poisson distribution이 무엇인가?
푸아송 분포는 단위 시간에 어떤 사건이 k번 일어날 확률에 대한 이산확률분포입니다.
포아송 확률 분포는 단위 시간 동안 어떤 사건이 k번 발생할 확률을 나타내는 이산 확률 분포입니다. 포아송 분포는 사건이 독립적으로 발생하고, 사건의 발생률이 일정할 때 사용됩니다. 즉, 단위 시간 동안 사건이 발생하는 횟수를 모델링하는 데 사용됩니다. 포아송 분포는 λ(람다)라는 매개념을 사용하여, λ는 단위 시간 동안 사건이 발생하는 평균 횟수를 나타냅니다.
Graph, Trees
Dijkstra의 Shortest path algorithm의 전제조건은?
두가지 조건이 있습니다. 먼저 그래프가 모두 연결되어 있어야 하고, 모든 그래프의 가중치가 0 이상이여야 합니다.
다익스트라 알고리즘은 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘입니다. 이 알고리즘의 전제 조건은 다음과 같습니다:
- 비음수 가중치: 그래프의 모든 간선의 가중치가 음수가 아니어야 합니다. 즉, 모든 간선의 가중치는 0 이상이어야 합니다.
- 연결 그래프: 그래프가 연결되어 있어야 합니다. 즉, 그래프의 모든 정점이 서로 연결되어 있어야 합니다.
- 시작 정점: 알고리즘은 시작 정점에서부터 최단 경로를 계산합니다. 따라서 시작 정점이 정의되어 있어야 합니다.
MST가 의미하는 것은?
MST는 그래프에서 간선을 선택하여 그 가중치의 합이 최소가 되는 트리를 만드는 문제입니다. 즉 모든 정점을 최소한의 비용으로 연결할 때 비용을 찾을 수 있습니다.
최소 신장 트리(Minimum Spanning Tree, MST)는 가중치가 있는 그래프에서 모든 정점을 포함하면서, 간선의 가중치 합이 최소가 되는 트리를 의미합니다. 즉, 그래프의 모든 정점을 연결하면서, 간선의 가중치 합이 최소가 되는 트리를 찾는 것입니다.
대표적인 알고리즘으로는 Kruskal’s algorithm과 Prim’s algorithm이 있습니다. Kruskal’s algorithm은 간선을 가중치 순으로 정렬한 후, 사이 클을 형성하지 않도록 간선을 선택하여 MST를 구성합니다. Prim’s algorithm은 시작 정점에서부터 인접한 간선 중 가중치가 가장 작은 간선을 선택하여 MST를 구성합니다. 간선이 많은 경우 Prim’s algorithm이 더 효율적이고, 간선이 적은 경우 Kruskal’s algorithm이 더 효율적입니다. 왜냐하면, Prim’s algorithm은 인접한 간선을 선택하기 때문에 간선이 많을 때 더 빠르게 동작하고, Kruskal’s algorithm은 간선을 정렬하는 과정이 필요하기 때문에 간선이 적을 때 더 빠르게 동작합니다.