[ Algorithm ] 자료구조와 Big-O 표기법

알고리즘 이란?

어떠한 문제를 해결하기 위한 절차나 방법을 뜻한다.

공식화한 형태로 표현한 것을 의미하며 유한성을 가지고 언젠가는 끝나야 하는 속성을 가지고 있다.

 

알고리즘의 조건

알고리즘은 아래 5가지 조건에 만족해야 한다.

• 입력: 외부에서 제공되는 자료가 0개 이상 존재해야 한다.
• 출력: 적어도 2개 이상의 서로 다른 결과를 도출해내야 한다.
• 명확성: 수행과정은 무엇을 하기위한 것인지 정의가 명확해야 한다.
• 유한성: 알고리즘의 명령어대로 수행하여 처리가 되었을때 종료되어야 한다.
• 효율성: 모든 과정이 명백히 실행가능해야 하며 시간적, 공간적 효율성을 가져야 한다.

 

1. 선형 자료구조

하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조이다.
데이터가 일렬로 연속적으로(순차적) 연결되어있다.
배열, 연결리스트, 스택, 큐, 덱 등이 있다.

 

2. 비선형 자료구조

하나의 데이터뒤에 다른 데이터가 여러개 올 수 있는 자료구조이다.
데이터가 일직선상으로 연결되어있지 않아도 되며 트리, 그래프 같은 것이 있다.

 

자료구조와 알고리즘의 관계

효율적인 자료구조 설계를 위해 알고리즘 지식이 요구된다.
효율적인 알고리즘을 작성하기 위해서는 문제상황에 맞는 적절한 자료구조가 사용되어야 하며
프로그램을 작성할 때 자료구조와 알고리즘 모두 고려해야 한다.

 

프로그램의 성능 측정 방법

• 시간복잡도(time complexity): 알고리즘에 사용되는 연산 횟수를 측정한다.
• 공간복잡도(space complexity): 알고리즘에 사용되는 메모리의 양을 측정한다.

주로 공간을 많이 사용하는 대신 시간을 단축하는 방법을 선택한다.

 

Big-O 표기법

복잡도를 표현할 때는 Big-O 표기법을 사용한다.

특정한 알고리즘이 얼마나 효율적인지 수치적으로 표현할 수 있으며 가장 빠르게 증가하는

항만을 고려하는 표기법이다.

 

• 다음 알고리즘은 O(n)의 시간 복잡도를 가진다.

let n =10;
let sum = 0;
for (let i = 0; i < n; i++) {
  sum += i;
}
console.log(sum); // 45

 

• 다음의 알고리즘은 O(n²)의 시간 복잡도를 가진다.

let n = 9;

for(let i = 1; i <= n; i++) {
  for(let j = 1; j <= n; j++) {
    console.log(`${i} X ${j} = ${i * j}`);
  }
}
/*
실행결과:
1 X 1 = 1
1 X 2 = 2
...
9X 8 = 72
9 X 9 = 81
*/

 

연산횟수에 대한 소요시간

일반적으로 연산횟수가 10억을 넘어가면 1초이상의 시간이 소요된다.
[예시] n = 1000

• O(log n) : 약 10번 연산
• O(n) : 약 1,000번 연산
• O(n log n) : 약 10,000번 연산
• O(n²) : 약 1,000,000번 연산
• O(n³) : 약 1,000,000,000번 연산

Big-O표기법으로 시간 복잡도를 표기할 때는 가장 큰 항만을 표시한다.
가장 큰 항에 붙어 있는 계수는 제거한다.
O(3n² + n) = O(n²)

 

 

Big-O 표기법을 사용한 시간복잡도의 예시

• O(1) : 스택에서 Push, Pop
• O(log n) : 이진트리
• O(n) : for 문
• O(n log n) : 퀵 정렬, 병합정렬, 힙 정렬
• O(n²): 이중 for 문, 삽입정렬, 거품정렬, 선택정렬
• O(2ⁿ) : 피보나치 수열

 

마치며...

마무리 글에 갑자기 알고리즘에 대해서 공부를 하게 된 이유에 대해 적을까 한다. 메모서비스 개발을 진행하고 있다가 마무리되어 갈 즈음에 문득 스스로 문제해결능력에 대한 불만와 방식에 대해서 의구심을 품게 되었다. "과연 지금까지의 방식이 효율적이고 가장 빠른 길일까?" 그러다 알고리즘에 대해서 문득 떠올리게 되었고 하나씩 알아보게 되었는데 지금까지 나에게 느꼈던 부족함을 해결해 줄 수 있을 것이라 생각이 들었다. 그렇게 개발에 1개월의 공백을 두게 되었지만 다양한 알고리즘을 학습하고 코드를 직접 만들어보기도 하면서 지금까지 나에게 부족했던 부분들이 많이 채워지는 것을 느꼈다. 문제를 해결하기 위해 사고하는 방식이 달라졌고 시간복잡도에 대한 개념이 생기니 효율적으로 문제해결에 다가설 수 있게 된 것 같았다. 완벽하다고 할 수 없겠지만 나에게 있어 개발자로서 필요한 역량을 향상시키기 위한 없어선 안될 1개월이었던 것 같다.