자료구조 기초

병목 현상을 처리해보자 / 시간복잡도 / 이진트리 / 스택 / 큐 / 힙 / 트리

학습목표

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

자료구조란?

어떤 데이터들을 묶음으로 저장하고, 사용하는 방법을 정의하는 것 (데이터는 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값)

왜 필요한가? 수많은 데이터를 관리하기 위해서는 체계적으로 정리하고 저장해두는 것이 훨씬 유리하다!

아주 좋은 예시들과 많은 연구들

• 번호를 다 알지 않아도, 이름을 아는 것만으로 전화를 할 수 있는 방법은 무엇이 있을까?
• 웹 브라우저에서 뒤로 / 앞으로 가는 방법은 무엇이 있을까?
• 게임 매칭을 잡을 때, 수많은 사람들을 통제하는 방법엔 무엇이 있을까? ...등등

정말 다양한 구조들이 있다. 그 중 가장 많이 접할 수 있는 스택, 큐, 트리, 그랩에 대해 알아보자.

자주 등장하는 네 가지의 자료구조

• Stack, Queue, Tree, Graph

자료구조는 특정한 상황에 맞게 문제를 해결할 수 있게 특화되어 있다.

Stack

:데이터를 순서대로 쌓는 구조

자료구조 Stack의 특징은 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근

→ Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)

가장 쉽게 적용된것 브라우저에 바로 뒤로 돌아가기 버튼입니다.

Queue

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

실제예시) 프린터는 인쇄 작업 Queue에 들어온 문서를 순서대로 인쇄하는 과정, 데이터가 스택에 쌓이고 버퍼링이 진행된 후 실행되는 동영상들

(위 예시처럼 컴퓨터 장치들 사이에서 데이터(data)를 주고 받을 때, 각 장치 사이에 존재하는 속도의 차이
나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용합니다. 이것을 통틀어 버퍼(buffer)
라고 합니다. 아래 이미지는 버퍼링(buffering)의 개념을 보여주고 있습니다.)

CPU에서는 규칙적인 처리를 하지만 컴퓨터 이벤트에서는 불규칙적으로 처리한다!