TIL24, 자료구조

자료구조란 무엇일까?

자료구조란, 여러 데이터들의 묶음을 저장하고 사용하는 방법을 정의한 것을 의미한다.
지금까지 공부하면서 알게 모르게 많이 사용해 온것은 물론,
일상 생활에서도 자료구조가 많이 사용되고있다.
가장 자주 등장하는 자료구조들을 살펴보면서 알아보도록 하자!

자주 등장하는 자료구조

1. Stack (선형구조)
   • 쌓다, 포개지다 라는 뜻 그대로 데이터를 순서대로 쌓는 구조이다.
   • 가장 먼저 쌓인 데이터는 가장 마지막에,
     가장 마지막에 쌓인 데이터는 가장 먼저 나올 수 있다.
     FILO (First In Last Out), LIFO (Last In First Out)이라고도 부른다.
   • 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근이다.
   • 우리가 자주 사용하는 웹페이지의 뒤로가기, 앞으로가기가 Stack이고,
     물건을 쌓아두는것 역시 Stack이다.
   • Javascript의 Array를 이용해서 Stack을 구현해보자.

let stack = [];
stack.push(1) // [1]
stack.push(2) // [1, 2]
stack.push(3) // [1, 2, 3]
stack.push(4) // [1, 2, 3, 4]
console.log(stack); // [1, 2, 3, 4]

stack.pop() // [1, 2, 3]
stack.pop() // [1, 2]
cosole.log(stack); // [1, 2]

위와 같이 첫번째 인덱스부터 데이터가 쌓이고, 마지막 인덱스부터 나온다.

1. Queue (선형구조)
   • 줄을 서서 기다리다, 대기 행렬이라는 뜻을 가진다. Stack과는 반대되는 개념이다.
   • 가장 먼저 들어온 데이터는 가장 먼저,
     가장 마지막에 들어온 데이터는 가장 나중에 나올 수 있다.
     FIFO (First In First Out), LILO (Last In Last Out)이라고도 부른다.
   • 데이터가 입력된 순서대로 처리돼야할 때 주로 사용한다.
   • 프린트 할 때, 대기 목록에 문서가 쌓이고, 들어온 순서대로 작업이 진행된다.
   • 주유소에서, 먼저 들어온 차가 주유를 끝낼 때 까지
     뒤의 차는 나갈 수 없다, 앞의 차가 주유를 끝내야 차례대로 나갈 수 있다.
   • Javascript의 Array를 이용해서 Queue를 구현해보자.

let queue = [];
queue.push(1) // [1]
queue.push(2) // [1, 2]
queue.push(3) // [1, 2, 3]
queue.push(4) // [1, 2, 3, 4]
console.log(queue); // [1, 2, 3, 4]

queue.shift() // [2, 3, 4]
queue.shift() // [3, 4]
console.log(queue); // [3, 4]

위와 같이 첫번째 인덱스부터 데이터가 쌓이고, 첫번째 인덱스부터 나온다.

1. Graph (비선형구조)
   • 기존의 알던 그래프와 달리 컴퓨터 공학에서 의미하는 그래프는
     여러개의 점들이 선으로 연결되어 있는 관계를 나타낸다.
   • 점은 정점(vertex), 선은 간선(edge)라고 표현한다.
   • 두 점이 직접적인 관계에 있다면 선으로 이어진다.
   • 두 점이 간접적인 관계에 있다면 몇개의 점과 선에 걸쳐서 이어진다.
   • 내비게이션을 예로 들어보자.
     ( 서울에서 부산을 갈때, 중간에 대전을 경유하는 경우. )
     → 정점: 서울, 대전, 부산
     → 간선: 서울-대전, 대전-부산, 서울-부산
   • 정점이 이어져 있다는 것만 알려줄 뿐, 거리 등 추가적인 정보를 파악할 수 없다.
     이런 그래프를 비가중치 그래프 라고 부른다. 객체로 표현하면 아래와 같다.

let isConnected = {
  seoul: {
    busan: true,
    daejeon: true,
  },
  daejeon: {
    seoul: true,
    busan: true,
  },
  busan: {
    seoul: true,
    daejeon: true,
  }
}

• 반면에 가중치 그래프 는 추가적인 정보를 포함한다.
  → 정점: 서울, 대전, 부산
  → 간선: 서울-140km-대전, 대전-200km-부산, 서울-325km-부산

3-1. 그래프 용어

• 무(방)향 그래프 (undirected graph): 위에서 살펴본 예제는 무(방)향 그래프이다. 서울에서 대전, 대전에서 서울을 갈 수 있지만, 단방향 (directed) 그래프로 구현되면 서울에서 대전은 갈 수 있지만, 대전에서 서울은 갈 수 없다 (또는 반대)
• 진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 들어오는 간선, 나가는 간선이 몇개인지 나타낸다.
• 인접 (adiacency): 정점 사이에 간선이 직접 이어져 있다면 인접한 정점이다.
• 자기 루프 (self loop): 정점에서 진출하는 간선이 바로 자신에게 진입하면 자기 루프를 가졌다고 한다. 다른 정점을 거치지 않는다.
• 사이클 (cycle): 한 정점에서 출발해 다시 해당 정점으로 돌아올 수 있다면 사이클이 있다고 한다. 위에서 예를 든 그래프는 서울 → 대전 → 부산 → 대전 → 서울이 가능하므로, 사이클이 존재하는 그래프이다.
• 인접 행렬: 두 정점 사이가 이어져 있다면 1(true), 이어져 있지 않다면 2(false)로 표시한다.
  1. Tree (비선형구조)
• 무방향 그래프의 한 구조이다. 아래로만 뻗어나가기 때문에, 사이클이 없다.
• 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로, 여러개의 데이터를 간선으로 연결한다.
• 각 데이터를 노드(Node)라고 하며, 두개의 노드가 위아래로 연결되면 부모/자식 관계를 갖는다.
• 자식이 없는 노드는 리프 노드(leaf Node)라고 부른다.

4-1. Tree의 깊이, 레벨, 높이

• 깊이: 루트로부터 깊이(Depth)를 표현할 수 있다. 루트 노드는 깊이가 0, 그 아래는 1, 그 아래는 2, … 쭉쭉쭉 내려간다.
• 레벨: 같은 깊이를 가지고 있는 노드를 묶어서 레벨(Level)로 표현한다. 깊이가 0인 루트의 레벨은 1, 같은 레벨에 있는 노드를 형제 노드 (Sibling Node)라고 한다.
• 높이: 리프 노드를 기준으로 루트까지의 높이를 표현한다.
• 서브 트리: 루트에서 뻗어나오는 큰 트리 내부에 트리 구조를 갖춘 작은 트리를 서브 트리라고 한다.

4-2. 여러 트리구조

• 이진 트리: 자식 노드가 최대 두개인 노드들로 구성된 트리.
• 정 이진트리 → 각 노드가 0개, 혹은 2개의 자식 노드를 갖고있다.

• 포화 이진 트리 → 마지막 레벨을 제외한 모든 노드가 가득 차 있고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.

• 완전 이진 트리 → 마지막 레벨을 제외한 모든 노드가 가득 차 있고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.

• 이진 탐색 트리 (Binary Search Tree) → 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지고 있다.
• 조직도