[Algorithm 알고리즘] 코딩 테스트 입문자를 위한 빅오 표기법 개념!

자료구조를 배우고 난뒤 알고리즘에 처음 입문하게 되면 떡 하니 그래프가 보이는것이 있다. 바로 빅오 표기법 이라는 것이다.

 

 

O(N)

 

 

이러한 형식상의 표기는 이해가 가지만 만약 처음 배운다면 이걸 그래서 알고리즘하고 어떻게 적용하라는거지? 라는 생각이 문득 들었던 경험이 있었다.

 

 

 

빅오 표기법을 대하는 마인드셋?

---

결론부터 말하자면, 알고리즘 학자가 될게 아니라면 이 빅오 표기법은 알고리즘을 처음 배우는 사람 입장에서는 그냥 이런게 있구나 라고 한 번 생각하고 넘어가면 된다. 아마 대다수 이 글을 읽으시는 분들은 "코딩 테스트"를 염두해 두고 있으실거라 생각한다.

 

 

순차 탐색이 O(n)

이진 탐색이 O(logn)

.

.

.

 

 

이해도 못한 채 100날 봐바야 그냥 활용하지 못하는 지식에 불과하다.

 

 

이 지식이 어떻게 적용되는가에 대해서 알고리즘을 접하면서 시간초과가 날 때 비로소 다시 빅오표기법으로 돌아와서 학습하면 그제서야 눈이 뜨일 것이다.

 

 

본질은 "문제를 잘 푸는 알고리즘"을 위한 학습이지 "학자를 위한 알고리즘"은 아니다.  깊은 학습도 중요하지만 결국 "본질"을 정확히 알아야 한다. 그 본질이란 문제를 풀 때 필요한 지식을 문제를 풀어 나가면서 부분부분 매꿔나가는 것이다. 문제를 풀고 있지도 않은데, 주구장창 개념만 익혀나가는것은 마치 수학 개념만 읽고 문제를 풀어나가고 있지 않는것과 같다.

 

 

 

그런데도 궁금하다... 빅오 표기법이 뭔데?

---

알고리즘 수행시 걸리는 시간 (데이터의 수에 따른 수행시간)

 

 

이게 무슨 말일까? 조금 쉽게 말하면 아래와 같은 예시를 생각해보면 쉽게 이해할 수 있다.

 

 

 

우리가 A라는 방법으로 10가지일 할 때 10초가 걸린다.

우리가 B라는 방법으로 10가지일 할 때 100초가 걸린다.

 

 

 

우리 입장에서 그렇다면 어떤 방법을 채택하는게 훨씬 좋을까?

 

 

당연 A라는 방법이다.

 

그 이유는?

효율적이니까

 

 

이처럼 인간 뿐만 아니라 컴퓨터 체계에서도 이러한 효율적인 방법을 표기하는 방식을 쉽게 정의 해놓은게 결국 빅오 표기법이다.

 

 

이제 다시 네이버나 구글에 "빅오 표기 그래프"를 검색하면 무슨 말인지 쉽게 이해할 수 있다.