Basic 카테고리에서는 효율적인 코드 작성을 위해서 필요한 기본 개념과 알고리즘들을 하나씩 익혀나 가겠습니다!

서론

저는 대학원을 입학하며 처음 코딩을 시작했습니다.
그 때가 2018년도 3월이니 벌써 3년전이네요.
학부에서 배운 내용이 아닌 새로운 세부 전공에 도전하다보니 수업이나 논문에 나오는 단어의 개념도 모를때였죠.
설상가상으로 첫 학기에 저를 마중나온 수업은 최신 통계 방법들을 코드로 작성해서 데이터에 적용하는 수업이었습니다.

즉, 저는 Python, 코딩, 통계, 머신러닝과 연구분야에 대한 개념까지 모두 없는 말그대로 zero base 학생이었습니다.
다른 연구자들보다 능력이 부족한 상태로 시작하다보니 시간이 늘 모자랐습니다.
모든 것들을 해내기 위해서 거의 1년간은 아침에 택시를 타고 집에 들어가며 수업 과제들, 연구 미팅 준비를 하며 지냈습니다.

시간이 부족했던 저는 python을 시작할 때 하나씩 배운다는 느낌보다는 빠른 구글링으로 문제를 해결하는데 급급했습니다. 결국 3년 후인 지금, 구글링을 통한 집요한 문제해결에는 누구보다 자신있지만, 자료 구조의 특징을 이해하고 알고리즘을 효율적으로 작성하는 방법에 대한 고민과 기본 지식이 부족한 상황입니다.

필요성

저처럼 실무 성과에 급급하며 python을 시작하셨다면 다음 그림에 익숙하실지도 모릅니다.

저는 빅데이터를 다루는 일을 했으므로, 비둘기가 매우 오랫동안 목을 돌려야 날아가는 상황이 수두룩했습니다.
이제 저도 빠르고 효율적인 코드를 작성하는 사람이 되고 싶습니다.
Big O Notation (빅오 표기법)은 ‘알고리즘이 얼마나 빠른가? 더 나은 방법은 없을까?’라는 생각에 대한 정량적인 비교를 가능하게 합니다.
예를 들어, Big O Notation으로 인풋 데이터가 늘어날 때 연산 횟수가 증가하는 정도를 예측할 수 있습니다.

정의

Big O Notation은 알고리즘이 얼마나 빠른지 표기하는 방법입니다.

O(원하는 계산 결과 n을 만들기 위해 필요한 연산횟수) 로 표기합니다. 이때 n은 원하는 계산 결과입니다.

예시

종이에 16개의 네모칸을 만들어야한다면, n=16입니다.

  • 경우 1
    하나씩 네모칸을 그린다면 총 16번의 연산이 필요합니다.
    이때 Big O Notation은 O(n) 입니다.

  • 경우 2
    종이를 반씩 접는 방법으로 더 빠르게 네모칸을 만드는 경우에는, 종이를 4번 접는 것만으로 16개의 칸을 만들 수 있으므로 연산 횟수는 4입니다. 연산횟수 4를 n=16이 들어간 식으로 표현한다면 Big O Notation은 O(logn) 입니다.

1초에 10번의 연산이 가능한 경우 걸리는 시간을 계산해봅시다.

  • 경우 1에 걸리는 시간
    경우 1은 16번의 연산이 필요하므로 1.6초 걸릴 것으로 예상할 수 있습니다.

  • 경우 2에 걸리는 시간
    경우 2는 4번의 연산이 필요하므로 0.4초 걸릴 것으로 예상할 수 있습니다.

이제 우리는 Big O Notation 덕분에 만들어야하는 네모칸의 수(n)이 증가할수록 ‘경우 2’ 방법이 연산 시간을 단축해줄 것이라는 것을 예상할 수 있습니다.

종류

많이 사용하는 Big O Notation을 빠른 순서대로 나열했습니다.

  1. O(log n): 이진탐색
  2. O(n): 단순탐색
  3. O(nlog n): 퀵 정렬 (빠른)
  4. O(n^2): 선택 정렬 (느린)
  5. O(n!): (매우 느린)

Reference

포스팅은 Hello Coding 그림으로 개념을 이해하는 알고리즘(아디트야 바르가바, 한빛미디어) >책을 요약한 것입니다.