[알고리즘] 2-1. 자료구조

# 자료구조(data structure)란?
- 다수의 자료(data)를 담기 위한 구조
- 데이터의 수가 많아질수록 효율적인 자료구조가 필요하다.
- 자료구조와 알고리즘은 상당히 밀접한 관계가 있다.
- 성능비교: 자료구조/알고리즘의 성능 측정 방법에 대해 이해할 필요가 있다.
- 자료구조의 필요성: 자료구조를 제대로 이해하지 못하면 불필요하게 메모리와 계산을 낭비할 여지가 있다.
  즉, 데이터를 효과적으로 저장하고, 처리하는 방법에 대해 바르게 이해할 필요가 있다.

# 자료구조의 종류
1. 선형구조(linear data structure)
- 배열(array)
- 연결 리스트(linked list)
- 스택(stack)
- 큐(queue)
2. 비선형 구조(non-linear data structure)
- 트리(tree)
- 그래프(graph)

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

# 비선형 자료구조
- 하나의 데이터 뒤에 다른 데이터가 여러개 올 수 있는 자료구조다.
- 데이터가 일직선상으로 연결되어 있지 않아도 된다.
- 예시) 트리, 그래프

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

# 프로그램의 성능 측정 방법
- 시간 복잡도(time complexity): 알고리즘에 사용되는 연산 횟수를 측정한다.
- 공간 복잡도(space complexity): 알고리즘에 사용되는 메모리의 양을 측정한다.
- 공간을 많이 사용하는 대신 시간을 단축하는 방법이 흔히 사용된다.

# 프로그램의 성능 측정 방법: Big-O 표기법
- 복잡도를 표현할 때는 Big-O 표기법을 사용한다.
 1. 특정한 알고리즘이 얼마나 효율적인지 수치적으로 표현할 수 있다.
 2. 가장 빠르게 증가하는 항만을 고려하는 표기법이다.
- 다음 알고리즘은 O(n)의 시간 복잡도를 가진다.

  let n = 10;
  let summary = 0;

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

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

  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 ....
   9 X 8 = 72
   9 X 9 = 81

 

# 프로그램의 성능 측정 방법
- 각 시간 복잡도

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

 

- 현실 세계에서는 동작 시간이 1초 이내인 알고리즘을 설계할 필요가 있다.
- 코딩 테스트에서 메모리의 크기를 나타낼 때는 일반적으로 MB 단위로 표기한다.

   int a[1000]: 4KB
   int a[1000000]: 4MB
   int a[2000][2000]: 16MB

 

# 자료구조를 적절히 활용하기
- 프로그램을 작성할 때는 자료구조를 적절히 활용하여 시간 복잡도를 최소화하여야 한다.