31일차 TIL 210415

1. 그래프란?

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

• 직접적인 관계를 가지고 있다면, 바로 이어주는 선이 존재하고, 간적접인 관계를 가지고 있다면 다른 여러점을 거쳐서 이어지는 선이 존재할 수 있다.
• 어떠한 간선으로도 연결되지 않는다면 그 점들은 관계가 없다고 말할 수 있다.
• 정점(vertex), 간선(edge)
• 무향 그래프(undirected graph) : 간선에 방향이 없는 경우
• 진입차수(in-degree) / 진출차수( out-degree) : 한 정점에 진입하고 진출하는 간선의 수
• 인접(adjacency) : 두 정점간의 간선이 직접 이어져있다면 인접한 정점이다.
• 자기 루프(self loop) : 정점에서 진출하는 간선이 곧바로 자기자신에게 진입하는 경우(다른 정점을 거치지 않는다)
• 사이클(cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있는 경우

1-1. 그래프의 표현 방식 : 인접행렬(Matrix)

• 두 정점이 이어져있다면 1 아니라면 0으로 표시하는 일종의 표같은 방식

• 두 정점 사이에 관계가 있는지, 없는지 확인하는데 용이하다.
• 가장 빠른 경로를 찾고자 할떄 주로 사용됨.

1-2 그래프의 표현 방식 : 인접리스트

• 각 정점이 어떤 정점과 인접한지 리스트의 형태로 볼 수 있는 표현 방식

• 순서는 중요하지 않다.
• 메모리를 효율적으로 사용하고 싶다면 인접행렬 다시 인접 리스트를 사용한다.

2. 트리

• 데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결되는 계층적 자료구조…뭔소리야?
• 거꾸로된 나무와 비슷한 구조이다. 하나의 뿌리로부터 가지가 사방으로 뻗은 형태를 가지고있다.

• 루트 라는 하나의 꼭지점 데이터를 시작으로 여러개의 데이터를 간선으로 연결한다. 이 데이터들을 노드라고 하고, 상위노드와 하위노드가 연결되면 부모/자식 관계를 가지게 된다.

• 이 자료구조는 높이와 깊이를 측정할 수 있다.
• 트리 실사용 예제 : 컴퓨터의 디렉토리 구조, 가계도, 조직도, 대진표

3. Binary Search Tree

• 자식노드가 최대 두 개인 노드들로 구성된 트리를 이진 트리라고 한다. 왼쪽 자식과 오른쪽 자식으로 분류한다.
• 모든 왼쪽 자식들은 루트나 부모보다 작은 값이고, 모든 오른쪽 자식들은 루트나 부모보다 큰 값인 특징을 가지고 있는 트리를 이진 탐색 트리라고 한다.

4. 디버깅의 중요성

• 내가 디버깅이 되고, 디버깅이 내가 되는 경지에 이르렀을때 문제가 풀리더라..
• 콘솔 찍어보고 디버깅 돌려보고!! 답은 그것밖에 없다!