Achievement Goals

• 1. 자료구조에 대해서 설명하는 것
• 2. Stack, Queue, Tree, Graph 자주 등장하는 네가지의 자료구조
  • 알고리즘 문제에서 Stack, Queue 자료구조를 배열로 대체하여 흉내내기
  • 각 자료구조의 개념과 구조를 파악하고 목적에 대해서 이해하기
  • 알고리즘 문제별로 각 상황에 맞는 자료구조를 떠올리기

• 3. Tree 및 Graph의 탐색 기법에 대해서 이해하기
  • Binary Search Tree를 이해하기
  • BFS 와 DFS의 개념을 이해하고 알고리즘 문제에서 사용할 수 있는가

• 4. 자료구조를 활용하여 알고리즘 문제에 접근하기

1. 자료구조란 무엇인가

• 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것

• 대부분의 자료구조는 특정한 상황에 놓인 문제를 해결하는데 특화되어 있다.
  따라서 많은 자료구조를 알아둔다면? 어떠한 상황이 닥쳤을 때 적합한 자료구조를 빠르고 정확하게 적용하여 문제를 해결할 수 있다. 이것은 문제 해결력을 필요로하는 알고리즘 테스트 즉, 코딩테스트와 굉장히 밀접한 연관성이 있다.

2(1). Stack

• 접시를 쌓아 놓은 형태와 비슷한 Stack은 데이터를 순서대로 쌓는 자료구조이다.
• 먼저 쌓은 접시가 가장 마지막에 나가고 반대로 마지막에 쌓은 접시가 가장 먼저 나감.

특징

• 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근에 있다. 이런 Stack 자료구조의 정책을 LIFO( last in first out) or FILO(first in kast out)이라고 부르기도 한다. 스택에 마지막으로 입력된 자료가 제일 먼저 삭제 하는 방식

2(2). Queue

• 큐는 줄을 서서 기다리다 그리고 대기행렬이라는 뜻을 가지고 있다.

특징

• Stack과 반대되는 개념으로, 먼저 들어간 데이터가 먼저 나오는 `FIFO(first in first out) or LILO(last in last out) 을 특징으로 가지고 있다.
• 그래서 데이터가 입력된 순서대로 처리할 때 주로 사용한다.

질문

• Array.prototype 에는 Stack, Queue 사용을 위해 어떤 메서드가 존재하는가
• 배열로 Stack, Queue를 사용할 때 주의해야 할 사항은?
• 배열로 Stack을 사용할 때 push,pop이외에 필요한 메서드는 어떻게 구현하는가?
• 배열로 Queue를 사용할 때 push,shift 이외에 필요한 메서드는 어떻게 구현하는가?
• JS의 Array와 Stack, Queue는 어떤 차이가 있나?

2(3). Graph

• 처음 그래프를 생각했을 때 원래의 그래프 개념을 떠올리겠지만, 자료구조에서의 그래프는 전혀 다른 모습을 가지고 있다. 자료구조의 그래프는 마치 거미줄처럼 여러개의 점들이 선으로 이어져 있는 복잡한 네트워크 망과 같은 모습을 가지고 있다.
• 이렇게 그래프는 여러개의 점들이 서로 복잡하게 이어져있는데, 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 존재한다.
• 간접적인 관계라면 몇개의 점과 선에 걸쳐 이어진다.
  • 하나의 점을 정점(vertex)라고 하며, 하나의 선은 간선(edge)라고 한다.

• 연결의 강도가 적혀있지 않은 그래프는 비가중치 그래프라고 한다.

• 하지만 간선에 연결정도를 표현한 그래프를 가중치 그래프라고 한다.