자료구조란?
- 자료구조는 다수의
자료(data)를 담기 위한 구조 - 데이터의 수가 많아질수록 효율적인 자료구조가 필요
자료구조의 개요
- 자료구조의 필요성에 대해서 이해할 필요가 있다.
성능 비교: 자료구조/알고리즘의성능 측정 방법에 대해 이해할 필요가 있다.
예)
자료1 : 나는 삽입과 추출이 모두 적당히 빨라 👉🏻 삽입 : O(logN) / 추출 : O(logN)
자료2 : 나는 삽입은 느리지만, 추출은 빨라 👉🏻 삽입 : O(N) / 추출 : O(1)
자료구조의 필요성
- 데이터를 효과적으로 저장하고, 처리하는 방법에 대해 바르게 이해할 필요가 있다.
- 자료구조를 제대로 이해하지 못하면 불필요하게 메모리와 계산을 낭비할 여지가 있다.
- C언어를 기준으로 정수(int) 형식의 데이터가 100만 개가량이 존재한다고 가정했을 때, 해당 프로그램을 이용하면 내부적으로 하루에 데이터 조회가 1억 번 이상 발생한다. 이 때 원하는 데이터를 가장 빠르게 찾도록 해주는 자료구조는?
👉🏻 tree같은 자료구조를 활용하면 된다.(데이터 검색, 추가, 수정, 삭제가 많이 발생할 때는 tree 구조를 많이 사용)
자료구조의 종류
1. 선형 구조(linear data structure)
- 배열(array)
- 연결 리스트(linked list)
- 스택(stack)
- 큐(queue)
2. 비선형 구조(non-linear data structure)
- 트리(tree)
- 그래프(graph)
선형 자료구조
- 선형 자료구조는 하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조
- 데이터가 일렬로 연속적으로(순차적으로) 연결되어 있다.
ex. 배열, 연결 리스트(linked list), 스택(stack), 큐, 덱(deque)
비선형 자료구조
- 비선형 자료구조는 하나의 데이터 뒤에 다른 데이터가 여러 개 올 수 있는 자료구조
- 데이터가 일직선상으로 연결되어 있지 않다.
ex. 트리(tree), 그래프(graph)
자료구조와 알고리즘
- 효율적인 자료구조 설계를 위해 알고리즘 지식이 필요
- 효율적인 알고리즘을 작성하기 위해서 문제 상황에 맞는 적절한 자료구조가 사용되어야 한다.
- 프로그램을 작성할 때 자료구조와 알고리즘 모두 고려해야 한다.
프로그램의 성능 측정 방법
- 시간 복잡도(time complexity) : 알고리즘에 사용되는
연산 횟수를 측정한다. - 공간 복잡도(space complexity) : 알고리즘에 사용되는
메모리의 양을 측정한다. - 공간을 많이 사용하는 대신 시간을 단축하는 방법이 흔히 사용된다.
- 시간과 공간은 어느정도 조율이 가능하다고 이해할 수 있다.
방법 1 : Big-O 표기법
- 복잡도를 표현할 때는 Big-O 표기법을 사용한다.
- 특정한 알고리즘이 얼마나 효율적인지 수치적으로 표현할 수 있다.
- 가장 빠르게 증가하는 항만을 고려하는 표기법
- 다음 알고리즘은 O(n)의 시간 복잡도를 가진다.
let n = 10;
let summary = 0;
for (let i = 0; i < n; i++) {
summary += i;
}
console.log(summary);- 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}`);
}
}
👉🏻 연산의 횟수(y축)이 낮은 복잡도가 속도가 더 빠르다.
-
Big-O 표기법으로 시간 복잡도를 표기할 때는 가장 큰 항만을 표시한다.
-
가장 큰 항에 붙어 있는
계수는 제거한다.
-
현실 세계에서는
동작 시간이 1초 이내인 알고리즘을 설계할 필요가 있다.
👉🏻 사용자 측면에서 봤을 때도 필요가 있다 -
코딩 테스트에서 메모리의 크기를 나타낼 때는
일반적으로 MB 단위로 표기한다.- int a[1000] : 4KB
- int a[1000000] : 4MB
- int a[2000][2000] : 16MB
hello, world!