4. 자료구조

1️⃣ 복잡도

- 시간 복잡도: 알고리즘의 실행 시간을 정량화하는 것

- 공간 복잡도: 알고리즘 실행시 필요한 메모리 사용량을 정량화하는 것

- 빅오 표기법: 입력 값에 대한 수식에서 최고차항을 기준으로 알고리즘이 수행되는 최악의 시간 복잡도를 표현

2️⃣선형 자료구조와 비선형 자료구조의 차이

- 선형 자료구조: 연속적으로 데이터가 나열되는 자료구조. 1:1 연결

- 비선형 자료구조: 하나의 데이터 뒤에 n개의 데이터가 이어질 수 있는 자료구조. 1:N, N:N 연결

3️⃣ 선형 자료구조 - 배열

- 정해진 크기만큼 데이터가 일렬로 저장되는 정적 자료구조

- 요소: 배열의 각 데이터 / 인덱스: 데이터를 가리키는 번호

- 시간 복잡도

  (1) 검색: O(n)

  (2) 삽입: O(n) (but 여유공간이 있고, 맨 마지막 삽입시 O(1))

  (3) 삭제: O(n) (마지막 데이터 삭제면 O(1))

4️⃣ 선형 자료구조 - 연결 리스트

- 여러 개의 노드로 구성 -> 배열과 달리 크기가 정해져있지 않은 동적 자료구조

- 노드는 데이터 + 다음 노드 주소 값으로 구성되어 있음

- 헤드 포인터와 테일 포인터로 시작과 끝을 알 수 있음

- 시간 복잡도

  (1) 검색: O(n)

  (2) 삽입: O(n) (but 맨 앞 삽입시 O(1)) -> 데이터를 추가하려는 위치로 이동해야하므로! 데이터 추가하는 연산 자체는 이전 노드가 가리키는 노드의 주소 값만 변경하면 되므로 O(1)  

  (3) 삭제: O(n) (but 맨 앞 삭제시 O(1)) -> 데이터를 추가하려는 위치로 이동해야하므로! 

👍장점: 배열과 달리 삽입시 기존 노드들의 위치 변경X -> 시간 효율적

👎단점: 배열과 달리 인덱스X -> 특정 위치 데이터 접근시 시간 비효율적

+ 이중 연결 리스트(앞 노드의 주소 값+다음 노드 주소 값 모두 저장) -> 양방향 탐색 가능으로 연속 탐색시 시간 효율적 but 구현 어렵고 메모리 많이 차지

+ 원형 연결 리스트(마지막 노드가 null이 아닌 첫 번째 노드의 주소 값을 가리킴)

5️⃣ 선형 자료구조 - 스택

- 데이터를 쌓는 형태. LIFO(후입선출)

- push(스택의 가장 위에 데이터 저장) <-> pop(스택의 가장 밑 데이터 삭제)

- top이라는 변수로 데이터를 마지막으로 저장한 인덱스 기억 -> 연산 포함 항상 O(1)으로 마지막 데이터 접근 가능!

- ex) 실행 취소, 웹 브라우저에서 뒤로가기

6️⃣ 선형 자료구조 - 큐

- 데이터가 순차적으로 들어오는 형태. FIFO(선입선출)

- front(맨앞), rear(맨뒤) 개념을 이용해 삽입, 삭제시 시간 복잡도를 줄임

- 인큐(enqueue): 삽입시 큐의 맨 뒤에 삽입 <-> 디큐(dequeue): 삭제시 큐의 맨 앞에서 삭제

- ex) 프로세스가 CPU를 할당받기 전까지 대기하는 준비 큐. 작업 요청이 들어온 순서대로 처리하는 경우

7️⃣ 비선형 자료구조 - 그래프

- 데이터를 포함하는 정점(=노드)과 정점을 잇는 간선으로 구성된 자료구조

- 차수: 정점에 연결된 간선의 수 / 진입 차수: 해당 정점으로 향하는 간선의 수 / 진출 차수: 해당 정점에서 나가는 간선의 수

- 간선의 방향성 유무에 따라 무방향 그래프와 방향 그래프로 나뉨

- BFS(너비 우선 탐색): 탐색을 시작하는 정점에서 가까운 정점을 먼저 탐색. 인접한 정점들을 큐에 모두 삽입하는 방식으로 진행. 중복 방지하기 위해 방문처리 꼭 해줘야함

- DFS(깊이 우선 탐색): 탐색을 시작하는 정점에서 탐색 가능한 최대 깊이의 정점까지 탐색. 최대깊이 도달하면 방문했던 정점들을 역순으로 재방문->탐색 가능한 정점에서 또 최대깊이까지 탐색. 재귀or스택으로 구현

8️⃣ 비선형 자료구조 - 트리

- 그래프의 한 종류로, 사이클이 없어서 계층적 관계 표현 가능

- 이진 트리: 자식 노드가 최대 2개인 트리

    (1) 완전 이진 트리: 마지막 레벨은 제외 모든 레벨에 노드 있음 + 마지막 레벨은 노드가 왼쪽에서 오른쪽으로 채워져있음

    (2) 포화 이진 트리: 마지막 레벨까지 노드가 모두 채워져 있음

    (3) 이진 탐색 트리: 한 노드의 왼쪽 서브트리는 해당 노드의 값보다 작은 값 + 오른쪽은 큰 값을 가진 노드로 구성

        -> 균형 이진 탐색 트리에서는 루트 노드와 가까운 노드일수록 검색해야 하는 노드 개수가 절반으로 줄어듦! 

9️⃣ 비선형 자료구조 - 우선순위 큐 & 힙

 - 우선순위가 높은 데이터가 먼저 나오는 자료구조

- 구현하는 방식은 배열, 연결 리스트, 완전 이진 트리인 힙 -> 힙이 가장 효율적!

- 힙: 완전 이진 트리. 최댓값 or 최솟값을 빠르게 찾을 수 있음! 

- 최대 힙(부모 노드의 값이 자식 노드의 값보다 크거나 같음) <-> 최소 힙

    (1) 삽입 연산: 힙의 맨 끝에서 데이터 삽입 -> 부모 노드와 우선순위 비교해 위치를 바꾸며 루트 노드까지 비교

    (2) 삭제 연산: 우선순위가 가장 높은 루트 노드 삭제 -> 루트 노드 자리에 마지막 노드를 옮긴 후 재정렬

🔟 비선형 자료구조 - 해시 테이블

- 하나의 키에 대해 하나의 값을 저장하는 형태의 자료구조

- 키는 해시 함수를 이용해 해시를 얻을 수 있음

- 해시: 값이 저장되어 있는 해시 테이블의 인덱스를 찾을 수 있는 값

- 해시 함수에 키를 넣으면 해시 테이블에서 매칭되는 결과 값에 한 번에 접근할 수 있음! -> O(1)

- 해시 충돌: 서로 다른 키에 대해 같은 해시가 도출되는 것

- 해시 충돌 해결 방법

                        (1) 체이닝: 같은 해시가 나오는 키의 값을 연결 리스트에 저장하는 방식. 저장 공간에 대한 제약이 적음 but                                             하나의 해시(인덱스)에 노드가 몰릴 수 있음!

                        (2) 개방 주소법: 해당 해시가 아닌 비어 있는 공간에 값을 저장하는 방식

                               a. 선형 조사법: 다음 인덱스로 이동하며 빈 공간을 찾음. -> 특정 인덱스 범위에 데이터가 몰리는 현상!

                               b. 이차 조사법: 거듭제곱한 인덱스만큼 이동하며 빈 공간을 찾음 -> 선형보다 군집화 현상이 적음

                               c. 이중 해싱: 해시 충돌 발생 시 다른 해시 함수를 한 번 더 적용