Big-O 표기법이란 알고리즘 공부를 시작할 때 필수적으로 언급하고 넘어가야합니다. Big-O 표기법을 설명할 때는 어쩔 수 없이 약간의 수학이 들어가게 됩니다. 이 글을 읽는 사람들 중에 최근 몇 년간 수학을 다뤄본적 없거나 로그라는 단어를 최근에 들어본 적 없다면 오랜만에 들어보게 될 수도 있겠네요. 걱정하지마세요. 알고리즘의 기초를 배우기 위한 내용이며 여러분도 할 수 있습니다.
우리가 Big-O 표기법을 알아야 하는 이유
이 글을 읽는 사람들 중 대부분은 알고리즘에 대한 공부를 하다 찾아오셨을 것입니다. 알고리즘에 대해 공부하다 보면 하나의 알고리즘에 대해 적게는 한 자리 수부터 많게는 그 이상의 해결방법들이 존재합니다.
예를 들어보죠. 어떤 하나의 문제에 두 가지 해결 방법이 있다고 생각해봅시다. 물론 두 가지 해결 방법 모두 정상적으로 동작하고, 단순히 변수나 함수의 식별자가 다른게 아닌 문제에 대한 접근법 자체가 다르다고 가정할 때 어떤 방법이 더 좋은지 어떻게 알 수 있을까요? "Big-O 표기법"은 바로 이런 질문들에 대한 답입니다.
어떠한 문제에 대한 코드를 일반화 하고 코드의 상대적 효율을 비교하는 방법입니다.
중요한 부분은 코드를 일반화하여 분류한다는 점입니다. 물론 코드에 "올해 최고의 코드" 나 "올해 최악의 코드" 같은 이름을 붙이는 것은 아니지만 판별 가능한 수치를 통해 코드의 성능을 표기하게 됩니다.
이걸 왜 신경써야해요?
이렇게 생각하는 사람도 있을겁니다. "제가 원하는 기능만 잘 작동하면 되는 거 아니에요? 어떤 코드가 최고인지 굳이 알아야하나요?" 혼자하는 프로젝트라면 지금 떠오른 질문이 맞습니다. 내가 사용하려고 만든 프로젝트 또는 프로그램이라면 여러분이 작성한 코드가 최고의 답이 될 수 있습니다. 하지만 기술 면접이나 알고리즘 문제를 풀거나 빅 데이터를 다뤄야 하는 회사에서 일하는 상황이라면 이야기가 달라집니다. 최적의 해결방법이 다른 방법들에 비해 몇 시간이 넘는 시간을 단축해줄 수도 있으니까요. 거짓말 같은 이야기라구요? 실제로 가장 좋은 알고리즘, 최고의 정답은 존재합니다.
예시
이제 하나의 문제에 대한 여러가지 해결방법들을 비교해보면서 알아봅시다.
여기 1부터 n 까지의 숫자를 모두 더하는 함수를 작성해야하는 문제가 있다고 해보죠.
문제
1부터 숫자n까지 (포함하여) 모두 더하여 결과를 리턴해주는 함수를 작성해보세요.
ex)
n이3일 때1 + 2 + 3이 되어6이 리턴되어야합니다.
가장 먼저 떠오를 수 있는 방법은 1부터 n 까지 반복하게 만든 뒤 total 이라는 변수를 만들어 누적시켜서 더하는 방식입니다.
두 번째로 떠오른 방법은 좀 더 한눈에 알아볼 수 있는 짧은 코드입니다. 한 줄로 적을 수 있는 짧은 코드지만 물론 짧다고 더 좋은 코드는 아닙니다.
바로 n 을 받아서 n + 1 을 곱하고 2 로 나누는 방식입니다.
이 코드가 어떻게 나왔는지 궁금할 수 있습니다. 사진이 준비되어 있지만, 이해를 못 하더라도 걱정하지 마세요. 지금 이야기의 핵심은 이 코드가 아니니까요! 중요하지 않습니다.
두 코드중 어떤 해결방법이 더 효율적인 코드일까요?
그리고 더 효율적인 코드라는 것이 무슨 뜻일까요?
- 초 단위, 밀리초 단위로 더 빠른 코드를 의미할까요?
- 작은 데이터나 큰 데이터를 계산할 때 더 빠른 코드를 의미할까요?
- 메모리 점유율이 더 낮은 코드를 의미할까요?
- 더 가독성이 좋은 코드를 의미할까요?
- 더 짧은 코드를 의미할까요?
더 효율적인 코드를 선택하라면 가독성보다는 빠르고 메모리 점유율이 낮은 코드를 일반적으로 선택할겁니다. 그리고 안타깝게도 속도와 메모리 점유율을 위한 코드는 가독성을 해치는 경우가 많습니다. 그렇기때문에 좋은 코드를 작성하는건 밧줄 위에서 균형을 잡는 것과 비슷합니다. 더 좋은 코드를 작성한다는 것은 속도가 빠른 코드를 작성하되 메모리 점유율도 낮지만 그러면서도 여전히 읽을수 있는 그러니까 밸런스 좋은 코드를 작성하는 것이고 속도, 메모리 점유율, 가독성과 같은 요소들이 어떻게 상호작용하는지를 알기 위해 우리는 알고리즘을 배우는 겁니다.
그렇다면 속도는 어떻게 측정할 수 있을까요? 먼저 가장 쉬운 방법은 내장 시간 측정 메소드를 사용하는겁니다.
두 번째 코드가 더 효율적으로 보이네요. 하지만 이 방법이 가장 정확한 시간 측정 방법은 아닙니다.
작성중
