Index

Posts

164 published posts · Page 5 of 28

06. 알고리즘, 함수의 증가, 알고리즘의 복잡도

discrete_mathematics

알고리즘을 이해하려면 무엇을 계산하는지뿐 아니라 왜 맞는지, 입력이 커질 때 얼마나 많은 일을 하는지도 봐야 한다. 검색과 정렬을 직접 따라가고, 반복 횟수를 함수로 표현하면 빅오 표기법이 무엇을 설명하는지 분명해진다. 특히 알고리즘 하나가 느리다는 사실과 문제 자체가 어렵다는 주장은 구별해야 한다.

05. 함수, 수열과 합, 행렬

discrete_mathematics

수열은 정수 인덱스를 입력으로 받는 함수이고, 행렬은 수를 행과 열에 맞춰 배열한 구조다. 바닥·천장 함수로 정수 단위의 자원을 계산하고, 점화식으로 반복되는 변화를 표현하고, 행렬로 여러 관계와 방정식을 한꺼번에 다룰 수 있다. 정의를 실제 계산에 적용하면서 각 구조의 성질을 살펴보자.

04. 집합과 집합의 연산, 함수의 기초

discrete_mathematics

집합은 어떤 대상이 포함되는지를, 함수는 한 대상이 다른 대상으로 어떻게 대응되는지를 표현한다. 원소와 부분집합, 공역과 치역처럼 비슷해 보이는 말을 구별해야 이후의 계산과 증명도 정확해진다. 집합 연산을 논리식으로 풀어 보고, 함수의 성질을 정의역과 공역까지 포함해 판단해 보자.

03. 추론 규칙과 증명 방법

discrete_mathematics

수학적 증명은 그럴듯한 예를 많이 모으는 일이 아니라, 주어진 가정에서 결론이 반드시 따라온다는 것을 보이는 과정이다. 추론 규칙은 그 과정의 작은 단위이고, 직접증명·대우증명·귀류법은 여러 단계를 구성하는 방법이다. 어떤 조건을 가정했는지, 그 조건을 어디에서 사용했는지 드러내며 쓰는 것이 중요하다.