컴퓨터과학을 위한 이산수학 공부 순서: 논리부터 그래프·조합까지

이산수학은 연속적인 값을 다루는 미적분과 달리, 셀 수 있고 구분할 수 있는 구조를 다룬다. 논리, 집합, 조합, 그래프처럼 컴퓨터과학에서 반복해서 만나는 개념이 여기에 속한다.

처음에는 관련 용어를 한꺼번에 나열하기보다 논리와 집합 → 증명과 재귀 → 경우의 수 → 그래프 → 알고리즘 적용 순서로 연결해서 보는 편이 이해하기 쉽다. 흩어져 있던 공부 항목을 이 흐름에 맞춰 다시 정리했다.

이산수학은 왜 컴퓨터과학에 필요할까

프로그램은 결국 참과 거짓을 판단하고, 유한한 데이터를 분류하며, 가능한 경우를 계산하고, 객체 사이의 관계를 탐색한다. 이산수학은 이런 문제를 정확한 기호와 규칙으로 표현하는 도구다.

• 논리와 집합은 조건문, 데이터 분류, 명세를 이해하는 기초가 된다.
• 함수와 관계는 입력과 출력, 데이터 사이의 연결을 설명한다.
• 귀납법과 재귀는 알고리즘이 왜 동작하는지 설명할 때 쓰인다.
• 순열과 조합은 가능한 경우의 수와 탐색 범위를 계산하게 해준다.
• 그래프와 트리는 네트워크, 경로 탐색, 계층 구조의 공통 언어다.

이 관점에서 보면 이산수학은 공식을 외우는 과목이라기보다, 문제를 구조로 바꾸는 연습에 가깝다.

이산수학 공부 순서

단계	핵심 주제	컴퓨터과학과의 연결
1	명제 논리, 진리표, 집합, 함수와 관계	조건식, 데이터 표현, 프로그램 명세
2	증명, 수학적 귀납법, 재귀, 수열	알고리즘 정당성, 재귀 함수, 점화식
3	순열, 조합, 포함·배제, 기초 확률	경우의 수, 탐색 공간, 확률적 판단
4	그래프, 경로, 트리, 연결성	네트워크, DFS·BFS, 최단 경로
5	복잡도와 알고리즘 적용	시간·공간 복잡도, 문제 해결 전략

1. 논리·집합·함수로 표현하는 법부터 익힌다

가장 먼저 명제와 논리 연산을 익힌다. AND, OR, NOT을 진리표로 직접 확인하면 복잡한 조건식이 어떤 경우에 참이 되는지 분해해서 볼 수 있다.

그다음 집합의 합집합, 교집합, 차집합과 함수의 일대일·전사·전단사 관계를 연결한다. 이 단계의 목표는 기호를 많이 외우는 것이 아니라, 문장으로 된 조건을 논리식이나 집합으로 옮길 수 있게 되는 것이다.

진법 변환과 비트 표현도 함께 공부하면 좋다. 이진수와 16진수는 이산수학의 핵심 이론이라기보다, 논리 연산이 실제 컴퓨터 데이터와 만나는 지점에 가깝다.

2. 증명·귀납법·재귀를 한 흐름으로 본다

어떤 명제가 항상 성립한다고 주장하려면 근거가 필요하다. 직접 증명, 대우 증명, 모순 증명과 수학적 귀납법은 그 근거를 만드는 대표적인 방법이다.

귀납법은 재귀와도 자연스럽게 이어진다. 작은 입력에서 성립하는지 확인하고, 한 단계 큰 입력에서도 성립함을 보이는 구조가 재귀 알고리즘을 이해하는 방식과 닮아 있다. 피보나치 수열 같은 점화식을 코드로 옮겨보면 둘의 관계가 더 분명해진다.

3. 순열과 조합으로 탐색 범위를 계산한다

순열은 순서가 중요하고, 조합은 선택 자체가 중요하다. 중복을 허용하는지까지 구분하면 대부분의 경우의 수 문제를 네 가지 틀로 정리할 수 있다.

공식만 외우면 조건이 조금 바뀔 때 흔들리기 쉽다. 작은 예를 직접 나열한 뒤, 순서가 중요한가, 같은 대상을 다시 선택할 수 있는가를 먼저 묻는 편이 안전하다.

관련 글: 순열·조합·중복순열·중복조합의 차이

4. 그래프와 트리로 관계를 모델링한다

그래프는 정점과 간선으로 관계를 표현한다. 방향 유무, 가중치, 연결성에 따라 문제의 성격이 달라지고, DFS와 BFS 같은 탐색 방법을 선택하는 기준도 달라진다.

트리는 사이클이 없는 연결 그래프다. 이진 트리, 탐색 트리, 힙은 모두 트리 구조를 특정 목적에 맞게 제한한 형태로 볼 수 있다. 최소 신장 트리와 최단 경로는 비슷해 보이지만, 모든 정점을 연결하는 비용과 두 지점 사이의 비용이라는 서로 다른 질문에 답한다.

관련 글: 그래프와 DFS·BFS의 출발점, 오일러 그래프는 어떤 경로를 찾는가

5. 알고리즘 문제에 적용하며 확인한다

마지막에는 개념을 알고리즘 문제와 연결한다. 시간 복잡도와 공간 복잡도를 계산하고, 완전 탐색·분할 정복·동적 계획법·그리디 같은 전략이 어떤 구조를 이용하는지 살펴본다.

스택, 큐, 우선순위 큐는 이산수학 자체보다는 자료구조에 가깝다. 행렬은 선형대수, 로그는 대수의 주제다. 다만 그래프 표현, 복잡도 분석, 확률 계산에서 자주 만나므로 필요한 시점에 함께 보완하면 된다. 예전 목차에서는 이 주제들이 한 목록에 섞여 있었는데, 다시 정리해보니 경계를 구분하는 것 자체가 공부의 일부였다.

공부하면서 스스로 확인할 질문

각 단원을 읽은 뒤 다음 질문에 답할 수 있는지 확인하면 단순 암기를 줄일 수 있다.

1. 문장으로 된 조건을 논리식이나 집합으로 표현할 수 있는가?
2. 공식의 결과뿐 아니라 왜 성립하는지 작은 예로 설명할 수 있는가?
3. 순서와 중복 조건을 보고 순열과 조합을 구분할 수 있는가?
4. 현실의 관계를 정점과 간선으로 바꿀 수 있는가?
5. 알고리즘의 실행 횟수를 입력 크기의 함수로 설명할 수 있는가?

이 목차는 완성된 강의계획서가 아니라 컴퓨터과학을 공부하며 계속 보완할 지도다. 새로운 개념을 만났을 때 어느 영역과 연결되는지 표시해두면, 따로 외웠던 내용이 하나의 구조로 묶이기 시작한다.