# [컴퓨터공학을 위한 수학] 2편 - 함수와 그래프, 증가율 이해하기

About this offer

[컴퓨터공학을 위한 수학] 2편 - 함수와 그래프, 증가율 이해하기 알고리즘 시간복잡도에서 O(N) , O(N2) , O(log N) , O(2^N) 같은 표현을 자주 본다. 이번 글에서는 함수와 그래프의 기본 개념부터 시작해서, 각각의 함수가 얼마나 빠르게 증가하는지 이해해본다. 1. 함수란 무엇인가? 함수는 어렵게 생각할 필요가 없다. 어떤 값을 넣었을 때 일정한 규칙에 따라 결과가 나오는 관계를 함수라고 한다. 예를 들어 f(x) = x + 1 이라는 함수가 있다고 하자. 여기에 x = 1 을 넣으면 f(1) = 1 + 1 = 2 이다. x = 5 를 넣으면 f(5) = 5 + 1 = 6 이다. 즉, 입력 ↓ 함수 ↓ 출력 이라고 생각하면 된다. 컴퓨터 프로그램과도 비슷하다. def add_one(x): return x + 1 이 함수 역시 값을 입력하면 결과를 반환한다. 따라서 수학의 함수와 프로그래밍의 함수는 기본적인 생각이 상당히 비슷하다. 2. x와 y는 무엇인가? 다음 함수가 있다고 하자. y = x + 1 여기서 x 는 입력값이고 y 는 결과값이다. 예를 들어 x = 1 이면 y = 2 이다. x = 2 이면 y = 3 이다. 표로 나타내면 다음과 같다. x y 1 2 2 3 3 4 4 5 5 6 함수는 결국 x가 변할 때 y가 어떻게 변하는가 를 나타내는 것이다. 3. 그래프란? 함수의 값을 그림으로 표현한 것이 그래프다. 예를 들어 y = x 라는 함수가 있다고 하자. 값은 다음과 같다. x = 1 → y = 1 x = 2 → y = 2 x = 3 → y = 3 x = 4 → y = 4 좌표로 나타내면 (1, 1) (2, 2) (3, 3) (4, 4) 가 된다. 이 점들을 연결하면 오른쪽 위로 올라가는 직선이 된다. 그래프를 보면 숫자를 하나하나 계산하지 않아도 x가 증가하면 y도 증가한다. 는 것을 한눈에 알 수 있다. 4. 알고리즘에서 함수가 왜 중요한가? 알고리즘에서는 보통 입력 데이터의 크기를 N 이라고 표현한다. 그리고 알고리즘이 수행해야 하는 연산 횟수를 함수처럼 생각한다. 예를 들어 데이터가 N개 있고 모든 데이터를 한 번씩 확인한다면 연산 횟수는 대략 N 번이다. 이를 함수로 보면 f(N) = N 이다. 만약 데이터마다 다시 전체 데이터를 확인한다면 N × N 번의 연산이 필요하다. 즉, f(N) = N2 이 된다. 시간복잡도는 결국 입력 크기 N이 커질 때 연산 횟수가 어떤 함수 형태로 증가하는가 를 표현하는 것이다. 5. 상수 함수 가장 단순한 형태부터 보자. f(N) = 1 입력 크기와 상관없이 항상 일정한 연산만 수행한다. 예를 들어 배열의 특정 인덱스에 접근한다고 하자. arr[3] 배열의 크기가 10개 이든 1,000,000개 이든 특정 인덱스에 접근하는 연산 자체는 거의 일정하다. 이런 시간복잡도를 O(1) 이라고 한다. 이를 상수 시간복잡도 라고 한다. 6. 선형 함수 다음은 f(N) = N 이다. 입력값이 증가한 만큼 결과도 똑같이 증가한다. 예를 들어 N = 10 → 10 N = 100 → 100 N = 1000 → 1000 이다. 알고리즘에서는 다음과 같은 경우다. for i in range(N): print(i) 반복문이 정확히 N번 실행된다. 따라서 시간복잡도는 O(N) 이다. 이것을 선형 시간복잡도 라고 한다. 7. 이차 함수 다음은 f(N) = N2 이다. 값을 비교해보자. N = 1 → 1 N = 10 → 100 N = 100 → 10,000 N = 1000 → 1,000,000 N이 10배 증가하면 결과는 100배 증가한다. 알고리즘에서는 중첩 반복문에서 자주 나타난다. for i in range(N): for j in range(N): 실행 바깥 반복문이 N번 실행되고 안쪽 반복문도 매번 N번 실행된다. 따라서 전체 연산 횟수는 N × N = N2 이다. 시간복잡도는 O(N2) 이다. 8. 세제곱 함수 반복문이 3개 겹치면 다음과 같은 형태가 나타날 수 있다. for i in range(N): for j in range(N): for k in range(N): 실행 전체 실행 횟수는 N × N × N 이므로 N3 이다. 시간복잡도는 O(N3) 이다. 값을 보면 빠르게 증가한다. N = 10 → 1,000 N = 100 → 1,000,000 N = 1000 → 1,000,000,000 중첩 반복문이 많아질수록 계산량이 매우 빠르게 증가하는 이유다. 9. 로그 함수 이번에는 log N 을 보자. 알고리즘에서 log N 은 보통 매번 일정한 비율로 줄어드는 경우 에 등장한다. 대표적으로 절반씩 줄어드는 경우다. 16 8 4 2 1 16에서 1까지 4단계다. 왜냐하면 24 = 16 이기 때문이다. 따라서 log216 = 4 이다. 10. 로그 함수는 매우 천천히 증가한다 N이 커져도 log N 은 매우 천천히 증가한다. 밑이 2인 로그를 기준으로 보면 N = 2 log2N = 1 N = 4 log2N = 2 N = 8 log2N = 3 N = 16 log2N = 4 N = 32 log2N = 5 N = 1024 log2N = 10 N이 1024 까지 커졌는데도 결과는 겨우 10 이다. 이것이 O(log N) 알고리즘이 매우 빠른 이유다. 11. O(log N)의 대표적인 예 대표적인 알고리즘은 이진 탐색이다. 데이터가 정렬되어 있을 때 매번 절반을 버린다. 예를 들어 데이터가 1024개라면 1024 512 256 128 64 32 16 8 4 2 1 약 10번이면 하나까지 줄일 수 있다. 따라서 O(log N) 이다. 12. N log N은 무엇인가? 알고리즘에서는 다음 표현도 매우 자주 등장한다. N log N 대표적으로 병합 정렬 힙 정렬 평균적인 퀵 정렬 등에서 등장한다. 직관적으로 생각하면 N개의 데이터를 처리하는 작업 을 log N번의 단계 동안 수행한다고 생각할 수 있다. 예를 들어 N = 1024 라고 하자. log21024 = 10 이므로 N log N 은 대략 1024 × 10 = 10,240 정도가 된다. 반면 N2 은 10242 = 1,048,576 이다. 둘의 차이가 매우 크다. 13. 지수 함수 이제 2^N 을 보자. 값을 살펴보면 N = 1 → 2 N = 2 → 4 N = 3 → 8 N = 4 → 16 N = 10 → 1024 N = 20 → 1,048,576 N이 조금 증가했을 뿐인데 값이 폭발적으로 증가한다. 알고리즘에서는 모든 부분집합을 확인하는 경우 등에 등장할 수 있다. 원소가 N개라면 가능한 부분집합의 개수는 2^N 개이기 때문이다. 14. 팩토리얼 함수 가장 무서운 증가율 중 하나가 N! 이다. 값을 살펴보자. 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 10! = 3,628,800 그리고 20! 은 약 2.43 × 10^18 이다. 입력값이 조금만 증가해도 경우의 수가 엄청나게 커진다. 모든 순열을 확인하는 알고리즘에서 자주 등장한다. 15. 시간복잡도 증가율 비교 알고리즘에서 자주 보는 시간복잡도를 빠른 순서대로 정리하면 대략 다음과 같다. O(1) ↓ O(log N) ↓ O(N) ↓ O(N log N) ↓ O(N2) ↓ O(N3) ↓ O(2^N) ↓ O(N!) 아래쪽으로 갈수록 입력 크기가 커졌을 때 연산량이 훨씬 빠르게 증가한다. 16. 실제 숫자로 비교하기 N = 10 이라고 해보자. O(1) → 1 O(log2N) → 약 3.32 O(N) → 10 O(N log2N) → 약 33 O(N2) → 100 O(N3) → 1,000 O(2^N) → 1,024 O(N!) → 3,628,800 N이 10일 때부터 이미 N! 은 엄청나게 커진다. 17. N = 100이면? 이번에는 N = 100 이라고 해보자. O(log2N) → 약 6.64 O(N) → 100 O(N log2N) → 약 664 O(N2) → 10,000 O(N3) → 1,000,000 여기서 중요한 것은 정확한 숫자를 외우는 것이 아니다. 핵심은 입력 크기가 증가할수록 함수마다 증가 속도가 완전히 다르다. 는 것이다. 18. O(N)과 O(N2)의 차이 처음에는 N 과 N2 이 별 차이가 없어 보일 수 있다. 하지만 N이 커지면 차이가 엄청나게 벌어진다. N = 10 N = 10 N2 = 100 N = 100 N = 100 N2 = 10,000 N = 10,000 N = 10,000 N2 = 100,000,000 입력 데이터가 많을수록 알고리즘의 시간복잡도가 중요한 이유다. 19. 그래프에서 기울기가 의미하는 것 함수 그래프를 볼 때는 얼마나 가파르게 올라가는가 를 보면 된다. 예를 들어 N 보다 N2 그래프가 훨씬 가파르게 올라간다. 그리고 2^N 은 더 빠르게 올라간다. 즉, 그래프가 가파르다 는 것은 입력 크기가 조금만 증가해도 연산량이 크게 증가한다. 는 뜻이다. 20. 알고리즘에서 중요한 것은 정확한 횟수가 아니다 다음 코드가 있다고 하자. for i in range(N): print(i) print(i) print(i) 연산이 대략 3N 번 일어난다. 그러면 시간복잡도는 O(3N) 일까? 아니다. Big-O에서는 상수를 제거한다. 따라서 O(N) 이라고 표현한다. 왜냐하면 N이 매우 커지면 중요한 것은 3 이라는 숫자가 아니라 N에 비례해서 증가한다. 는 사실이기 때문이다. 21. 최고차항이 중요한 이유 다음 함수가 있다고 하자. N2 + N + 10 N이 작을 때는 각각의 항이 모두 의미가 있다. 하지만 N이 매우 커지면 N2 이 압도적으로 커진다. 예를 들어 N = 1000 이면 N2 = 1,000,000 N = 1,000 10 = 10 이다. 따라서 전체 증가 속도를 결정하는 것은 N2 이다. 그래서 N2 + N + 10 의 시간복잡도는 O(N2) 이라고 한다. 22. 함수 증가율을 읽는 방법 시간복잡도를 보면 다음처럼 생각하면 된다. O(1) 데이터가 아무리 많아도 일정하다. O(log N) 데이터가 증가해도 연산 횟수는 아주 조금 증가한다. 주로 절반씩 줄이는 과정 에서 나타난다. O(N) 데이터가 2배면 연산량도 약 2배다. O(N log N) N보다 조금 더 빠르게 증가하지만 N2보다는 훨씬 느리다. O(N2) N이 2배가 되면 연산량은 약 4배가 된다. O(2^N) N이 1 증가할 때마다 연산량이 거의 2배가 된다. O(N!) N이 조금만 커져도 사실상 계산이 불가능할 정도로 증가한다. 23. 알고리즘 문제를 볼 때 생각하는 순서 코드를 보면서 다음 순서로 생각하면 좋다. 1. 입력 크기 N은 무엇인가? 2. 반복문이 몇 번 실행되는가? 3. 중첩 반복문이 있는가? 4. 반복할 때마다 값이 절반으로 줄어드는가? 5. 모든 경우의 수를 확인하는가? 6. N이 증가했을 때 전체 연산량이 어떻게 증가하는가? 이 과정을 통해 시간복잡도를 추측할 수 있다. 24. 함수와 알고리즘 연결하기 정리하면 다음과 같다. 함수 ↓ 입력값이 변하면 결과값이 어떻게 변하는지 표현 알고리즘에서는 입력값 = 데이터 크기 N 이고 결과값 = 연산 횟수 라고 생각할 수 있다. 따라서 시간복잡도는 사실상 입력 크기 N에 따른 연산 횟수의 증가 함수 를 표현하는 것이다. 25. 이번 편 핵심 정리 함수 입력값이 들어오면 일정한 규칙에 따라 결과가 나오는 관계 이다. 그래프 함수의 변화를 그림으로 표현한 것 이다. 시간복잡도 N이 증가했을 때 연산 횟수가 어떤 속도로 증가하는가 를 표현한다. 증가율 순서 1 < log N < N < N log N < N2 < N3 < 2^N < N! 정도로 기억하면 된다. 마무리 함수와 그래프를 배우는 이유는 단순히 수학 문제를 풀기 위해서가 아니다. 컴퓨터공학에서는 입력 데이터가 증가했을 때 프로그램의 연산량이 어떻게 증가하는가 를 이해하기 위해 함수가 필요하다. 특히 알고리즘에서는 O(1) O(log N) O(N) O(N log N) O(N2) O(2^N) O(N!) 같은 표현을 계속 사용한다. 이 표현들을 단순히 외우는 것보다 N이 커졌을 때 어느 것이 얼마나 빠르게 증가하는가 를 이해하는 것이 훨씬 중요하다. 다음 편에서는 수열과 급수 를 공부한다. 알고리즘 분석에서 자주 등장하는 1 + 2 + 3 + ... + N N + (N - 1) + ... + 1 1 + 2 + 4 + 8 + ... 같은 식이 왜 등장하고 어떻게 계산하는지를 정리한다.