꾸준히 노력하는 것
혹시 여러분들은 꾸준히 노력하고 있는 것이 있나요?
예를 들자면, 알고리즘 풀이, 운동, 독서 또는 미라클 모닝과 같은 챌린지 말입니다.
만약 있다면, 여러분들의 실력 혹은 능력이 얼마나 빠른 속도로 늘었나요?
누군가는 어떤 분야에 소질이 있어 빠른 속도로 높은 퍼포먼스를 낼 수도 있고,
누군가는 난생 처음 해보는 분야라서 조금은 더딜 수도 있겠죠.
저 같은 경우에는, 최근 수영을 배우고 있습니다.
일주일에 3번, 겨우 45분만 투자하고 있는데요.
원래도 물에서 노는 것을 좋아하고 물에서 뜨거나 눈을 뜨는 재롱(?) 등은 할 수 있는 상태여서인지
제 생각보다도 빠르게 실력이 늘고 있는 것 같습니다.
이와 유사하게, 알고리즘에서는 문제를 얼마나 빨리 해결할 수 있는지를 "시간복잡도"라고 표현합니다.
단어만 생소하지, 의미는 위에서 말한 수영을 배울 때와 크게 다르지 않습니다.
수영 실력이 얼마나 빨리 느는가
수영의 실력을 가늠하는, 특정한 점수가 있다고 해봅시다.
낮을 수록 못하고, 높을 수록 잘하는 것이죠.
저는 처음에 그 점수가 0인 사람이었습니다.
수영장에 갈 때마다, 저의 점수는 늘어갔습니다.
늘어나는 패턴을 보니 아래와 같았습니다.
0, 1, 4, 9, 16...
이때, 제 친구 A가 저에게 이야기를 듣곤 수영에 관심이 생겨 같이 다니게 되었습니다.
이 친구도 역시 점수가 0으로 시작했는데요.
맥주병이었던 탓에, 실력이 빠르게 늘지 않았습니다.
친구 A의 점수는 아래와 같은 패턴이었습니다.
0, 1, 2, 3, 4...
딱 봐도 저의 실력이 더 빠르게 늘 것이라고 예상할 수 있겠죠??
제가 수영이라는, "과제"를 더 빠르게 풀고 있는 셈입니다.
나중엔 내가 더 잘해
저와 친구 A는 수영에 푹 빠져, 하루종일 수영 얘기만 했습니다.
이때 친구 B가 지나가다가 이 얘기를 듣게 됩니다.
친구 B는 예전에 수영을 배운 적이 있는데, 저희의 이야기를 듣고 관심이 생겨
수영을 다시 배우기 시작했습니다.
이 친구는 한 번 수영을 배운적이 있는 사람이었기 때문에,
점수가 0에서 시작하지 않습니다.
무려 100에서 시작하죠.
친구 B의 점수는 아래와 같은 패턴이었습니다.
100, 101, 102, 103, 104...
점수가 늘어나는 속도는 친구 A와 같지만, 시작점이 너무 달랐죠.
친구 B는 틈만 나면, 저와 친구 A를 놀려댔습니다.
수영 그렇게 하는 거 아니라면서 말이죠.
하지만 길게 생각해보면, 저와 친구 A는 크게 기죽을 것이 아니었습니다.
한 번 생각해보죠, 만약 10일이 지나면 어떻게 될까요?
저의 점수는 아래와 같습니다.
0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100...
친구 A의 점수는 아래와 같습니다.
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10...
친구 B의 점수는 아래와 같습니다.
100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110...
제가 어마무시한 속도로 따라잡고 있는 거 보이시나요?
위의 점수 추이를 봤을 때, 제가 왜 기죽을 필요가 없는지 단번에 이해가 될 것입니다.
나중엔 크게 차이 없어
물론 아직 친구 B는 속상할 겁니다
쟤들은 100점에서 노는데 자신은 아직도 10점에 머물러 있으니까요
그렇다면 10일이 아니라 1,000일이 지나면 어떻게 될까요?
성장 속도가 빠른 저는.. 그때까지 수영을 한다면 수영선수를 하고 있겠네요.
그렇다면 친구 A와 B는 어떨까요?
친구 A는 1000점, 친구 B는 1100점이 되겠죠.
만약 10,000일이 지나면요?
친구 A는 10,000점이고 친구 B는 10,100점이 될겁니다.
둘이 실력 차이가 점점 비슷해지는 느낌이 드시나요??
둘이 같은 속도로 실력이 늘어난다면, 아주 오랜 시간이 지난 뒤에는 비등비등할겁니다.
그날의 컨디션에 따라서 친구 A가 친구 B를 이길 수도 있죠.
수영 예제와 시간복잡도
위에서 예시로 들었던 점수가 특정 함수 형태를 따른다고 생각하면,
우리가 일반적으로 말하는 시간복잡도와 같은 이야기가 됩니다.
아래 내용 처럼 말이죠
- 제 수영 실력이 성장하는 양상은 $ f(x) = x^2 $
- 친구 A의 수영실력은 $ f(x) = x $
- 친구 B의 수영실력은 $ f(x) = x + 100 $
다만, 위의 수영 예제에서는 점수가 높을 수록 좋은 것이었지만
시간은 높을 수록 안좋다는 점이 다릅니다.
시간복잡도
자 그럼 시간복잡도에 대해서 얘기해볼까요?
시간복잡도란, 간단히 이야기해서
얼마나 오래 걸리는가
라고 볼 수 있습니다.
예를 들어보겠습니다.
문제 A가 있고, 이를 풀어내는 방법이 x, y, z로 3가지가 있습니다.
문제 A는 n개의 숫자에 대한 문제입니다. 예를 들자면, n개의 숫자 중 가장 큰 것을 찾는 것이 있겠네요.
이때, 방법 x, y, z는 각각 A를 풀어내는 시간이 다릅니다.
당연히 그 시간은 n이 늘어날 수록 늘어나고, 줄어들 수록 줄어들게 됩니다.
말하자면, n에 의존하고, n으로 표현 가능하다는 거죠.
각각의 방법이 사용하는 시간이 아래와 같다고 가정해봅시다.
- x : $ n^2 $
- y : $ n $
- z : $ n + 100 $
네, 아까의 수영 예제와 같은 식입니다.
앞서 말씀드렸던 것처럼 숫자가 높을 수록 안좋다는 점만 빼면요.
여기서 숫자는, 컴퓨터에서의 연산횟수라고 생각하시면 됩니다.
n = 100일 때, x는 그 문제를 풀기 위해서 10,000번의 연산을 진행한다고 말할 수 있죠.
x는 n이 늘어날 수록, 누구보다 빠르게 크기가 커집니다.
y와 z는 x보다 더디게 증가하죠.
다만, z는 시작점이 조금 앞서있어서 초반에는 x보다 큽니다.
여기서 앞의 수영예제처럼 n이 10, 100, 1000, 10000처럼 증가하게 되면
z가 초반에는 x보다 앞서있었을 지 몰라도 추후에는 x가 훨씬 커지게 됩니다.
알고리즘 문제들은 대부분 n이 작지 않기 때문에, 적은 시간을 들이는 방법을 찾고 싶다면
시작점이 조금 앞서있더라도, 더디게 증가하는 방법이 최종적으로는 가장 빠른 방법일 가능성이 높습니다.
다르게 말하자면, 기울기가 중요하다는 뜻이죠.
점근표기법
앞서 시간 복잡도는 "얼마나 오래 걸리는가?"라는 의미라고 했습니다.
그리고 예시를 통해서, "더디게 증가하면 제일 빠르다"라는 것도 확인했죠.
따라서 여러가지의 방법이 존재할 때, 시작점이 어딘지가 아니라, 얼마나 더디냐 얼마나 가파르냐를 중심으로 봐야할 필요가 생겼습니다.
예를 들면 아래 2개의 방법 x, y가 있다고 합시다.
- x : $ n^6 + n^4 + 2n^3 + 3n^2 + n $
- y : $ 15n^5 + n^4 + n + 350 $
네 뭐 당연히 x가 더 가파른 친구겠지만, 이게 더 복잡해진다면 한 번에 확인하기 힘들 수도 있겠죠?
그래서 우리는 시간복잡도를 점근표기법이라는 방식으로 표현합니다.
점근 표기법의 정의는 아래와 같은데요,
보기만 해도 눈이 핑핑 돕니다 ㅋㅋㅋ
간단하게 이해하자면,
x 값이 충분히 클 때,
$ f(x) $보다 $ g(x) $의 상수배가 크다면,
$ f(x) \in O(g(x)) $이라고 할 수 있다는 겁니다.
앞의 수영 예제에서, x가 충분히 클 때(날짜가 많이 지났을 때)
$ n + 100 $보다 $ n^2 $의 상수배가 더 크다면,
$ n + 100 \in O(n^2) $이라고 할 수 있습니다.
$ n + 100 \in O(n) $이기도 하고,
$ n + 100 \in O(n^3) $이기도 하며,
$ 30n + 2 \in O(2n) $이기도 합니다.
따라서 $ O(n) $에는 $ n + 100, 30n + 2, 40n + 32, 3 $ 등등이 있을 수 있고,
$ O(2n) $에는 $ 3n + 100, 30n + 2, 41n + 32, 3 $ 등등이 있을 수 있고,
$ O(n^2) $에는 $ n + 100, 30n + 2, n^2 + 3, 500n^2 $ 등등이 있을 수 있죠.
점근 표기법의 의미
그래서 이렇게 복잡한 수식으로 이런 O(뭐시기) 표기법을 사용하면 무슨 의미가 있는 걸까요?
바로, 간단함 입니다.
엥? 뭐가 간단하냐 싶으실 수도 있습니다.
앞서 나열했던 내용을 잘 보시면,
O(뭐시기)는 결국 자기보다 기울기가 비슷하거나 작은 친구들을 가지게 됩니다.
그러니까 "대략 이 정도 최대 속도로 증가하는 녀석들" 을 표현할 수 있는 겁니다.
$ O(n) $에 속하면, 대략 $ n $ 정도 속도로 증가하는 녀석인 것이고,
$ O(3n^2) $에 속하면, 대략 $ 3n^2 $ 정도 속도로 증가하는 녀석인 거죠.
알고리즘 문제를 풀어내는 방법,
즉 알고리즘마다 시간복잡도는 천차만별일 것입니다.
다양한 상수배와 상수합이 시간복잡도 식을 어지럽게 만들겠죠.
그러나, 알고리즘의 시간복잡도를 점근표기법으로 표현한다? 그러면 이제 간단하게 표현할 수 있는 겁니다.
당연하고 상식적이게도, 우리는 굳이 $ O(3n^2 + 2) $이라고는 하지 않습니다.
그냥 상수배나 상수 합을 다 떼어내고 담백하게 $ O(n^2) $이라고 표기하죠.
둘의 의미는 사실상 거의 동일하기 때문에, 우리의 목표인 단순성을 위해서 다 떼버렸다고 보시면 됩니다.
시간복잡도와 공간복잡도
아하, 그러면 시간복잡도는 그 알고리즘이 얼마나 빠르냐 느리냐인 것이고 표현 방식으로 점근표기법을 쓴다고 이해하면 되겠네요.
그러면 공간복잡도는 뭘까요?
사실 공간복잡도는 시간복잡도 만큼 중요하지 않습니다.
현대 컴퓨터가 발전하면서 저장공간이 기하급수적으로 증가했지만, 우리에게 아직 시간은 정복의 대상이죠.
그래서 공간을 효율적으로 활용하는 것은 시간을 효율적으로 활용하는 것보다는 덜 중요하게 여겨집니다.
물론, 공간복잡도를 아예 고려할 필요가 없다는 것은 아닙니다.
문제에 공간에 대한 제한이 분명히 존재하고, 실제 프로그램에서도 공간을 덜 쓰는 게 더 좋으니까요
다만, 고전 게임인 마리오 브라더스에서 사용했던 방식처럼 "악착같이" 용량을 줄일 필요까지는 없어졌다는 말입니다.
심지어 공간복잡도는 시간복잡도를 위해서 희생하기도 합니다.
공간을 더 많이 활용한다는 것은 더 많이 기억한다는 뜻이고,
굳이 매번 계산하지 않고 기억해두면 계산하는 시간을 아낄 수 있기 때문이죠.
실전에서 적용하는 시간복잡도와 공간복잡도
자 이제 시간복잡도와 공간복잡도가 뭔지는 알았는데, 이게 문제 푸는데 무슨 쓸모가 있을까요?
우리가 알고리즘 문제를 풀게 되면, 어떠한 입력을 받게 됩니다.
이 입력 값의 개수에 따라서, 컴퓨터가 문제를 푸는데 걸리는 시간이 결정되죠.
문제의 제한 시간, 그리고 문제에서 주어지는 입력 값의 개수를 모두 만족할 수 있는,
그런 알고리즘을 고르는 기준이 되는 것이 바로 시간 복잡도입니다.
컴퓨터는 대략 1초에 1억번의 연산을 진행할 수 있다고 합니다.
그렇다면 문제에서 주어지는 입력 값이 1억개라면,
$ O(n) $의 시간복잡도를 가지는 알고리즘을 이용했을 때 1초가 걸리겠죠.
만약 문제에서 주어지는 값이 1,000개라면,
$ O(n^2) $의 시간 복잡도를 가지는 알고리즘을 이용할 수 있습니다.(1초보다 덜 걸리기 때문)
이처럼 문제의 제한시간과 입력 값의 개수를 알고있다면, 얼마만큼의 시간복잡도를 가지는 방식을 이용해야할지 감을 잡을 수 있습니다.
아래 표를 통해서 적합한 시간복잡도를 확인해보세요.
연산 횟수가 1억이라면(0이 9개, 콤마가 3개) 실행시간이 1초라고 생각하면 됩니다.
$O(logn)$의 연산횟수를 구하려면, $2^n = 연산횟수$인 n을 찾으면 됩니다.
이렇게 보니 $ log n $은 정말 강력하네요 ㄷㄷ
| 입력값 개수 | 시간복잡도 | 연산 횟수 |
| 1,000 | O(logn) | 10 |
| O(n) | 1,000 | |
| O(nlogn) | 1,000 x 10 = 10,000 | |
| O(n^2) | 1,000 x 1,000 = 1,000,000 | |
| O(n^3) | 1,000 x 1,000 x 1,000 = 1,000,000,000 | |
| 10,000 | O(logn) | 10 + 3 |
| O(n) | 10,000 | |
| O(nlogn) | 10,000 x 13 = 130,000 | |
| O(n^2) | 10,000 x 10,000 = 100,000,000 | |
| 1,000,000 | O(logn) | 10 + 10 = 20 |
| O(n) | 1,000,000 | |
| O(nlogn) | 1,000,000 x 20 = 20,000,000 |
당신의 기울기는 얼마인가요?
우리는 학생으로서 공부하고, 수영 강습 수강생으로서 수영하고, 블로그의 주인장으로서 글을 쓰는 등의 많은 일들을 하고 있습니다.
이들은 어떤 관점에서는 해야할 일이고 책임이며, 문제이기도 하고 취미이기도 하죠.
그리고 그 경험과 노력들은 실력과 능력이 되어 우리를 이루게 됩니다.
어떤 사람들은 태어날 때부터 빠르게 배웁니다.
평범한 사람이라도 어떤 특정 분야에서는 누구보다 가파른 학습곡선을 그리기도 하죠.
저는 항상 그런 사람이 되고 싶었습니다.
누구보다 높은 기울기를 가지고, 모든 일을 해결하는 그런 슈퍼맨이 되고 싶었죠.
그러나 사람은 컴퓨터가 아니고, 우리의 기울기는 고정되어있지 않은, 꾸준히 변하는 속성을 가지고 있습니다.
그렇기 때문에 높은 기울기를 강박적으로 좇게 되면 일시적으로는 가파를 수 있지만
이후의 기울기가 급격하게 낮아져 결과적으로는 그리 높지 못한 곳에 위치하게 됩니다.
우리는 컴퓨터가 다루는 문제보다 더 큰 문제들을 다룹니다.
컴퓨터가 풀어내는 알고리즘 문제는 대부분 10초 이상을 넘지 않죠.
우리의 문제는 우리가 살아가는 일평생 풀어내야 합니다.
컴퓨터가 아닌 사람이기에, 당신의 기울기는 적절한 수준에서 관리되어야 합니다.
너무 높은 기울기에 지쳐 주저앉았다면, 적절함과 꾸준함에 대해 고민할 때인 것 같습니다.
'알고리즘' 카테고리의 다른 글
| 백준 1931 : 회의실 배정 (1) | 2024.10.09 |
|---|---|
| 백준 1193 : 분수찾기 (0) | 2024.10.08 |
| 취업을 위한 코테 톺아보기 (0) | 2024.10.04 |
| 코딩 테스트를 여행하는 개발자를 위한 모든 준비법 (4) | 2024.10.01 |
| 백준 26156: 나락도 락이다 아이디어 & 코드 (0) | 2023.03.16 |
