[Data Structure] Intro

자료구조에 대해 정리하고자 한다. 참고자료는 천인국 교수의 C언어로 쉽게 쓴 자료구조이며 C와 Python으로 모두 구현할 예정이다.

자료구조와 알고리즘의 정의

• 자료구조란 프로그램에서 자료들을 효율적으로 정리하여 보관하는 여러가지 구조

• 알고리즘은 특정 문제를 단계적으로 해결하는 절차, 따라서 문제를 해결하는 방법을 먼저 고안해야 하며, 수행해야 할 절차를 컴퓨터가 수행할 수 있도록 명령어의 집합으로 구현해야 함

• PS는 자료구조 + 알고리즘

알고리즘의 조건

• 입력 : 0개 이상의 입력이 존재

• 출력 : 1개 이상의 출력이 존재

• 명백성 : 각 명령어의 의미는 명확해야 함

• 유한성 : 한정된 수의 단계 후에는 반드시 종료해야 함

• 유효성 : 각 명령어는 종이와 연필(의사코드), 또는 컴퓨터로 실행 가능한 연산

알고리즘의 기술

• 자연어 : 모호하므로, 유효성 원칙 위배

• 흐름도 : 이해하기 쉽지만, 복잡한 알고리즘을 그리기 힘듬

• 의사코드 : 알고리즘을 기술하는 데에만 사용되는 언어

• 프로그래밍 언어

추상자료형(ADT)

• 자료형은 데이터의 type과 데이터 간의 operation

• 추상자료형은 추상적, 수학적으로 자료형을 정의하여 실재적인 구현으로부터 분리한 것, 순수한 기능만을 명세한 것

• 이때 추상은 시스템의 간략화한 명세로, 가장 핵심적인 구조 및 동작에 집중하는 것을 의미

• 사용자는 ADT에서 제공하는 연산만을 사용할 수 있으며, 내부의 데이터에 접근이 불가능하며 어떻게 기능이 구현되었는지 알 수 없다

• 구현과 사용이 나뉘어지며, 구현 부분은 외부로부터 숨겨져 정보 은닉이 이루어짐

알고리즘의 성능

• 상용 프로그램이 규모가 커짐에 따라 처리해야할 자료의 양이 늘어서 성능이 중요

• 사용자의 입장에서는 되도록이면 빠른 프로그램을 선호

알고리즘 분석

• 시간 복잡도 : 알고리즘을 이루고 있는 연산이 몇 번이나 수행되었는지를 숫자로 표시, 입력의 개수 n의 함수로 표현(T(n))

• 공간 복잡도 : 알고리즘이 사용하는 메모리 분석

• 빅오 표기법

  두 개의 함수 f(n)과 g(n)이 주어질 경우, 모든 n >= n<sub>0</sub>에 대하여 |f(n)| <= c|g(n)|를 만족하는 두 상수 c와 n<sub>0</sub>이 있으면, F(n) = O(g(n)). 상한을 의미하기 때문에 여러 개의 기준이 나올 수 있으나, 최소 차수 함수로 정의해야 의미있음
  

• O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(2ⁿ) < O(n!)

• 최선(자료집합 중에서 알고리즘 수행 시간이 가장 적은 경우), 최악(자료 집합 중에서 알고리즘의 수행 시간이 가장 많은 경우), 평균(각 입력이 발생하는 확률을 고려한 평균적인 수행시간) => 통상적인 경우 최악의 경우를 시간 복잡도로 설정