Coding Warehouse

1. Tree

자료구조 중 Tree는 이름 그대로 나무의 형태를 가진 자료구조를 말합니다. 이 트리는 부모-자식 관계로 정의하고, 부모에서 자식으로 간선이 이어져 있는 단방향 그래프를 말합니다.

1.1 Tree 용어설명

• 노드 : 트리를 구성하는 각 원소로 그림에서는 (A), (B), (C) ,(D), ... (I) 가 된다.
  • 루트 노드(root node): 트리에서 최상단에 존재하는 노드로 부모가 없다.  : (A)
  • 부모 노드(parent node): 어떤 노드에서 위 방향으로 연결된 다른 노드를 말한다. : (A)는 (B)의 부모노드
  • 자식 노드(child node): 부모 노드의 반대되는 개념이다. : (B)는 (A)의 자식 노드이다.
  • 형제 노드(siblings node): 같은 부모노드에서 연결된 노드들을 말한다 : (B)와 (C)는 형제노드이다.
  • 리프 노드(leaf node): 나무의 잎을 말하는 '리프'인데 자기 자식이 존재하지 않는 노드를 말한다. : (F)와 (G)
• 간선 : 노드와 노드를 연결해주는 선을 말하며 Tree에서는 단방향이다.
• 길이(length) : 출발에서 시작까지 거쳐간 간선의 길이.
• 깊이(depth) : 루트에서 부터의 어떤 노드까지의 길이.
• 높이(height): 어떤 노드에서부터 루트까지의 최대길이.
• 차수(degree) : 한 노드가 가지고있는 자식의 개수.
• 서브트리 (Sub tree): 원래의 트리 내부에 트리구조를 갖춘 작은 트리 일부를 말한다.

1.2 이진 트리(Binary Tree)

: 이진트리는 트리구조의 형태 중에서 자식노드가 최대 2개로 제한된 트리형태를 말합니다. 보통 이진트리의 자식노드를 말할 땐, 왼쪽 자식노드와 오른쪽 자식 노드라고 부릅니다. 이러한 이진트리는 보통 효율적인 탐색을 위해 사용됩니다.

1.2.1 이진 트리의 종류

• 정 이진트리(full binary tree) : 모든 트리의 자식이 0개이거나 2개 일때.
• 포화 이진 트리(perfect binary tree) : 정 이진 트리를 만족하는 가운데,  리프노드를 제외한 모든 노드의 자식들이 2개를 가진 경우이다. 쉽게 생각해서 '포화'되었다는 말로 모든 노드에 2개씩 연결되어있다고 생각하면 좋다.
• 완전 이진 트리(complete binary tree) : 포화 이진트리는 리프노드를 제외한 모든 노드에 간선이 2개씩 있는 경우라면, 이 경우는 리프노드의 부모노드에선 1개의 간선만 존재하는 경우가 있는 트리를 말한다. 즉 포화 이진 트리는 완전 이진 트리의 부분집합(조건이 더 까다로운)이다.

1.2.2 이진 트리 순회 방법

• 전위 순회(pre-order traversal) : 8-3-1-6-4-7-10-14-13
• 중위 순회(in-order traversal): 1-3-4-6-7-8-10-13-14
• 후위 순회(level-orfer traversal):  1-4-7-6-3-13-14-10-8

• 전위 순회: 왼쪽 자손 , 자기자신, 오른쪽 자손  -> 이 세 순서를 지키면서 방문하는 방법
• 중위순회 : 자기자신, 왼쪽 자손, 오른쪽 자신 
• 후위 순회: 왼쪽 자손, 오른쪽 자손, 자기자신

2. Graph

: 이런 그래프의 형태가 우리가 흔히 생각하는 그래프의 형태이다. 하지만 앞으로 얘기할 그래프는 조금 다르다

우리가 앞으로 이야기할 그래프는 서로 거미줄 처럼 처럼 엮어진 네트워크 망처럼 생긴 형태를 뜻합니다.

2.1 Graph 용어정리

• Vertex: 그래프의 각 노드 입니다. 이 그림에서는 초록색 동그라미 안에 있는 0, 1, 2, 3, 4, 5, 6을 말합니다
• edge: 두개의 vertex사이를 연결하고 있는 선들을 말합니다. 이 그림에서는 검은색 선들을 이야기 합니다.
• Adjacency(인접) : 두개의 Vertex사이에 edge가 있어서 둘이 연결되어 있다면, 그 경우엔 두개의 vertex가 인접해 있다고 표시합니다. 여기서는 0과 1, 1과 2 그리고 1과3 등이 될 수 있습니다.  보통 이어져 있는 경우는 값은 1이라 두고 인접성이 없다면 0이라 표현합니다
  • 만약 인접을 표현하는 1이 다른 숫자 2,3,4등등 다른 값으로 표현 되는 경우엔 가중치그래프( weight Graph)라고 부릅니다.
• self loop(자기 루프) : 정점에서 출발한 edge가 자기 자신에게 돌아오는 경우에 self loop가 있다고 표현합니다.
• cycle(사이클) : 어떤 한 vertex에서 edge를 타고 떠난 다음에 다른 vertex와 edge를 거쳐 자기자신에게 돌아올 수 있다면 해당 그래프에는 cycle이 존재한다고 말합니다

Stack

후입선출(Last In First Out)특성을 가지는 자료구조(Data Structure)를 말한다.

내가 좋아하는 프링글스를 꺼내먹는것과 같은 형태이다 .. ㅎ

Stack의 특징

• LIFO(Last in First out)로 데이터를 저장 출력 할 수 있다.
• 데이터는 한개씩 넣고 뺄 수 있다.
• 입출력 방향이 한 개 입니다.

Stack 자료구조의 예시

• 앞서 말한 프링글스(각 감자칩==데이터)를 넣고 빼는 형태
• 우리가 문서작성을 할 때 사용하는 Ctrl +Z (Undo)도 Stack 형태이다. 해당 명령어를 실행하면 바로 직전의 상태로 돌아간다.
• 함수가 함수를 호출하거나 재귀함수도 스택에 기반해 데이터를 임시저장한다. 그리고 각 재귀를 빠져나오면서 데이터를 빼면서 참조한다.
• 웹 브라우저의 방문기록에 사용하는 '뒤로가기'버튼

Stack 관련 메서드

• push(): 스택의 상단에 데이터를 추가합니다
• pop(): 가장 나중에 추가된 데이터를 스택에서 삭제하고 삭제한 데이터값 리턴합니다
• size(): 스택 데이터의 크기를 리턴 합니다.
• peek(): 가장 나중에 추가된 데이터 값을 리턴합니다.
• show(): 스택 내 모든 데이터를 문자열로 변환하여 리턴합니다.
• clear(): 스택에 포함되어 있는 모든 데이터 삭제합니다.

Queue

선입선출(First In First Out)특성을 가지는 자료구조(Data Structure)를 말한다.

우리가 어디서 항상 줄 서  있는 바로 그 모습

Queue의 특징

• FIFO(First in First out)로 데이터를 저장 출력 할 수 있다.
• 데이터는 한개씩 넣고 뺄 수 있다.
• 입출력 방향이 두 개 입니다. 데이터의 입출력 방향이 다르기 때문에 같다면 Queue라고 볼 수 없습니다.

Queue 자료구조의 예시

• 한줄로 서서 티켓을 받아가는 형태 (티켓받는 순서 = 데이터 출력 순서)
• 고속도로에서 한줄로 나란히 가야만 하는 차들
• 컴퓨터 운영체제의 테스크 

Queue관련 메서드

• offer() : 큐의 가장 뒤에 데이터를 추가합니다.
• poll(): 가장 처음에 추가된 데이터를 큐에서 삭제하고 삭제한 데이터값 리턴합니다
• size(): 스택 데이터의 크기를 리턴 합니다.
• peek(): 가장 일찍 추가된 데이터 값을 리턴합니다(=poll로 리턴될 값).
• show(): 스택 내 모든 데이터를 문자열로 변환하여 리턴합니다.
• clear(): 스택에 포함되어 있는 모든 데이터 삭제합니다.