Today I learned
- Graph
- Tree
- Binary Search Tree
@@ 오늘 자료구조 구현 part 3번째 그래프, 트리, 이진탐색트리를 학습하는 날이다. 음 우선 세번째 정도 하다보니 구현에 대한 의미와 구현 전 내가 알아야 할 개념에 대해 명확하다보니 좀 더 빠르게 레슨도 진행하고 구현도 진행할 수 있었다.
재귀 함수를 이용해서 사고하는 것이 익숙하지 않아서, 메서드 안에서 생성자 함수를 통해 인스턴스를 생성하고 하위 노드에 생성한 인스턴스를 집어넣고, 다시 인스턴스 메서드를 사용하는 것이 바로 이해가 가진 않았다.
그래도 페어분과 이야기를 주고받으며 진행하다보니 어려워보였던 것도 차근차근 진행이 돼서, 내일 마감 시간 안에 과제를 마무리할 수 있을 것 같다 ( 물론 숨겨진 복병이 있을지도 모르지만 )
이번 스프린트를 진행하며 정말 어느때보다 디버깅을 열심히 하고, 콘솔을 미친듯이 찍어본 것 같다. 콘솔에 너무 의존하는 것도 좋지 않은 습관 같지만, 막힐 때나 감이 오지 않을 때 찍어보고 확인하며 돌다리 두들기는 게 내 생각엔 도움이 많이 되는 것 같다. 내 생각과 다른 반환 값, 변수값 등을 보면서 몰랐던 부분을 많이 깨닫는다.
이번주는 자료구조 책 서적들을 병행 하며, 시간 복잡도 및 자료구조 복습에 만전을 기해야겠다. 그래도 오늘 해시 테이블만큼의 충격은 다행히 없었다.
Graph
- vertex or Node
- 인접 버텍스
- edge
- 진입 차수(indegree) / 진출 차수 (outdegree)
- 무방향 그래프 / 양방향 그래프
- 데이터 구조의 자유로움
- selp loop
- cyclic graph
- 가중치 그래프
- 완전 그래프 (오일러 경로)
- 그래프 구현 방법
- 인접행렬 (공간복잡도 V^2)
- 2차원 배열에 모든 버텍스의 연결 관계를 담는 방식.
- vertex는 추상화로 나타나지 않는다 간선 연결 정보만 담긴다
- 0과 1을 이용한 정수 행렬로 표현할 수 있다.
- 버텍스를 잇는 엑싲 여부를 O(1)으로 찾을 수 있다.
- 그래프 간에 간선이 많은 그래프일 때 좋다.
- 인접리스트 (공간복잡도 V+E)
- 인접 노드를 쉽게 찾을 수 있다.
- 모든 간선의 수를 O(V+E) 안에 알 수 있다.
- 무방향에선 양 쪽 모두 다 저장해야 서로 이어진다.
- 버텍스에 대한 탐색을 자주할 때 인접 리스트를 사용한다.
- 인접행렬 (공간복잡도 V^2)
- DFS, BFS
Tree
- 노드로 구성된 계층적 자료구조
- 재귀적
- Tree의 높이와 깊이
- 노드
- root
- sibling
- child
- parent
- edge
- leaf
- 트리의 종류
- 이진 트리, 이진탐색트리, 힙트리
- 완전 이진트리, 정 이진트리, 포화 이진트리
- 전위순회, 중위 순회, 후위순회
Binary Search Tree
-
최대 2개의 자식만 갖는 이진 검색을 사용하는 트리 구조
-
노드의 왼쪽 서브트리엔 노드의 값보다 작은 값이, 오른쪽 서브트리엔 노드의 값보다 같거나 큰 값이 존재.
-
DFS (깊이 우선 탐색), BFS (너비 우선 탐색)
-
DFS는 재귀로 움직일 수 있고 BFS 는 움직일 수 없다.
-
DFS는 스택 사용
-
BFS 는 큐 사용
-
전위,중위,후위 순회
- 재귀함수를 통한 사고
-
완전 이진트리, 정 이진트리, 포화 이진트리
