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

Achievement Goals

• 자료구조가 무엇인지 설명할 수 있다.
• Stack, Queue, Tree, Graph 자료구조에 대해 이해할 수 있다.
  • 알고리즘 문제에서 Stack, Queue 자료구조를 배열로 대체하여 흉내낼 수 있다.
  • 각 자료구조의 개념과 구조를 파악하고 목적을 이해할 수 있다.
  • 알고리즘 문제의 각 상황에 맞는 자료구조를 떠올릴 수 있다.
• 트리 및 그래프의 탐색 기법에 대해 이해할 수 있다.
  • Binary Search Tree를 이해할 수 있다.
  • BFS와 DFS의 개념을 이해하고 알고리즘 문제에서 사용할 수 있다.
• 자료구조를 활용하여 알고리즘 문제에 접근할 수 있다.

자료구조란

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

자료구조/알고리즘의 4가지 방법

Stack, Queue, Tree, Graph

Stack : 데이터(data)를 순서대로 쌓는 자료구조 가장 먼저 들어갈경우 가장 나중에 나오고 (FILO)/ 가장 늦게 들어갈경우 가장 일찍 나온다 (LIFO).

같은 사례에 대해서 생각을 해보면?

• 브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때

1. 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관합니다.
2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때에는, 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져옵니다.
3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때에는, Next Stack의 가장 마지막으로 보관된 페이지를 가져옵니다.
4. 마지막으로 현재 페이지를 Prev Stack에 보관합니다.

Queue : Stack과 반대되는 개념으로, 먼저 들어간 데이터(data)가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out) 을 특징으로 가지고 있습니다.

같은 사례에 대해서 생각을 해보면?

• 프린트를 하는 경우

1. 우리가 문서를 작성하고 출력 버튼을 누르면 해당 문서는 인쇄 작업 (임시 기억 장치의) Queue에 들어갑니다.
2. 프린터는 인쇄 작업 Queue에 들어온 문서를 순서대로 인쇄합니다.

출처 : 코드스테이츠