Today I Learned

• 자료구조(Stack, Queue, Graph, Tree) 이론
• 자료구조 알고리즘 문제

자료구조(Data Structure)란?

• 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미
• 더 구체적으로 말하면, 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미

자료구조는 형태에 따라 선형 구조, 비선형 구조로 나눌 수 있다.

선형 구조

Stack

• 뜻: 쌓다 쌓이다 포개지다
• 직역 그대로 스택은 자료(data)를 쌓는 자료구조
• 후입선출(LIFO)
• 실사용 예: 브라우저에서 뒤로가기, 앞으로 가기 기능

Queue

• 뜻: 줄을 서서 기다리다, 대기 행렬
• 선입선출(FIFO)
• 자료가 입력된 순서대로 처리해야 할 필요가 있는 상황에서 사용
• 실사용 예: 프린터의 문서 인쇄작업
  • 컴퓨터 장치들 사이에 자료를 주고받을 때 각 장치들 간의 속도차를 극복하기 위한 임시 기억 장치로 Queue가 사용됨 ➡️ buffer 개념

비선형 구조

Graph

• 정점과 정점을 잇는 간선으로 구성
• 유향 그래프, 무향 그래프
  • 간선이 방향성을 갖는지 갖지 않는지에 따른 분류
  • 무향 그래프는 순환이 없는 연결 그래프
• 진입 차수(in-degree) / 진출 차수(out-degree)
  • 한 정점에 들어오고 나가는 간선의 개수
• 인접(adjacency)
  • 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접해 있다고 한다.
• 자기 루프(self loop)
  • 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우
• 사이클(cycle)
  • 한 정점에서 출발하여 다시 해당 정점으로 돌아가는 것

Tree

• 데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결되는 계층적 자료구조
• 부모 노드(Parent Node), 자식 노드(Child Node)
• 리프 노드(Leaf Node): 자식이 없는 노드
• 실사용 예: 컴퓨터의 디렉토리 구조, 가계부, 조직도 등
• 이진 트리(binary tree)
  • 자식이 최대 두 개인 트리

BST(Binary Search Tree)

이진 탐색 트리(BST)는 이진 트리 기반의 탐색을 위한 자료 구조이다. 아래와 같은 조건을 갖는다.

• 모든 노드의 키는 유일하다.
• 왼쪽 자식 트리의 키들은 루트나 부모 트리의 키보다 작다.
• 오른쪽 자식 트리의 키들은 루트나 부모 트리의 키보다 크다.
• 왼쪽과 오른쪽 자식 트리도 이진 탐색 트리이다.