면접을 위한 CS 전공지식 노트 (주홍철, 길벗) : 233p ~ 237p
1. 자료구조
- 자료구조(data structure) : 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합
- C++ : STL을 기반으로 전반적인 자료 구조를 가장 잘 설명할 수 있는 언어
- STL(Standard Template Library) : C++의 표준 템플릿 라이브러리, 스택/배열 등 데이터 구조의 함수 등을 제공하는 라이브러리의 묶음
2. 복잡도 : 시간 복잡도와 공간 복잡도로 나뉨
1) 시간 복잡도
① C++의 기본
- main 함수를 중심으로 돌아감 -> main 함수를 무조건 하나 만들어야 함
- 이후 컴파일이 시작되면 전역변수 초기화, 라이브러리 import 등의 작업 .. -> main 함수에 얽혀 있는 함수들 작동 -> main 함수가 0을 리턴하며 프로세스가 종료
#include <bits/stdc++.h> // 모든 표준 라이브러리가 포함된 헤더
using namespace std; // 네임 스페이스 : 같은 클래스 이름 구별, 모듈화에 쓰이는 이름
string a = 0; // a : lvalue(추후 다시 사용될 수 있는 변수), rvalue : 한 번 쓰고 다시 사용되지 않는 변수
int main()
{
cin >> a;
cout << a << "\n";
return 0; // 프로세스가 정상적으로 마무리됨을 뜻함
}
② 빅오 표기법
- 시간 복잡도 : 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계
-> 어떠한 알고리즘의 로직이 얼마나 오랜 시간이 걸리는지를 나타나는 데 쓰이며, 보통 빅오 표기법으로 나타냄
- 빅오 표기법 : 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것, '가장 영향을 많이 끼치는' 항의 상수 인자를 빼고 나머지 항을 없앰 (입력 크기가 커질수록 연산량이 가장 많이 커지는 항 : n의 제곱항, 다른 것은 그에 비비 미미하기 때문에 n의 제곱항만 신경 쓰면 됨)
ex. 입력 크기 n의 모든 입력에 대한 알고리즘에 대한 필요한 시간 : 10n^2 + 2 = 빅오 표기법 : O(n^2)
for (int i = 0; i < 10; i++) { // i 루프 :10회
for (int j = 0; j < n; j++) { // j 루프 : n번
for (int k = 0; k < n; k++) { // k루프 : n번
if (true) cout << k << '\n';
}
}
} // -> 10 x n x n = 10n^2
for (int i = 0; i < n; i++) { // i 루프 : n번
if (true) cout << i << '\n';
} // n
// 10n^2 + n
// 빅오표기법 : 상수계수, 낮은 차수 항 무시 -> O(n^2)
③ 시간 복잡도의 존재 이유 : 효율적인 코드로 개선하는 데 쓰이는 척도
ex. 버튼을 누르고 화면이 나타나는 로직
원래 : O(n^2)의 시간 복잡도를 가지고, 9초가 걸림
O(n)의 시간 복잡도를 가지는 알고리즘으로 개선 -> 3초가 걸림
④ 시간 복잡도의 속도 비교
-> O(n^2)보다는 O(n), O(n)보다는 O(1)을 지향해야 함
2) 공간 복잡도
- 공간 복잡도 : 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함
int a[1004]; // a 배열 : 1004 x 4바이트(int형)의 크기를 가짐
3. 자료 구조에서의 시간 복잡도
보통 시간 복잡도를 생각할 때 평균, 최악의 시간 복잡도를 고려하면서 씀
평균 시간 복잡도
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
| 배열(array) | O(1) | O(n) | O(1) | O(n) |
| 스택(stack) | O(n) | O(n) | O(1) | O(1) |
| 큐(queue) | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스(doubly linked list) | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블(hash table) | O(1) | O(1) | O(1) | O(1) |
| 이진 탐색 트리(BST) | O(logn) | O(logn) | O(logn) | O(logn) |
| AVL 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
| 레드 블랙 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
최악의 시간 복잡도
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
| 배열(array) | O(1) | O(n) | O(n) | O(n) |
| 스택(stack) | O(n) | O(n) | O(1) | O(1) |
| 큐(queue) | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스(doubly linked list) | O(n) | O(n) | O(1) | O(n) |
| 해시 테이블(hash table) | O(n) | O(n) | O(n) | O(n) |
| 이진 탐색 트리(BST) | O(n) | O(n) | O(n) | O(n) |
| AVL 트리 | O(longn) | O(longn) | O(longn) | O(longn) |
| 레드 블랙 트리 | O(longn) | O(longn) | O(longn) | O(longn) |
'CS > 자료구조' 카테고리의 다른 글
| [C#/자료구조]스택 , 큐 (0) | 2024.08.05 |
|---|---|
| [자료 구조]선형 자료 구조 - 연결 리스트, 배열, 벡터, 스택, 큐 (0) | 2023.12.08 |