# [컴퓨터공학을 위한 수학] 1편 - 지수·로그·시그마·팩토리얼 기초

Об этом предложении

[컴퓨터공학을 위한 수학] 1편 - 지수·로그·시그마·팩토리얼 기초 컴퓨터공학을 공부하다 보면 2^n , log N , Σ , N! 같은 표현을 매우 자주 만나게 된다. 이번 글에서는 이러한 수학 표현이 무엇을 의미하는지부터 차근차근 정리한다. 1. 왜 컴퓨터공학에서 수학이 필요한가? 알고리즘을 공부하다 보면 다음과 같은 표현을 자주 보게 된다. O(N) O(N2) O(log N) O(N log N) O(2^N) 처음 보면 단순히 외워야 하는 공식처럼 보인다. 하지만 각각은 결국 입력 데이터가 커졌을 때 계산량이 얼마나 증가하는지 를 수학으로 표현한 것이다. 예를 들어 데이터가 10개 있을 때와 1,000개 있을 때 프로그램이 얼마나 더 많은 계산을 해야 하는지를 나타내는 것이다. 따라서 컴퓨터공학에서 필요한 수학은 단순히 문제를 풀기 위한 수학이라기보다 컴퓨터가 얼마나 많은 일을 하는지를 설명하기 위한 언어 라고 생각하면 된다. 이번 편에서는 그중에서도 가장 많이 등장하는 지수 로그 시그마 팩토리얼 을 알아본다. 2. 지수란? 먼저 다음 표현을 보자. 23 이것은 2 × 2 × 2 라는 뜻이다. 따라서 23 = 8 이다. 여기서 23 에서 2 → 밑(base) 3 → 지수(exponent) 라고 한다. 지수는 쉽게 말하면 같은 숫자를 몇 번 곱하는지 나타내는 표현 이다. 예제 21 = 2 22 = 2 × 2 = 4 23 = 2 × 2 × 2 = 8 24 = 2 × 2 × 2 × 2 = 16 계속하면 25 = 32 26 = 64 27 = 128 28 = 256 29 = 512 210 = 1024 가 된다. 컴퓨터공학에서는 특히 2의 거듭제곱 이 매우 중요하다. 그 이유는 컴퓨터가 기본적으로 0 1 두 가지 상태를 사용하는 이진수(binary) 기반이기 때문이다. 3. 왜 컴퓨터에서는 2의 지수가 많이 등장할까? 비트 하나는 두 가지 값을 가질 수 있다. 0 1 즉, 21 = 2가지 상태가 존재한다. 비트가 2개라면? 00 01 10 11 총 4가지다. 즉, 22 = 4 이다. 비트가 3개라면 000 001 010 011 100 101 110 111 총 8가지다. 따라서 23 = 8 이다. 일반적으로 비트가 N개 라면 표현 가능한 경우의 수는 2^N 이다. 예를 들어 8비트라면 28 = 256 개의 서로 다른 값을 표현할 수 있다. 그래서 컴퓨터공학에서는 2 4 8 16 32 64 128 256 512 1024 같은 숫자를 매우 자주 만나게 된다. 4. 지수 법칙 지수에는 몇 가지 기본적인 법칙이 있다. 같은 밑끼리 곱하기 22 × 23 을 직접 풀어보면 (2 × 2) × (2 × 2 × 2) 이므로 25 가 된다. 따라서 a^m × a^n = a^(m+n) 이다. 예를 들어 23 × 24 = 27 = 128 이다. 같은 밑끼리 나누기 25 ÷ 22 는 2^(5-2) 가 된다. 따라서 a^m ÷ a^n = a^(m-n) 이다. 예를 들어 25 ÷ 22 = 23 = 8 이다. 지수의 지수 (23)2 는 23 × 23 이므로 26 이 된다. 따라서 (a^m)^n = a^(mn) 이다. 5. 0제곱은 왜 1일까? 다음 식을 생각해보자. 23 ÷ 23 같은 숫자를 나누면 1 이다. 하지만 지수 법칙을 적용하면 2^(3-3) = 20 이다. 따라서 20 = 1 이 되어야 한다. 일반적으로 a0 = 1 이다. 단, a ≠ 0 이라는 조건이 필요하다. 6. 음수 지수 다음과 같은 것도 존재한다. 2^-1 음수 지수는 역수를 의미한다. 2^-1 = 1 / 2 그리고 2^-2 = 1 / 22 = 1 / 4 이다. 일반적으로 a^-n = 1 / a^n 이다. 7. 로그란? 로그는 처음 보면 어려워 보이지만 사실 지수의 반대 개념이다. 예를 들어 23 = 8 이라는 것을 알고 있다. 이 질문을 반대로 바꿔보자. 2를 몇 번 곱해야 8이 될까? 정답은 3번 이다. 이것을 로그로 표현하면 log28 = 3 이다. 즉, 23 = 8 과 log28 = 3 은 정확히 같은 내용을 표현하고 있다. 8. 로그를 쉽게 읽는 방법 다음 식이 있다고 하자. log28 = 3 이것은 다음 질문이다. 2를 몇 제곱해야 8이 되는가? 답은 3 이다. 또 다른 예를 보자. log216 은 2를 몇 제곱해야 16이 되는가? 라는 뜻이다. 24 = 16 이므로 log216 = 4 이다. 9. 로그 예제 log22 = 1 왜냐하면 21 = 2 이기 때문이다. log24 = 2 왜냐하면 22 = 4 이기 때문이다. log28 = 3 왜냐하면 23 = 8 이기 때문이다. log216 = 4 왜냐하면 24 = 16 이기 때문이다. log232 = 5 왜냐하면 25 = 32 이기 때문이다. 결국 2 → 1 4 → 2 8 → 3 16 → 4 32 → 5 64 → 6 128 → 7 256 → 8 1024 → 10 처럼 생각하면 된다. 10. 알고리즘에서 log N이 왜 등장할까? 대표적인 예가 이진 탐색(Binary Search) 이다. 1부터 16까지 숫자가 있고 어떤 숫자를 찾는다고 해보자. 처음부터 하나씩 찾으면 최대 16번을 확인해야 한다. 하지만 이진 탐색은 매번 절반을 버린다. 처음 데이터가 16개 있다고 하자. 한 번 비교하면 8개 가 남는다. 다시 비교하면 4개 가 남는다. 다시 비교하면 2개 가 남는다. 마지막으로 1개 가 남는다. 즉, 16 ↓ 8 ↓ 4 ↓ 2 ↓ 1 4번 만에 줄어든다. 그런데 24 = 16 이다. 따라서 log216 = 4 가 된다. 그래서 이진 탐색의 시간복잡도는 O(log N) 이다. 11. log N의 핵심 알고리즘에서 log N 이 등장하면 우선 다음 이미지를 떠올리면 된다. 계속 절반으로 줄어든다. 예를 들어 1024 512 256 128 64 32 16 8 4 2 1 1024가 1이 되기까지 10번 나누었다. 그리고 210 = 1024 이므로 log21024 = 10 이다. 즉 데이터가 무려 1024개 있어도 약 10단계면 된다. 이것이 O(log N) 알고리즘이 매우 빠른 이유다. 12. 시그마 Σ란? 알고리즘을 공부하다 보면 이런 기호를 볼 수 있다. Σ 이것을 시그마(Sigma) 라고 한다. 시그마는 어려운 개념이 아니다. 단순히 여러 숫자를 더하라 라는 뜻이다. 예를 들어 1 + 2 + 3 + 4 + 5 를 시그마로 표현할 수 있다. Σ i 여기서 i 가 1부터 5까지 움직인다고 하면 i = 1 i = 2 i = 3 i = 4 i = 5 를 모두 더한다. 따라서 1 + 2 + 3 + 4 + 5 가 된다. 13. 왜 알고리즘에서 시그마가 등장할까? 다음과 같은 반복문이 있다고 생각해보자. for i in range(1, N + 1): for j in range(i): 실행 바깥 반복문의 i 값이 증가함에 따라 안쪽 반복 횟수도 증가한다. i = 1 → 1번 i = 2 → 2번 i = 3 → 3번 ... i = N → N번 전체 실행 횟수는 1 + 2 + 3 + ... + N 이다. 이것을 시그마로 나타낼 수 있다. 그리고 이 합은 N(N + 1) / 2 라는 공식으로 계산할 수 있다. 14. 1부터 N까지의 합 매우 중요한 공식이다. 1 + 2 + 3 + ... + N 의 합은 N(N + 1) / 2 이다. 예를 들어 1 + 2 + 3 + 4 + 5 라면 N = 5 이므로 5(5 + 1) / 2 즉, 5 × 6 / 2 = 15 이다. 실제로 더해도 1 + 2 + 3 + 4 + 5 = 15 이다. 15. 왜 N(N + 1) / 2가 될까? 다음 숫자가 있다고 하자. 1 2 3 4 5 반대로 하나 더 적어보자. 5 4 3 2 1 두 줄을 같은 위치끼리 더하면 6 6 6 6 6 이 된다. 즉 6이 5개 있다. 따라서 5 × 6 = 30 이다. 하지만 같은 수열을 두 번 사용했으므로 2로 나누어야 한다. 30 / 2 = 15 이를 일반화하면 N × (N + 1) / 2 가 된다. 그래서 1 + 2 + ... + N 은 N(N + 1) / 2 이다. 16. N + (N-1) + ... + 1도 똑같다 알고리즘에서 다음 형태도 많이 등장한다. N + (N - 1) + (N - 2) + ... + 1 순서만 반대일 뿐 1 + 2 + 3 + ... + N 과 완전히 같다. 따라서 합은 N(N + 1) / 2 이다. 예를 들어 5 + 4 + 3 + 2 + 1 은 15 이다. 17. N(N - 1) / 2는 언제 등장할까? 비슷하게 생긴 공식이 하나 더 있다. N(N - 1) / 2 이것은 보통 1 + 2 + 3 + ... + (N - 1) 을 계산할 때 나온다. 예를 들어 N = 5 라면 1 + 2 + 3 + 4 이다. 합은 10 이다. 공식에 넣어보면 5(5 - 1) / 2 = 5 × 4 / 2 = 10 이다. 따라서 기억해야 할 차이는 간단하다. 1부터 N까지 더한다 → N(N + 1) / 2 1부터 N-1까지 더한다 → N(N - 1) / 2 18. 팩토리얼이란? 팩토리얼은 다음 기호를 사용한다. ! 예를 들어 5! 는 5 × 4 × 3 × 2 × 1 이라는 뜻이다. 따라서 5! = 120 이다. 몇 가지 팩토리얼 1! = 1 2! = 2 × 1 = 2 3! = 3 × 2 × 1 = 6 4! = 4 × 3 × 2 × 1 = 24 5! = 5 × 4 × 3 × 2 × 1 = 120 그리고 특별히 0! = 1 로 정의한다. 19. 팩토리얼은 왜 컴퓨터공학에서 등장할까? 팩토리얼은 가능한 모든 순서를 확인할 때 자주 등장한다. 예를 들어 사람 3명이 있다고 하자. A B C 이 사람들을 줄 세우는 방법은 ABC ACB BAC BCA CAB CBA 총 6가지다. 즉, 3! = 6 이다. 사람이 5명이라면 5! = 120 가지다. 10명이라면 10! = 3,628,800 가지다. 숫자가 조금만 증가해도 경우의 수가 엄청나게 증가한다. 그래서 시간복잡도가 O(N!) 인 알고리즘은 입력 크기가 조금만 커져도 현실적으로 실행하기 어려워진다. 20. 지수와 팩토리얼은 얼마나 빠르게 증가할까? 몇 가지 시간복잡도를 비교해보자. 1 log N N N log N N2 2^N N! 아래로 갈수록 일반적으로 훨씬 빠르게 증가한다. 예를 들어 N = 10 이라면 N = 10 N2 = 100 2^N = 1024 N! = 3,628,800 이다. 그래서 알고리즘에서는 단순히 몇 번 반복하는가? 뿐만 아니라 N이 증가했을 때 반복 횟수가 어떤 속도로 증가하는가? 를 매우 중요하게 본다. 21. 이번 편 핵심 연결 이번에 배운 내용을 컴퓨터공학과 연결하면 다음과 같다. 지수 ↓ 2^N ↓ 비트의 경우의 수 완전탐색 알고리즘 복잡도 로그 ↓ log N ↓ 계속 절반으로 나누는 과정 이진 탐색 트리 시그마 ↓ Σ ↓ 반복문의 전체 실행 횟수 계산 팩토리얼 ↓ N! ↓ 순서의 경우의 수 순열 완전탐색 즉 이 네 가지 개념은 서로 따로 떨어져 있는 것이 아니라 알고리즘의 시간복잡도를 이해하는 데 계속 연결된다. 22. 반드시 기억할 것 지수 23 = 2 × 2 × 2 = 8 같은 숫자를 반복해서 곱하는 것을 표현한다. 로그 23 = 8 이라면 log28 = 3 이다. 즉, 2를 몇 제곱해야 8이 되는가? 를 묻는 것이다. 시그마 Σ 는 여러 값을 모두 더한다. 라는 뜻이다. 1부터 N까지의 합 1 + 2 + ... + N 은 N(N + 1) / 2 이다. 1부터 N-1까지의 합 1 + 2 + ... + (N - 1) 은 N(N - 1) / 2 이다. 팩토리얼 N! 은 N × (N - 1) × (N - 2) × ... × 1 이다. 마무리 이번 편에서는 컴퓨터공학에서 앞으로 계속 만나게 될 가장 기본적인 수학 표현을 살펴봤다. 중요한 것은 공식을 무조건 외우는 것이 아니다. 예를 들어 log N 을 보면 아, 계속 절반으로 줄어드는 상황이구나. 라고 생각할 수 있어야 한다. N(N + 1) / 2 를 보면 1부터 N까지 반복 횟수를 모두 더했구나. 라고 생각할 수 있어야 한다. 그리고 N! 을 보면 가능한 모든 순서를 확인하고 있구나. 라고 연결할 수 있어야 한다. 이런 식으로 수학을 알고리즘과 연결해서 이해하면 시간복잡도 역시 단순 암기가 아니라 자연스럽게 이해할 수 있다. 다음 편에서는 함수와 그래프 를 공부한다. N , N2 , 2^N , log N 이 실제로 얼마나 다른 속도로 증가하는지 그래프를 통해 비교하고, 이것이 알고리즘 시간복잡도와 어떻게 연결되는지 살펴본다. 추천 태그