22.08.16_TIL

📌 페어를 하는 마지막 시간이자 실제 프로젝트를 들어가기 전 마지막 학습 단계인 만큼 열심히해야 겠다. 또한, 내일은 CRUD를 직접 만들게 되는데 REACT 학습을 처음 시작했던 Section2에서 이미 한번 스터디원들과 함께 각자만의 CRUD를 제로부터 해봤기 때문에 걱정보단 어떤것을 만들면 좋을까(?)에 대한 고민이 되는 날이다. '스터디하자'라는 프로젝트를 스터디원 두명과 같이 진행을 했는데 무언가 믿고 따라와준 만큼 작은 보답을 하고 싶다!!

📗 오늘 학습한 내용

Tree

• 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태의 구조
• 하나 이상의 데이터에 한 개의 경로와 하나의 방향으로만 연결된 계층적 자료구조이다.
• 아래로만 뻗어나가기 때문에 시작 노드에서 출발하여 다시 출발 노드로 돌아오는 사이클이 없다.

Tree의 구조

• 루트(Root): 하나의 꼭짓점 데이터 시작 노드이며 여러개의 데이터를 간선(edge)으로 연결한다.
• 노드(Node): 데이터이며 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가진다.
• 깊이(depth): 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있다.
• 레벨(Level): 같은 깊이를 가지고 있는 노드를 묶어서 레벨이라고 한다. 같은 레벨에 나란히 있는 노드를 형제노드라고 한다.
• 높이(height): 리프 노드를 기준으로 루트까지의 높이를 표현할 수 있다.
• 서브 트리(Sub tree): 트리 구조를 갖춘 작은 트리를 서브 트리라고 한다.
• 리프(Leaf): 트리 구조의 끝 지점이고, 자식 노드가 없는 노드이다.

Tree의 실사용

• 컴퓨터의 디렉터리 구조, 월드컵 토너먼트 대진표, 가계도(족보), 조직도 등이 있다.

이진 트리(Binary tree)

• 자식 노드가 최대 두 개인 노드들로 구성된 트리이다.
• 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binery tree), 포화 이진 트리(Perfect binary tree)로 나뉜다.

이진 트리 특징

• 정 이진 트리(Full binary tree): 각 노드가 0개 혹은 2개의 자식 노드를 갖는다.
• 포화 이진 트리(Perfect binary tree): 정 이진 트리이면서 완전 이진 트리인 경우이다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리이다.
• 완전 이진 트리(Complete binary tree): 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.

이진 탐색 트리(Binary Search Tree)

• 이진 탐색과 연결 리스트를 결합한 트리이다.
• 이진 탐색의 효율적인 탐색 능력을 유지하면서 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다.

이진 탐색 트리 특징

• 각 노드에 중복되지 않는 키가 있다.
• 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.
• 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.
• 좌우 서브트리도 모두 이진 탐색 트리이다.

이진 탐색 트리 탐색 과정

1. 루트 노드의 키와 찾고자 하는 값을 비교한다. 만약 찾고자 하는 값이라면 탐색을 종료한다.
2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다.
3. 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행한다.

트리를 순회하는 방법

• 전위 순회(preorder traverse)
  • 가장 먼저 방문하는 노드는 루트이며, 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색한다. 부모 노드가 제일 먼저 방문되는 순회 방식이다.
  • 주로 부모 노드가 먼저 생성되어야 하는 트리를 복사할 때 사용하게 된다.
• 중위 순회(inorder traverse)
  • 루트를 가운데에 두고 순회한다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하며, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색한다.
  • 부모 노드가 서브 트리의 방문 중간에 방문되는 순회방식이며, 이진 탐색 트리의 오름차순으로 값을 가져올 때 쓰인다.
• 후위 순회(postorder traverse)
  • 루트를 가장 마지막에 순회하며 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문한다.
  • 트리를 삭제할 때 사용하며 자식 노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있다.

Graph의 정의

• 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다.

Graph의 구조

• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.
• 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다.
• 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge)라고 한다.

Graph의 표현 방식

• 인접 행렬
  • 두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다고 하며, 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다.
• 인접 리스트
  • 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현하며, 각 정점마다 하나의 리스트를 가지고 있다.
  • 이 리스트는 자신과 인접한 다른 정점을 담고 있다.

Graph의 실사용 예제

• 포털 사이트의 검색 엔진, SNS에서 사람들과의 관계, 내비게이션 등에서 사용하고 있다.

BFS(Breadth-First Search)

• 너비를 우선적으로 탐색하는 방법이며, 너비 우선 탐색이라고 한다.
• 주로 두 정점 사이의 최단 경로를 찾을 때 사용한다. 만약, 경로를 하나씩 전부 방문한다면, 최악의 경우에는 모든 경로를 다 살펴보아야 한다.

DFS(Depth First Search)

• 깊이를 우선적으로 탐색하는 방법이며, 깊이 우선 탐색이라고 한다.
• 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용 한다.
• BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있다.

📘 추가로 공부할 내용

Study원과 함께 진행중인 프로젝트 구현

나만의 포트폴리오 사이트 구현  해보기

pre-project 관련 사이트 찾아보기

📝 중요한 내용

• 트리
• 이진 트리
• 그래프
• BFS
• DFS