혼자공부하기

트리 순회에는 4가지가 있다.

전위순회(Preorder Traversal)

VLR이며 ABDECFB순으로 방문한다.

중위순회(Inorder Traversal)

LVR이며 DBEAFCG순으로 방문한다.

후위순회(Postorder Traversal)

레벨순회(Levelorder Traversal)

트리는 노드로 이루어진 비선형 자료구조이며 계층적이다.

루트 노드(root node) : 최상위 노드를 의미하며 A가 루트 노드

단말 노드(leaf node) : 자식이 없는 노드를 의미하며 D,E,F가 단말 노드

간선(edge) : 노드 사이 연결해주는 직선을 의미

내부 노드(internal node) : 단말 노드가 아닌 노드를 의미하며 A,B,C가 내부 노드

형제(sibling) : 같은 부모를 가지는 노드를 의미 하며 B와C, D와E가 형제이다.

높이 : 루트노드부터 가장 밑의 노드까지의 깊이를 의미 하며 위의 트리는 level 2이다.

트리의 차수 : 노드 중 가장 많은 자식을 가진 노드의 갯수를 의미하며 위의 트리는 2이다.

자료구조는 선형구조(Linear)와 비선형구조(Non Linear)이 있습니다.

선형구조는 데이터를 순차적으로 나열시킨 것을 의미합니다.

ex) 스택, 큐, 덱, 배열, 연결리스트

비선형구조는 데이터 뒤에 여러개의 데이터가 존재할 수 있는 것을 의미합니다.

ex) 그래프, 트리

최근에 연산자 우선순위 문제를 접하였다..

,의 우선순위를 물어보았다.. 그래서 정리한다.

DV와 Link State를 공부하다가 위의 둘 알고리즘에 대해 복습을 한다. 필자의 기억에 의하면 자료구조 6장 그래프에 나왔던 것으로 기억한다.

가장 큰 차이점은 다익스트라는 음의 가중치를 가질 수 없고 벨만포드는 음의 가중치를 가질 수 있다.

다음 그림으로 위의 알고리즘을 간단히 설명한다.

위의 그림에서 B의 위치에서 다익스트라 알고리즘은 D로 갈려면 D로 바로가면 20 C를 거치게 되면 40+알파인데 현재 가중치의 값으로 결정을 해서 B->D를 선택하게 된다.

하지만 벨만포드는 음의 가중치를 가질 수 있기 때문에 끝가지 돌아보고 나서 B->C->D를 선택하게 된다.

한 방향에서 자료의 입력과 출력이 이루어지는 자료구조이며 LIFO(Last In First Out)라고 불린다. 

ex) 함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법

한 방향에서는 자료의 입력이 이루어지고, 반대편 방향에는 자료의 출력이 이루어지는 자료구조이며 FIFO(First In First Out)라고 불린다.

ex) 버퍼

자료의 입력과 출력을 양 쪽 끝에서 가능하게 하는 자료구조

• 스크롤(Scroll) : 입력이 한쪽에서만 가능하도록 제한한 덱
• 셀프(Shelf) : 출력이 한쪽에서만 가능하도록 제한한 덱