[자료구조/알고리즘] 자료구조 기초 리뷰

소금·2021년 9월 6일

Chapter. 자료구조

🥜 자료구조

자료구조 : 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것
특정한 상황에 놓인 문제를 해결하는데 특화됨
데이터 : 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값
=> 사용하려는 목적에 따라 형태를 구분, 분류 빛 분석하고 정리하여 활용해야 의미있음

Chapter. stack / queue

🍯 stack

데이터를 순서대로 쌓는 구조
입력과 출력이 하나의 방향으로 이루어지는 제한적 접근
가장 먼저 들어간 데이터가 가장 나중에 나오고,
가장 나중에 들어간 데이터가 가장 먼저 나올 수 있음
ex) 브라우저의 뒤로가기 및 앞으로 가기 기능
1. 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관합니다.
2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때에는, 
현재 페이지를 Next Stack에 보관하고 
Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져옵니다.
3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때에는,
Next Stack의 가장 마지막으로 보관된 페이지를 가져옵니다.
4. 마지막으로 현재 페이지를 Prev Stack에 보관합니다.
🍯 queue

줄을 서서 기다리는 대기행렬 데이터
가장 먼저 들어간 데이터가 먼저 나오고,
가장 나중에 들어간 데이터가 나중에 나옴
버퍼 => 장치들 간 데이터를 주고 받을 때, 장치 사에에서 존재하는 속도차/시간차를 극복하기 위해 임시 기억 장치의 자료 구조로 queue를 사용

ex) 프린터 출력의 작업 목록, 유튜브 영상

컴퓨터(출력 버튼) =>
(임시 기억 장치의) Queue에 하나씩 들어옴 =>
Queue에 들어온 문서를 순서대로 인쇄

일반적으로 프린터는 속도가 느립니다.
CPU는 프린터와 비교하여, 데이터를 처리하는 속도가 빠릅니다.
따라서, CPU는 빠른 속도로 인쇄에 필요한 데이터(data)를 만든 다음, 
인쇄 작업 Queue에 저장하고 다른 작업을 수행합니다.
프린터는 인쇄 작업 Queue에서 데이터(data)를 받아 일정한 속도로 인쇄합니다.

Chapter. graph / tree / BST

🍠 graph

여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
직접적인 관계 : 두 점 사이를 직접 이어주는 선이 있음
간접적인 관계 : 직접적으로 이어져있진 않으나 몇 개의 점과 선에 걸쳐 이어짐
관계없음 : 두 점이 전혀 이어져있지 않음

정점 vertext : 그래프에서 하나의 점
간선 edge : 그래프에서 하나의 선
인접 : 두 정점간 간선이 직접 이어져 있다면 두 정점은 인접한 정점
자기 루프 : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우
(다른 정점을 거치지 않음)
사이클 : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈수 있다면 사이클이 있음

가중치 : 두 정점간 연결이 얼마나 되는지 정보
비가중치 그래프 : 가중치가 적혀있지 않은 그래프

무향 그래프 : 정점간 이동이 자유로운 방향성이 없는 그래프
단방향 그래프 : 일방통행인 간선이 있는 그래프
진입차수 : 한 정점에 들어오는 간선 진입 개수
진출차수 : 한 정점에서 나가는 간선 진출 개수

🍠 인접행렬

정점들이 인접한 상태인지를 표시한 행렬, 2차원배열 형태로 나타내짐
두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이

🍠 tree

단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 뻗어 있는 비선형 구조 형태
데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결된 계층적 자료구조

트리 내부 데이터를 노드 node, 두 개의 노드가 상하 계층으로 연결되면 위 노드는 부모 노드 parent node, 아래 노드는 자식 노드 child node, 자식이 없는 노드는 리프 노드 leaf node , 트리 구조의 시작점 노드는 루트 root

깊이
루트로부터 하위 계층의 특정 노드까지의 깊이 - 루트의 깊이는 0

레벨
트리 구조에서 갚은 깊이를 가지고 있는 노드의 묶음 - 루트의 레벨은 1
같은 레벨의 노드는 형제 노드 sibling node

높이
리프 노드를 기준으로 루트까지의 높이를 표현 - 그림에서 루트의 높이는 3

서브 트리
큰 트리의 내부에 트리 구조를 갖춘 작은 트리

ex) 컴퓨터의 디렉토리 구조, 토너먼트 대진표, 가계도(족보), 조직도

🍠 binary search tree

자식노드가 최대 두 개인 노드들로 구성된 트리 = 왼쪽 자식 노드 + 오른쪽 자식 노드
모든 왼쪽 자식의 값이 루트보다 부모보다 작고,
모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가짐

정 이진 트리 full binary tree : 각 노드가 0 또는 2 개의 자식 노드를 가짐
완전 이진 트리 complete binary tree : 마지막 레벨을 제외한 모든 노드가 가득차있고, 마지막 레벨의 노드는 적어도 왼쪽이 채워져 있어야 함
포화 이진 트리 perfect binary tree : 정 이진 트리이면서 완전 이진 트리, 모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 채워져 있음

🍠 tree traversal

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것

전위 순회

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

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

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

🍠 BFS / DFS

그래프의 탐색 : 모든 정점들을 한번씩 방문하는 것이 목적

BFS breadth-first search

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

DFS depth-first search

비행기 티켓이 없다면 어떤 비행기가 미국으로 가는 것인지 알 수 없습니다. 이때 비행기를 타고 여러 나라를 방문하면서, 마지막에 미국에 도착하는 경로를 찾아야 합니다. DFS는 하나의 경로를 끝까지 탐색한 후, 미국 도착이 아니라면 다음 경로로 넘어가 탐색합니다. 하나의 노선을 끝까지 들어가서 확인하고 다음으로 넘어가기 때문에, 운이 좋다면 단 몇 번만에 경로를 찾을 수 있습니다. 또 미국으로 가는 길이 아님을 미리 체크할 수 있다면, 바로 그 순간 다음 탐색으로 넘어갈 수 있습니다.
이렇게, 깊이를 우선적으로 탐색하는 방법을 Depth-First Search, 깊이 우선 탐색이라고 합니다. 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용합니다. BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있습니다. 만약, BFS로 탐색을 하게 된다면 제일 첫 번째 경로가 미국행이라도, 다른 모든 경로를 살펴보아야 합니다.