[데이터구조] Intro

해당 글은 POSTECH 백승환 교수님의 2022년도 데이터 구조의 복습입니다.

데이터구조가 왜 필요한가

프로그램은 컴퓨터가 정보를 처리하여 결과를 도출하도록 하는 명령문의 순서목록이다.

Program = Data structures + Algorithms

프로그램이 정보를 입력받아 결과를 도출하기 위해서는 1. 어떻게 정보를 조직화 할것인가? 2. 어떻게 정보를 처리할 것인가? 2가지의 질문에 부딪히게 된다. 정보를 어떻게 조직화할지에 대한 개념이 데이터구조, 어떻게 정보를 처리할 것인지에 대한 개념이 알고리즘이다.
좋은 데이터구조와 알고리즘을 사용하면 더 정확하고, 더 빠른 프로그램을 만들 수 있다. 그렇기에 좋은 프로그램을 짜기위해서는 데이터구조를 적재적소에 사용할 줄 알아야한다. 이 과목에서는 각 데이터구조가 어떻게 정보를 조직화하는지, 어떤 상황에서 얼마나 빠른지, 얼마나 정확한지 배운다.

I will, in fact, clain that the difference between a bad programmer and a good one is whether
they consider their code or their data structure more important.
Bad programmers worry about the code.
Good programmers worry about data structure and their relationships
- Linus Torvalds

Linux와 git의 창시자 Linus Torvalds

데이터구조에서는 뭘 배우는가?

사실 데이터 구조만 배우지 않고, 데이터 구조와 그 데이터 구조를 활용하는 간단한 알고리즘에 대해 배운다. Algorithm Analysis

컴퓨터 스펙과 관계없이 얼마나 알고리즘이 좋은지를 판별하는 방법이다.

List, Stack, queue

순차적인 데이터를 입력 순서에 따라 처리하는 데이터구조이다.

Tree

Tree 같이 정보를 계층화하는 데이터구조이다.

Priority Queue, Heap

주어진 Priority에 따라 정보를 조직화하는 데이터구조이다.

Sorting

컴퓨터가 정보를 정렬할 수 있도록 하는 알고리즘에 대해 배운다.

Binary Search Tree, AVL Tree, B Tree

Tree를 특정한 방법으로 구성하여, 특정한 성질을 띄게할 수 있는데, 그런 Tree들에 대해 배운다.

Graph

데이터별로 연관성은 있지만 계층적인 구조가 존재하지 않는 경우 사용하는 데이터구조이다.

Shortest Path Finding

Graph를 이용하여 최단거리를 찾는 알고리즘이다.

Minimum Spanning Tree

Graph의 정점들을 최소한의 cost를 이용하여 구성하는 데이터구조 & 알고리즘이다.