Chap 2. 자료구조
렛츠고!
1 ) 자료구조의 분류
- 선형 자료구조 : 데이터가 일렬로 나열된 형태
- 배열
- 연결 리스트 -> cpp에선 vector, deque .. ?
- 스택 -> pointer 사용
- 큐 -> pointer 사용시 메모리 고려
- 비선형 자료구조 : 데이터가 특정한 (일렬이 아닌) 형태를 띄고있음
더 자세히 렛쯔고
2 ) 배열
특징 ?
- 데이터 접근 용이
- 데이터 삽입 삭제 비교적 어렵
- 구조 간단함. 프로그램으로 작성하기 쉬움
(CPP로 구현시, 크기가 고정된 상태라면 배열 활용하지만, 아닐땐 벡터 사용을 추천)
3 ) 연결 리스트
: 각 노드가 데이터 & 포인터를 가진 형태. 일렬로 연결되어 데이터 저장
특징 ?
- 배열과 반대되는 특징 가짐
- 데이터의 접근 느림
- 데이터 삽입 삭제 편함 (push, pop)
- 포인터를 위한 추가 공간 필요. 프로그램 작성 비교적 어렵
(~=> 벡터)
4 ) 스택
특징 ?
- 삽입/삭제가 한방향에서 이뤄지는 선형 자료구조
- LIFO
- Top : 스택에 데이터가 삽입될 위치
5 ) 큐
특징 ?
- 삽입/삭제의 방향 반대. 선형 자료구조
- FIFO
- Front / Head : 데이터가 삭제될 위치
- Rear / Tail : 데이터가 삽입될 위치
- Deque 덱 : 양 방향에서 삽입/삭제가 모두 이루어지는 큐
(삭제 : pop/dequeue, 삽입 : push/enqueue)
6 ) 트리
용어
- 조상 노드 : 해당 노드의 부모부터 루트까지의 경로에 존재하는 노드들 (-> LCA 최소 공통 조상)
- 루트 노드 ( -> 유니온 파인드(동맹찾기) / 서로소 집합 문제 등에 활용)
- 깊이 Depth : 루트에서 해당 노드까지의 간선 수. 루트의 깊이는 0
- 레벨 Level : 깊이 + 1
- 노드의 차수 Degree : 자식 수 ( -> Indegree / Outdegree )
- 트리의 차수 : 해당 트리 내 모든 노드의 차수 중 최댓값
- 내부 노드 : 자식이 있는 노드 ( internal / nonterminal )
- 외부 노드 = 단말노드 = 잎새노드
- 높이 Hight : 루트에서 해당노드까지 지나간 정점 개수 => 트리의 높이 = 노드 높이 중 최댓값
7 ) 이진 트리 Binary Tree
: 노드의 차수 <= 2
특징 ?
- 높이가 N일때, 최대 노드 갯수 = 2^N - 1 개
노드 탐색을 lgN으로 만들고 싶을때 유용
- segment tree를 떠올려보자
- 이진 트리의 종류 (그러려니)
- 정 이진 트리
- 포화 이진 트리
- 완전 이진 트리
- 사향 이진 트리
- 이진 트리의 표현
- 연결 자료 구조 (연결리스트)
- 연속 구조 : 일차원 배열 ~= 인덱스드 트리
- 이진 트리의 순회
- for로 하는거 절대 아님 ㅋ
- 전위 순회 / 중위 순회 / 후위 순회 (그러려니) ; 다 루트에서 시작하는거 당욘 알지 ㅋ
- 이 중 전위 순회 ? 우리가 흔히 하는 일반적인 dfs 형식
8 ) 힙 : 이진트리의 응용
- 힙?
- 힙 조건 Heap Condition 을 만족해야함. 즉, 각 노드의 키 값이 자식노드의 키 값보다 커야함
- 일차원 배열로 구현
cpp에서, <queue> 헤더 인클루드 해서 priority_queue() 사용하면 최대힙 바로 구할 수 있음
- 활용 ?
- 힙정렬(Heap Sort)
- 입력된 데이터 안에서 최대/최소 값을 찾을 때
- 우선순위 큐
수행시간 : O(logN) - 데이터 삽입삭제 빠름
- 최대 힙 & 최소 힙 => 우선순위큐! (구조 암기)
- 최대힙 : 부모노드의 키 값이 자식노드의 키 값보다 항상 큼 => 루트노드가 트리 중 가장 큰 key값 가짐
- 최소힙 : 부모노드의 키 값이 자식노드의 키 값보다 항상 작음 => 루트노드가 트리 중 가장 작은 key값 가짐
- 자세한건 9번에서 ㅎㅎ 무튼 <queue> 헤더 인클루드해서 우선순위큐로 연산!
- 힙 삽입 연산
- 힙 삭제 연산
9 ) 우선순위 큐 ( Priority Queue ) : 힙의 활용
- 우선순위 큐 ?
- 각 데이터에 우선순위 부여. 큐에 넣은 데이터 꺼낼 때 우선순위 높은거 먼저 꺼내자
- 삽입시, 데이터에 우선순위 지정하여 큐로 추가 pq.push()
- 제거시, 큐에서 우선순위 젤 높은 데이터를 반환하고 제거 pq.top() + pq.pop()
- #include <queue>
10 ) 인덱스 트리 ( Indexed Tree ) : 이진트리의 활용
- 인덱스드 트리 ?
- 시간복잡도 O(MlogN)
- 포화 이진트리 형태
- 리프노드 : 배열에 적혀있는 수
- 내부노드 : 두 자식의 합
- 제거시, 큐에서 우선순위 젤 높은 데이터를 반환하고 제거
11) 해싱 Hashing
- 해싱 ?
- 입력된 데이터(key)를 해시함수를 통해 얻은 주소로 그 위치를 직접 참조
- 일반적으로 O(1)의 시간복잡도 => query 실행 많을때 유용
- iterator는 auto로 하기
12) 그 외
- 트라이 Trie (그러려니)
- 셋 Set : 노드의 갯수와 관련해서 유용할때가 있음
- 맵 Map : 몇 종류 있지만, 해쉬맵을 추천 !
하핫 내용이 많아서 오래걸렷음 흑흑 대충 쓴 감이 없잖아 있지만 .. 공부ㅎㅏ는건 나니까 하핫 일단 가독성 포기하고 정리정리