12.16

홍왕열·2021년 12월 16일

queue stack 자료구조

STACK

stack이란 data를 순서대로 쌓는 자료구조이다.

ex) 1차로인 막다른 길에 차량 5대가 차례대로 들어오면 들어온 순서대로 나갈 수밖에 없다.
즉, 가장 나중에 들어간 자동차가 제일 먼저 나온다.

-> stack은 입력과 출력의 방향이 하나로 이루어지는 제한적 접근에 있다.
이런 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out) 이라고 한다.

홈페이지의 뒤로가기, 앞으로가기가 대표적인 예시.

새로운 페이지에 접속하면 Prev Stack에 현재 페이지이를 보관한다.
뒤로가기를 누르면 현재페이지는 NextStack에 옮겨지고, Prev Stack에 가장 나중에 보관된 Page를 갖고 온다.
앞으로가기를 하면 NextStack을 불러온다.
현재 페이지를 Prev Stack에 보관한다.

Queue(큐)

줄을 서서 기다리다, 대기행렬.

while반복문과 세트다!!

stack과 반대다.
먼저 들어간 것이 먼저 나온다.

톨게이트를 생각하자.

FIFO(First In First Out) or LILO(Last In Last Out)

즉, 데이터가 입력된 순서대로 처리할 때 사용되는 구조.

프린트를 보면 출력을 누르면 임시기억장치 Queue에 하나씩 들어가고 Queue에 들어온 문서를 순서대로 인쇄한다.

속도의 차이나 시간 차이를 극복아기 위해 임시기억장치의 자료구조로 Queue를 사용한다.
이것을 통틀어서 우리가 흔히 얘기하는 Buffering, 즉 버퍼(Buffer)라고 한다.

유튜브를 보면 버퍼링 때문에 동영상이 재생이 안 될 때가 있는데, 그때 일시정지를 눌러놓으면 Queue에 data를 모았다가 충분한 양이 모이면 동영상을 재생하는 것.

Queue 모양이 나오면 짝꿍처럼 쓰는 반복문!!
While!!!!

Graph

자료구조의 그래프는 마치 거미줄처럼 여러 개의 점들이 선으로 이어져 있는 복잡한 네트워크망과 같은 모습을 가지고 있다.

정점, 간선

Graph의 용어들

검색 엔진, SNS에서 사람들과의 관계, 내비게이션 등에서 사용하는 자료구조가 바로 그래프다.

예) 서울에 사는 A는 부산에 사는 B와 오랜 친구 사이입니다. 이번 주말에 부산에서 열리는 B의 결혼식에 참석하기 위해 A는 차를 몰고 부산으로 가려고 합니다. 대전에 살고 있는 친구 C도 B의 결혼식에 참석한다고 하여, A는 서울에서 출발하여 대전에서 C를 태워 부산으로 이동하려고 합니다.

위를 보면 3개의 정점이 존재하고 그 3개의 정점은 서로 이어지는 간선을 가지고 있다.

정점: 서울, 대전, 부산
간선: 서울—대전, 대전—부산, 부산—서울

이 간선은 서로 이동할 수 있음을 나타낸다.
이동할 수 없는 경우에는 간선을 추가할 수 없기 때문에 이럴 때는 관계가 없다고 표현한다.

위 자바스크립트는 비가중치 그래프를 표현한 것이다
위의 정보만으로는 갈 수 있다는 사실 외에는 알 수 있는 것이 없다.
그래서 비가중치 그래프를 가중치 그래프로 바꾼다면 이렇게 표현할 수 있을 것이다.

정점: 서울, 대전, 부산
간선: 서울—140km—대전, 대전—200km—부산, 부산—325km—서울

인접 행렬

인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다.
만약 정점이 이어져있다면 1(true), 안 이어져있다면 0(false)으로 표시한 일종의 표.

A의 진출차수는 1개 입니다: A —> C
[0][2] === 1
B의 진출차수는 2개 입니다: B —> A, B —> C
[1][0] === 1
[1][2] === 1
C의 진출차수는 1개입니다: C —> A
[2][0] === 1

인접리스트

각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한다.

B는 A와 C로 이어지는 간선이 두 개 있는데, A가 먼저 이어지든 C가 먼저 이어지든 보통은 중요하지 않다.

BFS / DFS

그래프의 데이터는 배열처럼 정렬이 되어 있지 않기 때문에 원하는 자료를 얻으려면 하나씩 모두 방문하여 찾아야 한다.

한국을 기준으로 미국까지 가는 방법을 가까운 정점부터 탐색한다.
더는 탐색할 정점이 없을 때, 그다음 떨어져 있는 정점을 순서대로 방문한다.
직항이라면 한국과 미국 사이에 어떠한 경유지도 없기 때문에 제일 가까운 정점에 미국이 있다.
경유지가 있다면 직항보다 거리가 멀다는 사실을 확인할 수 있다.
이렇게, 너비를 우선적으로 탐색하는 방법을 Breadth-First Search, 너비 우선 탐색이라고 한다.
주로 최단 경로를 찾을 때 사용한다.

하나의 경로를 끝까지 탐색한 후 미국 도착이 아니라면 다음 경로로 넘어가 탐색한다.
하나의 노선을 끝까지 들어가서 확인하고 넘어가기 때문에 운이 좋으면 단 몇 번 만에 경로를 찾을 수 있다.
또한 미국으로 가는 길이 아님을 미리 체크할 수 있다면 바로 그 순간 다음 탐색으로 넘어갈 수 있다.

이렇게 깊이를 우선적으로 탐색하는 방법을 Depth-First Search, 깊이 우선 탐색이라고 한다.
만약, BFS로 탐색하게 된다면 제일 첫 번째 경로가 미국행이라도, 다른 모든 경로를 살펴보아야 한다.

Tree

데이터가 바로 아래에 하나 이상의 데이터에 단방향으로 연결된 계층적 자료구조.
하나의 데이터 아래에 여러개의 데이터가 존재할 수 있는 비선형 구조이다.
트리구조는 계층적으로 표현이 되고 아래로만 뻗어나가기 때문에 사이클이 없다.

트리 구조는 루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한다.
각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가진다.
그림에서 A는 B와 C의 부모 노드(Parent Node)이고, B와 C는 A의 자식 노드(Child Node)이다.
자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(Leaf Node)라고 부른다.

자료구조 Tree는 깊이와 높이, 레벨 등을 측정할 수 있다.

깊이 (depth)
트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있다.
루트 노드는 지면에 있는 것처럼 깊이가 0이다.
위 그림에서 루트 A의 depth는 0이고, B와 C의 깊이는 1이다.
D, E, F, G의 깊이는 2다.

레벨(Level)
트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현할 수 있다.
depth가 0인 루트 A의 level은 1이다.
depth가 1인 B와 C의 level은 2이다.
D, E, F, G의 레벨은 3이다.
같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node) 라고 한다.

높이(Height)
트리 구조에서 리프 노드를 기준으로 루트까지의 높이(height)를 표현할 수 있다.
리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가진다.
트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 놓는다.
위 그림에서 H, I, E, F, J의 높이는 0이다.
D와 G의 높이는 1이다.
B와 C의 높이는 2다.
이때 B는 D의 height + 1 을, C는 G의 height + 1 을 높이로 가진다.
따라서, 루트 A의 높이는 3이다.

서브 트리(Sub tree)
트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리 라고 부른다.
(D, H, I)로 이루어진 작은 트리도 서브 트리이고, (B, D, E)나 (C, F, G, J)도 서브 트리다.

Tree Traversal

특정 목적을 위해 모든 노드를 한 번씩 방문하는 것을 트리순회라고 한다.
트리 구조는 계층적 구조라는 특별한 특징을 가지기 때문에 모든 노드를 순회하는 방법에는 크게 세 가지가 있다.

트리구조에서 노드는 순차적으로 조회를 할 때 순서는 항상 왼쪽부터 오른쪽이다

전위 순회 -

가장 먼저 방문할 노드는 루트다.
루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색을 한다.

중위 순회 -
루트를 가운데에 두고 순회한다.
제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색한다.

후위 순회

루트를 가장 마지막에 순회한다.
제일 왼쪽 끝에 있는 제일 하위 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문한다.

Binary Search Tree

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