[F-Lab 모각코 페이백 41일차] (CS) CHAPTER 6 자료구조

데이터를 효율적으로 이용하기 위한 저장 방법

학습목표

• 자료구조의 의미를 이해하고 종류를 알아본다.
• 배열과 연결 리스트의 구조를 이해하고 데이터의 삽입과 삭제 과정을 알아본다.
• 스택과 큐의 구조를 이해하고 데이터의 삽입과 삭제 과정을 알아본다.
• 그래프의 구조를 이해하고 깊이 우선 방법과 너비 우선 방법으로 탐색해본다.
• 트리의 구조를 이해하고 이진 탐색 트리에서 데이터의 삽입과 삭제 과정을 알아본다.

 

 

TIL

• 자료구조

 

 

자료구조의 개요

• 자료구조의 개념: 데이터를 효율적으로 이용하기 위해 저장하는 방법이다. 이를 통해 데이터에 대한 검색, 삽입, 삭제 등의 연산을 효율적으로 처리할 수 있다.

배열과 연결 리스트

• 배열: 동일한 데이터 타입의 변수들을 하나의 이름으로 엮어서 관리하는 선형 자료구조이다. 데이터를 인덱스로 접근할 수 있기 때문에 검색 연산이 빠르다. 하지만 삽입, 삭제 연산이 느리다는 단점이 있다.
• 연결 리스트: 데이터와 다음 노드의 주소를 함께 저장하는 방식으로 구현된 선형 자료구조이다. 포인터를 이용해 데이터를 연결하기 때문에 삽입, 삭제 연산이 빠르다. 하지만 검색 연산이 느리다는 단점이 있다.

스택과 큐

• 스택: 데이터를 일시적으로 저장하기 위한 자료구조로, 후입선출(LIFO) 방식으로 동작한다. 데이터 삽입, 삭제가 맨 위에서 이루어지기 때문에 검색 연산은 불가능하다.
• 큐: 데이터를 일시적으로 저장하기 위한 자료구조로, 선입선출(FIFO) 방식으로 동작한다. 데이터 삽입은 큐의 뒤에서, 삭제는 큐의 앞에서 이루어진다. 스택과 달리 검색 연산도 가능하다.

그래프

• 오일러의 증명: 모든 정점의 차수가 짝수인 그래프는 오일러 경로와 오일러 회로를 갖는다.
• 그래프의 주요 용어: 그래프는 정점(Vertex)과 간선(Edge)로 이루어진 자료구조이다. 연결되어 있는 정점들을 노드(Node)라고 하며, 노드와 노드 사이를 잇는 선을 간선이라고 한다.
• 그래프의 탐색: 그래프를 탐색하는 방법에는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다. DFS는 스택을 이용해 구현하며, BFS는 큐를 이용해 구현한다.

트리

• 트리의 구조와 주요 용어: 트리는 계층적인 구조를 표현하기 위한 자료구조이다. 루트(Root) 노드를 중심으로 여러 개의 서브 트리(Subtree)가 존재하며, 각 서브 트리는 또 다시 루트가 될 수 있다.
• 이진 트리: 자식 노드가 최대 2개인 트리를 이진 트리라고 한다. 이진 트리는 이진 탐색 트리, AVL 트리, 힙 등의 자료구조에서 사용된다.
• 이진 탐색 트리: 이진 트리 중에서도 각 노드의 왼쪽 서브 트리에는 노드의 값보다 작은 값이, 오른쪽 서브 트리에는 큰 값이 위치하도록 구성된 트리이다. 검색, 삽입, 삭제 등의 연산을 빠르게 수행할 수 있어 많이 사용된다.