회고록(19) - 트리, 그래프, 이진탐색트리

1. 데일리 일기

코플릿 문제들을 풀어보면서 남은 시간에 백준 문제좀 풀어보려했는데, 입출력에서 시간을 엄청 썼다. EOF 라는 개념을 몰라서 꽤나 고생했던 것 같다..

요즘 자료구조관련 문제를 풀면서 느끼는게 문제를 처음 봤을때, 수도코드로 디테일하게 작성해놓을 수록 코드 작성하기도 편하고 피로감도 준다는 느낌을 받았다. 결국 모든 문제들은 다 작은 문제들을 쪼개서 보면 되는 것이다. 잘 해결해 보자.

2. 오늘 배운 내용

(브레인 스토밍 후, 핵심 내용들을 요약해서 작성하자. 절대 복붙 X, 나만의 단어로 표현하기.)

오늘은 데이터를 묶어놓은 자료구조중 트리, 그래프, BST를 배웠다.

트리

정의

나무를 뒤집어 놓은 모양처럼 한 노드가 있고, 작은 노드들이 사방으로 뻗어있는 있는 구조이다.

특징

• 데이터에 무방향으로 연결된 계층형 구조이다.(비선형구조)
• 노드와 간선으로 구성되어 있다.
  • 부모노드
  • 자식노드
  • 형제노드(sibling)
  • leaf 노드
• 깊이(depth) : root 노드를 기준(0)으로 특정한 노드까지의 길이를 말한다. 간선의 개수라고 볼 수도 있겠다.
• 레벨(level) : root 노드를 Level = 1로 두며, 같은 깊의 노드를 가진 계층을 레벨이라고 부른다. 이때 같은 노드들은 형제 노드라고 부른다.
• 높이(Height) : leaf노드를 기준으로 루트나 부모 노드까지의 높이를 나타낼수 있다. 여러 개의 리프노드로 인해 높이가 겹칠때는 더 큰값을 우선으로 한다.

활용 예제

파일 디렉토리, 우리가 사용하던 패키지의 자료구조로 사용된다.

그래프

정의

여러 개의 정점들이 서로 복잡하게 연결되어 있는 자료 구조를 말한다.

구조

하나의 점을 정점(Vertax) 라고 부르고 점들끼리 연결된 선을 간선(Edge) 라고 부른다.

정점들은 하나의 간선으로만 이어진 직접적인 관계를 가질수 있고, 여러 점들과 선들로 인해 연결된 간접적인 관계도 가질 수 있다.

표현 방식

그래프를 표현하는 여러 방식이 있지만, 이번 교육에서는 두가지를 다루었다.

인접하다라는 의미는 점과 점이 직접적인 관계(간선1개)로 연결 되어 있다는 의미이다.

(1)인접행렬

• 인접한 점들을 2차원 배열로 표현할 수 있다.
  • 2차원 배열의 값을 1로 아닌 다른값으로 하면 가중치를 줄 수 있다.
• 각 정점들을 배열 인덱스에 파싱하여 [from] -> [to] from 과 to 사이에 간선이 있음을 알려줄 수 있다.
  • 단방향과 (무)양방향 그래프를 표현 할 수 있다.
• 주로 가장 빠른 경로를 찾을때 사용된다.

(2)인접 리스트

• 각 정점마다 연결된 정점들을 리스르를 통해 넣어줄 수 있다.(ex) ArrayList<ArrayList>> )
• 인접행렬은 연결 가능한 모든 경우를 행렬에 나타내야한다. 리스트는 연결된 부분만 리스트로 나타내면 되므로, 메모리를 아낄 수 있다.

활용 예제

실제 네비게이션, 검색엔진, SNS 친구 찾기 기능들에 사용되는 자료구조 입니다.

BST(Binary Search Tree)

자료 묶음을 전시하는 목적 외에 효율적으로 탐색하기 위해 자료구조를 사용하기도 합니다. 탐색을 위한 트리구조들은 아래와 같습니다.

이진 트리

각 부모노드(루트노드 포함)를 기준으로 최대 두개의 노드를 가지는 트리를 말한다.

종류

자료의 삽입과 삭제에 따라 아래 3가지로 나뉜다.

• 정 이진 트리(full binary tree)
• 포화 이진 트리(Perfect ~)
• 완전 이진 트리(Complete)

이진 탐색 트리

모든 왼쪽노드가 부모노드보다 작고, 모든 오른쪽 노드가 부모노드보다 큰 특징을 가지는 트리입니다.

특징

• 전위 순회, 중위 순회, 후위 순회 방식으로 순회할 수 있습니다.
• 이전 이진 트리에서 말했듯이 입력되는 값들의 삽입순서에 따라서 한쪽으로 쏠리는 트리구조가 될수 있습니다. 이렇게 균형이 잡히지 않는 트리는 탐색하는데 시간이 더 오래 걸리기때문에, 삽입과 삭제마다 트리의 구조를 재구성 해주는 알고리즘도 존재합니다.

3. 새로 알게 된 내용

진입 차수, 진출 차수 : 한 정점에 진입하고 진출하는 간선의 수를 나타냅니다.

deepToString() : 다차원 배열 또는 다차원 컬렉션의 ToString을 배열 해시값이 아닌 요소를 출력하도록 해줍니다.

ArrayList.subList(from, to) : from<= <to 의 범위로 ArrayList를 잘라줍니다.

PrintWriter : 스트림을 이용해 출력해주는데, 해당 Writer 스트림은 println(), printf() 등 오버로딩된 메서드들이 구현되어 있습니다.