프로그래밍이란 결국 많은 자료들 중, 필요한 것을 찾아내서 원하는 모양으로 구현해 내는 것이라 생각한다. 그것을 효율적으로 하기 위해선 자료를 어떻게 보관하는지가 중요하다. 들어오는 많은 데이터를 어떤 방법으로 보관하는지에 따라, 원하는 모양으로 구현함에 있어서 효율성이 차이가 나기 때문이다.

보관하는 형태를 자료 구조, 필요한 것을 찾거나 원하는 모양으로 구현해 내는 과정이 알고리즘이다.

Data Structure(자료구조)

자료 구조(Data Structure)는 자료를 조직하는 방법이다.

자료를 추가(삽입), 삭제, 탐색 하는 기본적인 기능을 함에 있어서, 어떤 형식으로 자료를 조직하여 저장하면 좋을지 고민을 해야한다. 결국 자료구조는 시간, 공간의 효율성을 높이는데에 목적이 있다.

대표적인 자료구조

  • Stack & Queue
  • Linked List
  • Hash Table
  • Tree

Big-O Notation(빅오 표기법)

실행 시간에 대한 효율을 측정하는 것을 시간복잡도라 하고, 데이터의 크기(n)에 따른 시간복잡도를 표현하는 방법이 Big-O이다.

보통 최악의 효율성(최장시간)을 기준으로 작성한 코드가 얼마나 효율적인지 판단한다. (운좋게 한번에 값을 낼 수도 있지만, 코드를 작성할 땐 극단적으로 생각해 볼 필요가 있다. 만약 마지막에 찾는 값이 있다면? 오조오억개의 데이터가 들어오면?)

컴퓨터의 성능에 따라 절대적인 시간은 달라지기 때문에 모든 조건이 동일하다고 했을 때를 조건으로 추상적으로 표현하는 것이다. 추상적으로 표현한다는 것이 좀 애매한데, 거치는 단계로 생각하면 된다.

빅오 표기법의 의미

대표적인 빅오 표기법의 의미는 다음과 같다. 영어 단어는 해외 알고리즘 문제 풀때 조건으로 나오는 경우가 있으니, 알아두면 좋다.

  1. O(1): Constant time 상수시간 복잡도

    • 항상 일정.
    • 데이터의 양(n의 크기)과 상관 없이, 실행시간이 일정한 것을 의미한다. 1이 1초 1시간을 의미하는 절대적인 숫자가 아니라 항상 한 단계만 거치는, 동일 하다는 상수의 의미이다.
  2. O(n): Linear time 선형시간 복잡도

    • 단계가 n만큼.
    • n은 자료의 사이즈를 의미한다. O(n)은 n의 크기만큼 시간이 걸리는 것을 의미한다.
    • 대표적인 예가 for문이다. 아래 코드에서 for문은 i가 0부터 n만큼(n = 100이면 백번 반복, 천이면 천번 반복...)console.log(i)를 반복한다. 이런 경우 시간 복잡도는 O(n)이라 표현한다.
var n = 10;
for (var i = 0; i < n; i++) {
  console.log(i)
}
  1. O(n^2): Quadratic time 다항시간 복잡도

    • 단계가 급격히 증가... 효율성이 좋지 않다.
    • 2중 for문을 간단한 예로 들 수 있다. 2중 for문은 n의 하나당 n만큼 순회하는 것이므로, n*n으로 n^2이다.
  2. O(log n): Logarithmic time 로그시간 복잡도

    • 단계가 증가는 하지만 일정 만큼을 제외하고 증가
    • 대표적인 예가 이진트리탐색이다. 이진트리탐색은 루트를 시작으로 작으면 왼쪽, 크면 오른쪽으로 배치를 하기때문에, 길이 정해지면 나머지 사항을 고려하지 않는다. 단계가 증가는 하지만, n이나 n^2에 비해 적게 증가한다.

Big-O Complexity Chart

출처 www.bigocheatsheet.com

주요 빅오 표기법 시간크기 비교
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)

빅오 표기법 계산하기

빅오 표기법을 이용하여 계산을 해야할 때가 있다. 계산하는 규칙은 다음과 같다.

  1. 상수항은 무시한다.

O(59891n)에서 상수인 59891은 무시하고 O(n)으로 표기한다.
상수가 몇이든, 결과적으로 O(n)인 것이다.

  1. 상대적으로 미미한 값은 무시한다.

O(n^2 + n + n^18)는 결과적으로 O(n^18)이다.
위의 그래프를 보면 알 수 있듯이, n과 n^2을 비교해보면 알 수 있듯이, 지수가 큰 수에 비해 지수가 작은 수는 무시할 정도로 미미하다.(n의 값이 커질 수록 차이는 더욱 많이 난다.)

O(59n^2 + 123n + 987)을 계산한 값은 O(n^2)이다.

마무리

자료구조를 공부해도, 바로 알고리즘에 적용하기는 어렵다. 문제를 많이 접해봐야만 알 수 있다고 한다. 비슷한 유형을 자주 보다보면 살짝 보이긴 하는데, 그래도 여전히 어렵다. 알고리즘을 풀때마다 복잡도를 생각하려 하지만, 솔직히 항상 복잡도를 계산하면서 풀기는 쉽지 않다🤯. 일단 통과하는게 먼저니까... 그래도 일단 알고리즘 풀이가 통과하거나, 코드가 원하는 대로 작동한다면, 그 시점엔 내가 작성한 코드의 복잡도는 어떠한지 생각해보고, 개선 방안을 찾아보는 자세가 중요하다.

Reference & Learn More

Big-O Cheat Sheet
VisuAlgo

Comments