이 포스팅은 '면접을 위한 CS 전공지식 노트'를 읽고 제 나름대로 정리를 해본 것입니다. 사족도 붙여 가며 정리하였는데, 만약 문제가 된다면 포스팅 내리겠습니다.
1. 복잡도
1) 시간 복잡도
- 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계(얼마나 오래 걸리느냐)
- 보통 빅오 표기법으로 나타냄
- 빅오 표기법 : 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것
- 효율적인 코드로 개선하는 데 쓰이는 척도가 됨
2) 공간 복잡도
- 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
3) 자료 구조에서의 시간 복잡도(평균)
2. 선형 자료 구조
- 요소가 일렬로 나열되어 있는 자료 구조
1) 연결 리스트
- 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조
- 연결 리스트는 이전에 공부한 적이 있어서 포스팅도 해두었다!(Link)
2) (정적) 배열
- 같은 타입의 변수들로 이루어짐
- 크기가 정해져 있음
- 인접한 메모리 위치에 있는 데이터를 모아놓은 집합
- 중복을 허용하고 순서가 있음
- 랜덤 접근(직접 접근: 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있음 <-> 순차적 접근)이 가능
3) 벡터(동적 배열)
- 컴파일 시점에 개수를 모르면 벡터를 사용해야 함
- 중복 허용하고 순서가 있음
- 랜덤 접근이 가능
- JS의 배열은 벡터라고 생각하면 될까?(*찾아보기)
4) 스택
- LIFO 성질을 지닌 자료 구조
- 재귀적 함수나 알고리즘, 웹 브라우저 방문 기록 등에 쓰임
5) 큐
- FIFO 성질을 지닌 자료 구조
- CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용
3. 비선형 자료 구조(*이 부분 추가로 공부하기)
- 자료 순서나 관계가 복잡한 구조. 일반적으로는 트리나 그래프를 뜻함.
1) 그래프
- 정점(vertext)와 간선(edge)로 이루어진 자료 구조
- 어떠한 곳(정점)에서 어떠한 곳으로 무언가를 통해(간선) 간다.
- 가중치 : 간선과 정점 사이에 드는 비용
- ex. 1번 노드와 2번 노드까지 가는 비용이 한 칸? 가중치도 한 칸
2) 트리
- 그래프의 하위 항목
- 부모, 자식 계층 구조를 가짐(같은 경로상에서 어떤 노드보다 위에 있으면 부모, 아래에 있으면 자식)
- 간선 수 = 노드 수 -1(E = V -1)
- 임의의 두 노드 사이의 경로는 유일무이하게 존재함(루트 노드가 있으니 당연함)
- 루트 노드, 내부 노드, 리프 노드로 이루어짐
- 루트 노드 : 가장 위에 있는 노드
- 리프 노드 : 자식 노드가 없는 노드(tree니까 leaf node는 최말단인 것)
- 깊이(레벨) : 각 노드마다 다름. 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리
- 높이 : 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리
- 이진 트리 : 자식의 노드 수가 두 개 이하인 트리.
- 정이진 트리, 완전 이진 트리, 변질 이진 트리, 포화 이진 트리, 균형 이진 트리 등이 있음
- 이진 탐색 트리(BST) : 오른쪽 하위 트리에는 '노드 값보다 큰 값'이, 왼쪽 하위 트리에는 '노드 값보다 작은 값'이 들어 있는 트리
- AVL 트리 : 두 자식 서브트리의 높이는 항상 최대 1만큼 차이(최악의 경우 선형 트리가 되는 것을 방지하는 것)
- 레드블랙트리 : '모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다' 등의 규칙을 기반으로 균형을 잡는 트리. 색상을 나타내는 추가 비트를 저장함
- => 트리의 종류가 상당히 많은데, 전부 세세하게 아는 것보다는 각 트리가 만들어진 이유를 아는 게 중요할 듯 하다. 결국은 전부 시간 복잡도를 줄이기 위해 만들어진 개념인 것 같음. 어떤 상황에 어떤 방식으로 대처하면 되는지 경험적으로 알아보기.
3) 힙
- 완전 이진 트리 기반의 자료 구조. 최소힙과 최대힙이 있음.
- 최소힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 제일 커야함
- 최대힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 제일 작아야 함
- => 여기서 만약 특정 요소가 들어왔다? 일단 완전 이진 트리니까 제일 왼쪽부터 채우고, 최소힙이냐 최대힙이냐에 따라 각 노드를 스왑함
4) 우선순위 큐(우선순위 대기열)
- 우선 순위가 높은 요소가 우선 순위가 낮은 요소보다 먼저 제공되는 자료 구조
- 힙을 기반으로 구현됨
- 브라우저의 이벤트 루프가 이렇게 되어 있었던 것 같음(*찾아보기)
5) 맵
- 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조(항상 정렬을 보장하진 않음)
- 레드 블랙 트리 자료 구조를 기반으로 형성
- 해시 테이블을 구현할 때 사용
- => 특정 자료 구조를 기반으로 다른 자료 구조를 만드는 경우가 빈번하다. 각 자료 구조의 특징과 왜 다른 자료 구조가 만들어졌는지도 찾아보면 좋을 것 같다.
6) 셋
- 순서가 없고 희소한 값만 저장함(배열과 다른 점)
7) 해시 테이블
- 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블
- unordered_map으로 구현함
=> 선형 자료 구조의 경우 많이 찾아봐서 이해가 조금 되는데, 비선형 자료 구조의 경우에는 아직 와닿지는 않는 것 같다. 각각의 자료 구조를 따로 포스팅하든지, 더 찾아 보든지 해서 이해도를 높여야겠다. (*참고)
G는 무슨 G?