자료구조 개요

데이터를 담기위한 구조 

 

# 자료구조의 종류

1. 선형 구조(linear data structure): 선형 저료구조는 하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조다.

데이터가 일렬로 연속적으로(순차적으로) 연결되어 있다. 

 - 배열(array)

 - 연결 리스트(linked list)

 - 스택(stack)

 - 큐(queue)

 

2. 비선형 구조(non-linear data structure): 비선형 자료구조는 하나의 데이터 뒤에 다른 데이터가 여러 개 올 수 있는 자료구조다.

데이터가 일직선상으로 연결되어 있지 않아도 된다. 

 - 트리(tree) 

 - 그래프(graph) 

 

# 프로그램의 성능을 측정하는 방법

 - 시간 복잡도(time complexity): 알고리즘에 사용되는 연산 횟수를 측정한다. 

 - 공간 복잡도(space complexity): 알고리즘에 사용되는 메모리의 양을 측정한다. 

 - 공간을 많이 사용하지만 시간을 단축하는 방법이 많이 사용된다. 

 

1. Big-O 표기법

 - 복잡도를 표현할 때 사용한다. 

(1) 특정한 알고리즘이 얼마나 효율적인지 수치적으로 표현할 수 있다. 

(2) 가장 빠르게 증가하는 항만을 고려하는 표기법이다. 

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

let n = 10l
let summary = 0;

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


// 결과: 45

 

- 다음 알고리즘은 O(n^2)의 시간 복잡도를 가지고 있다. 

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
*/

 

보통 연산 횟수가 10억을 넘어가게되면 1초 이상의 시간이 소요되는데

예로 n이 1,000이라고 생각해보면

 - O(n): 약 1,000번의 연산

 - O(nlogn): 약 10,000번의 연산

 - O(n^2): 약 1,000,000번의 연산

 - O(n^3): 약 1,000,000,000번의 연산

 

 

# Big-O 표기법으로 시간 복잡도를 표기할 때는 가장 큰 항만을 표시한다. 

 - 가장 큰 항에 붙어 있는 계수는 제거한다. 

   O(3n^2 + n) = O(n^2)

 - 현실 세계에서는 동작 시간이 1초 이내인 알고리즘을 설계할 필요가 있다. 

 

# 코딩테스트에서는 일반적으로 메모리의 크기를 나타낼 때 MB단위로 표기한다. 

int a[1000]: 4KB

int a[1000000]: 4MB

int a[2000][2000]: 16MB

 

 

 

1. 배열(Array)

 - 가장 기본적인 자료구조다. 

 - 여러 개의 변수를 담는 공간으로 이해할 수 있다. 

 - 배열을 인덱스(index)가 존재하며, 인덱스는 0부터 시작한다. 

 - 특정한 인덱스에 직접적으로 접근 가능 -> 수행 시간: O(1)

 - 컴퓨터의 메인 메모리에서 배열의 공간은 연속적으로 할당된다. 

 - 장점은 캐시(cache) 히트 가능성이 높고, 조회가 빠르지만. 단점으로 배열의 크기를 미리 지정해야 되서, 데이터의 추가 및 삭제에 한계가 있다. 

 

2. 연결 리스트(Linked List)

 - 연결 리스트는 컴퓨터의 메인 메모리상에서 주소가 연속적이지 않다. 

 - 배열과 다르게 크기가 정해져 있지 않고, 리스트의 크기를 동적으로 변경 가능하다.

 - 장점은 포인터(pointer)를 통해 다음 데이터의 위치를 가리킨다는 점에서 삽입과 삭제가 간편하다. 

단점으로서는 특정 번째의 원소를 검색할 때는 앞에서부터 원소를 찾아야 하므로, 데이터 검색 속도가 느리다.