상권's
TIL 4 (2021.10.08) 본문
자료구조가 무엇인지 설명할 수 있다.
자료구조란 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것입니다.
데이터를 정해진 규칙없이 저장하거나, 하나의 구조로만 정리하고 활용하는 것보다 데이터를 체계적으로 정리하여 저장해두는 게, 데이터를 활용하는 데 있어 훨씬 유리합니다. 선배 개발자들은 무수한 상황에서 데이터를 효율적으로 다룰 수 있는 방법을 모두 모아, 자료구조라는 이름을 붙였습니다.
Stack, Queue 자료구조에 대해 이해할 수 있다.
Stack 자료구조 Stack의 특징은 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근에 있습니다. 이런 Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부르기도 합니다.
각 자료구조가 가진 특징을 학습한다. 처음에 들어간 것이 맨 마지막에 나온다.
각 자료구조를 사용하기 적합한 상황을 이해한다.
뒤로 가기, 앞으로 가기 = 뒤로 가기를 구현 할 때, 우리가 방문했던 페이지를 history라는 스택을 만들어 넣는다. 이후에 방문하는 페이지들도 history 스택에 집어 넣는다. 이 상황에서 뒤로 가기를 실행하면, history라는 스택에서 제일 늦게 들어갔던 페이지를 꺼낸다(last in first out). 계속해서 뒤로 가기를 눌렀을 경우, 맨 마지막에 해당하는 페이지는 history 스택에 제일 처음으로 들어갔던 페이지가 나온다(first in last out).
다른 자료구조와의 차이점을 이해하기 위해 자료구조 내부를 직접 구현한다.
자료구조를 구현하며, 자료구조의 동작원리를 이해한다.
class Stack {
constructor() {
this.storage = {};
this.top = 0; // 스택의 가장 상단을 가리키는 포인터 변수를 초기화 합니다.
}
size() {
return this.top; // top은 storage에 있는 갯수를 뜻한다.
}
// 스택에 데이터를 추가 할 수 있어야 합니다.
push(element) {
this.storage[this.top] = element; // 0: element
this.top += 1; // storage에 1개가 있다는 뜻.
}
// 가장 나중에 추가된 데이터가 가장 먼저 추출되어야 합니다.
pop() {
// 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않아야 합니다
if (this.top === 0) { // 빈스택일 경우
return;
}
const result = this.storage[this.top - 1]; // pop이 될 데이터
delete this.storage[this.top - 1]; // 삭제한다. delete를 할 경우, true가 입력된다.
this.top -= 1; // storaga에 하나가 빠졌기 때문에 top에서 하나를 뺀다
return result; // pop을 할 경우, 해당 데이터를 리턴한다.
}
}
Queue 자료구조 Stack과 반대되는 개념으로, 먼저 들어간 데이터(data)가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out) 을 특징으로 가지고 있습니다.
각 자료구조가 가진 특징을 학습한다. 처음 들어간 것이 제일 처음으로 나온다.
각 자료구조를 사용하기 적합한 상황을 이해한다.
프린터 = 회사에서 다수의 컴퓨터가 연결된 프린터에서 파일 출력을 진행하면 예약이라는 큐에 파일이 들어가는데, 나보다 먼저 출력을 진행했던 파일들이 예약이라는 큐에 먼저 들어가있고 그 뒤로 내 파일이 위치하게 된다(last in last out). 출력이 완료가 되면 예약이라는 큐의 맨 앞의 파일이 진행된다(first in first out). 예약이 되어있던 파일들의 출력이 완료되면 비로소 내 파일이 출력된다.
class Queue {
constructor() {
this.storage = {};
this.front = 0; // 가장 처음에 들어온 요소를 표현한다.
this.rear = 0; // 다음에 추가될 요소를 표현한다.
}
size() { //size(): 큐에 추가된 데이터의 크기를 리턴해야 합니다.
return this.rear-this.front; // 추가를 할 때는 rear가 오르고, 삭제를 할 때 front 가 오르기 때문에
} // 이 두개의 차이로 현재 storage에 있는 갯수를 표현할 수 있다.
// 큐에 데이터를 추가 할 수 있어야 합니다.
enqueue(element) {
this.storage[this.rear] = element;
this.rear += 1; // 추가를 할 경우, 다음에 들어올 요소를 나타내기 위해서 rear에 1을 추가한다.
}
// 가장 먼저 추가된 데이터가 가장 먼저 추출되어야 합니다.
dequeue() {
// 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 합니다
if (this.size() <= 0) {
return;
}
// 가장 먼저 추가된 데이터를 큐에서 삭제하고 삭제한 데이터를 리턴해야 합니다.
const result = this.storage[this.front]; // 가장 먼저 들어온 요소를 삭제하기 때문에 리턴하는 부분에서는 먼저 들어온 요소를 표현한다.
delete this.storage[this.front]; // 처음들어온 요소를 삭제한다. => true를 리턴한다.
this.front += 1; // 그 다음에께 front가 되기 때문에 front에 1을 더해서 다음 요소를 표현한다.
return result; // 삭제한 요소를 표현한다.
}
}
그래프란,
그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조입니다. 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있습니다. 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어집니다. 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge) 이라고 합니다.
추가적인 정보를 파악할 수 없는 그래프, 가중치(연결의 강도가 얼마나 되는지)가 적혀 있지 않은 이런 그래프를 비가중치 그래프 라고 합니다.
간선에 연결정도(거리 등)를 표현한 그래프를 가중치 그래프라고 합니다.
그 외 그래프의 종류
무(방)향그래프(undirected graph): 앞서 보았던 내비게이션 예제는 무(방)향 그래프 입니다. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는것도 가능합니다. 하지만 단방향(directed) 그래프로 구현 된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능합니다(혹은 그 반대). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있습니다.
진입차수(in-degree) / 진출차수(out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냅니다.
인접(adjacency): 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.
자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현합니다. 다른 정점을 거치지 않는다는 것이 특징입니다.
사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다. 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프 입니다.
두 정점을 바로 이어 주는 간선이 있다면 이 두 정점은 인접하다고 이야기합니다. 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬으로 2차원 배열의 형태로 나타냅니다. 만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표입니다. 만약 가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장합니다.
그래프의 표현 방식: 인접 행렬 & 인접 리스트
인접 행렬
두 정점을 바로 이어 주는 간선이 있다면 이 두 정점은 인접하다고 이야기합니다. 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬으로 2차원 배열의 형태로 나타냅니다. 만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표입니다. 만약 가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장합니다. 위의 내비게이션 예제라면, 거리를 입력하면 좋습니다. 네비게이션 그래프를 인접 행렬로 표현하면 다음과 같습니다.
인접 행렬은 언제 사용할까?
한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이합니다.
예를 들어, A에서 B로 진출하는 간선이 있는지 파악하기 위해선 0 번째 줄의 1 번째 열에 어떤 값이 저장되어있는지 바로 확인할 수 있습니다.
가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용됩니다.
class GraphWithAdjacencyMatrix {
constructor() {
this.matrix = [];
}
addVertex() { // 버텍스 정점을 추가한다.
const currentLength = this.matrix.length;
for (let i = 0; i < currentLength; i++) {// 매트릭스의 길이만큼 돌면서
this.matrix[i].push(0); //매트릭스의 요소마다 0을 더 추가해서 길이를 늘린다.
}
this.matrix.push(new Array(currentLength + 1).fill(0)); //길이가 추가되는 만큼 새로운 배열을 매트릭스에 더한다.
}
// 0일 경우 11번 줄이 돌면서 [0]
// 1일 경우 8번 줄이 돌면서 [0, 0] 이 되었다가 11번 줄에서 다시 [0, 0] [0, 0] 이된다.
//vertex를 탐색합니다.
contains(vertex) {
return !!this.matrix[vertex]; // undefined나 null의 값을 false로 바꿀 수 있다 => !!
}
addEdge(from, to) { // 간선을 추가한다.
const currentLength = this.matrix.length - 1;
if (from === undefined || to === undefined) { // from이나 to가 undefined면
console.log("2개의 인자가 있어야 합니다."); // 주의 문자가 뜬다.
return;
}
if ( from > currentLength || to > currentLength || from < 0 || to < 0) { // 현재 정점의 수보다 더 크다면 없다는 이야기를 한다.
console.log("범위가 매트릭스 밖에 있습니다.");
return;
}
this.matrix[from][to] = 1; //해당 하는 부분을 1로 바꿔서 연결이 되어있다는 표시를 한다.
}
hasEdge(from, to) {
return !!this.matrix[from][to]; // this.matrix[from][to] 가 0으로 연결이 안되어있다면 !!0은 false가 된다.
}
removeEdge(from, to) {
const currentLength = this.matrix.length - 1;
if (from === undefined || to === undefined) {
console.log("2개의 인자가 있어야 합니다.");
return;
}
if ( from > currentLength || to > currentLength || from < 0 || to < 0 ) {
console.log("범위가 매트릭스 밖에 있습니다.");
return;
}
this.matrix[from][to] = 0; // 0이 되어서 연결이 안된다는 걸 표현한다.
}
}인접 리스트는 언제 사용할까?
인접 리스트는 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현합니다. 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있습니다.
인접행렬을 보게 되면 B는 A나 C로 갈 수 있으면, A는 C로, C는 A로 갈 수 있는데, 왜 B -> A -> C 표현이 되었으며, 이 순서는 중요한가요?
보통은 중요하지 않습니다. 그래프, 트리, 스택, 큐 등 모든 자료 구조는 구현하는 사람의 편의와 목적에 따라 기능을 추가/삭제할 수 있습니다. 그래프를 인접 리스트로 구현할 때, 정점별로 살펴봐야 할 우선 순위를 고려해 구현할 수 있습니다. 이때, 리스트에 담겨진 정점들을 우선 순위별로 정렬할 수 있습니다. 우선 순위가 없다면, 연결된 정점들을 단순하게 나열한 리스트가 됩니다.
- 우선 순위를 다뤄야 한다면 더 적합한 자료구조(ex. queue, heap)를 사용하는 것이 합리적 입니다. 따라서 보통은 중요하지 않습니다. (언제나 예외는 있습니다.)
메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용합니다.
인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지합니다.
트리란,
그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부릅니다.
트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결된 계층적 자료구조입니다. 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조입니다. 트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클이 없습니다.
트리 구조는 루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결합니다. 각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하계층으로 연결되면 부모/자식 관계를 가집니다. 위 그림에서 A는 B와 C의 부모 노드(Parent Node)이고, B와 C는 A의 자식 노드(Child Node)입니다. 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(leaf Node)라고 부릅니다.
용어정리
노드(Node) : 트리 구조를 이루는 모든 개별 데이터
루트(Root) : 트리 구조의 시작점이 되는 노드
부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
리프(Leaf) : 트리 구조의 끝지점이고, 자식 노드가 없는 노드
깊이 (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)도 서브 트리입니다.
트리의 실사용 예제
가장 대표적인 예제는 컴퓨터의 디렉토리 구조입니다. 어떤 프로그램이나 파일을 찾을 때, 바탕화면 폴더나 다운로드 폴더 등에서 다른 폴더에 진입하고, 또 그 안에서 다른 폴더에 진입하면서 원하는 프로그램이나 파일을 찾습니다. 모든 폴더는 하나의 폴더(루트 폴더, /)에서 시작되어, 가지를 뻗어나가는 모양새를 띕니다.
하나의 폴더 안에 여러 개의 폴더가 있고, 또 그 여러 개의 폴더 안에 또 다른 폴더나 파일이 있습니다. 위 그림처럼, 제일 첫 번째 폴더에서 출발하여 도착하려는 폴더로 가는 경로는 유일합니다. 사용자들이 사용하기 편하게 사용하기 위한 파일 시스템 등에서는 트리 구조를 이용해 만들어져 있습니다.
class Tree {
constructor(value) {
// constructor로 만든 객체는 트리의 Node가 됩니다.
this.value = value;
this.children = [];
}
// 트리의 삽입 메서드를 만듭니다.
insertNode(value) { // children 배열에다가 value값을 넣은 new Tree를 넣어준다.
const childNode = new Tree(value);
this.children.push(childNode);
}
// 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드를 만듭니다.
contains(value) {
// Tree의 value랑 맞는 지 확인을 하고
if (this.value === value) {
return true;
}
else { // 자식들을 돌면서 value를 가진 자식이 있는 지 확인을 한다.
for (let el of this.children) {
if(el.contains(value)) {
return true;
}
}
}
// TODO: 값을 찾을 때까지 children 배열을 순회하며 childNode를 탐색하세요.
// 전부 탐색했음에도 불구하고 찾지 못했다면 false를 반환합니다.
return false;
}
}Binary Search Tree를 이해할 수 있다.
이진트리(Binary tree)는 자식 노드가 최대 두 개인 노드들로 구성된 트리입니다. 이 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있습니다.
이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉩니다.
| 정 이진 트리 |
Full binary tree | 각 노드가 0 개 혹은 2 개의 자식 노드를 갖습니다. |
| 포화 이진 트리 | Perfect binary tree | 정 이진 트리이면서 완전 이진 트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다. |
| 완전 이진 트리 | Complete binary tree | 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다. |
이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있습니다.
이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있습니다. 균형이 잡히지 않은 트리는 탐색하는 데 시간이 더 걸리는 경우도 있기 때문에 해결해야할 문제입니다. 이 문제를 해결하기 위해 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가할 수 있습니다.
class BinarySearchTree {
constructor(value) {
// constructor로 만든 객체는 이진 탐색 트리의 Node가 됩니다.
this.value = value;
this.left = null;
this.right = null;
}
//이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있습니다.
//루트보다 작은 값은 왼쪽, 큰 값은 오른쪽.
insert(value) {
if (value < this.value) { // this.value가 더 클 경우에는 왼쪽에 위치해야 한다.
if (this.left === null) {
this.left = new BinarySearchTree(value); // left가 null 일 경우에는 left에다가 해당 벨류로 인스턴스를 만들어준다.
} else {
this.left.insert(value);
// null 이 아닌 인스턴스의 경우에는 insert 함수를 이용한다. left 가 10이고 벨류가 8인 경우에는 10의 left에 들어가야하니깐,
// 재귀함으로써, 10의 left에 8로 BinarySearchTree를 다시 진행하게 된다.
}
} else if (value > this.value) { // this.value보다 크다면 오른쪽에 위치해야 한다.
if (this.right === null) { // 오른쪽이 null이라면 해당값으로 인스턴스를 만든다.
this.right = new BinarySearchTree(value);
} else {
this.right.insert(value);
// right 인스턴스에다가 값을 넣어준다. right가 10인 상황에서 11이 들어오면, right도 인스턴스기 때문에 거기에다가 11로 BinarySearchTree 를 다시 만들어주게 된다.
}
}
}
contains(value) {
if (value === this.value) {
return true;
}
// 입력값이 this.value보다 작다면 왼쪽에서 찾아야 한다.
if (value < this.value) {
return !!(this.left && this.left.contains(value));
// left 가 null일 경우에는 !!null 은 false, left에다가 다시 contain 함수로 값이 있는 지 확인한다.
// !! true && null은 false this.value 보다는 큰데 왼쪽 인스턴스에서 갖고 있지 않다면, false를 리턴한다.
}
// this.value 보다 크다면 오른쪽에서 찾아야 한다.
if (value > this.value) {
return !!(this.right && this.right.contains(value));
// TODO: 현재 노드의 오른쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true를 반환합니다.
// TODO:일치하지 않다면 오른쪽 노드로 이동하여 다시 탐색합니다.
}
}
// 이진 탐색 트리를 전위 순회하는 메서드를 만듭니다.
preorder(callback) { // 전위 순회는 중 왼 오
callback(this.value);
if (this.left) { // 왼쪽에 값이 있다면, 왼쪽이 먼저 진행한다. 왼쪽에 대해서 한 번 던 preorder을 한다.
this.left.preorder(callback);
};
if (this.right) { // 오른쪽이 있다면 오른쪽에 대해서도 preorder 한다.
this.right.preorder(callback);
};
}
inorder(callback) { // 왼 중 오
if (this.left) { // 왼쪽 먼저 하고,
this.left.inorder(callback);
}
callback(this.value); // 중간에 진행을 하고,
if (this.right) {
this.right.inorder(callback); // 오른쪽을 한다.
}
}
postorder(callback) { // 왼 오 중
if (this.left) {
this.left.postorder(callback);
}
if (this.right) {
this.right.postorder(callback);
}
callback(this.value);
}
}'~2022 작성 글 > TIL' 카테고리의 다른 글
| TIL 6 (2021.10.12) (0) | 2021.10.12 |
|---|---|
| TIL 5 (2021.10.11) (0) | 2021.10.11 |
| TIL 3 (2021.10.07) (0) | 2021.10.07 |
| TIL 2 (2021.10.06) (0) | 2021.10.06 |
| TIL 1 (2021.10.05) (0) | 2021.10.05 |
