[HUFS/자료구조] #1 자료구조와 알고리즘

 

대략적인 커리큘럼

자료구조란?

다양한 자료를 효율적인 규칙에 따라 정리한 구조이다.

알고리즘을 어떠한 자료구조로 구성할 것인지 선택할 수 있어야 한다

 

선형 자료구조: 연속적으로 붙는 연결관계를 가진 자료구조

비선형 자료구조: 복잡하고 계층관계를 가진 자료구조

알고리즘이란?

알고리즘의 조건

저장된 자료구조를 알고리즘으로 구현

알고리즘 기술 순서는..

 

자연어로 표현 -> 흐름도로 표현 -> 유사 코드로 표현 -> 프로그래밍 언어로 표현

 

추상 자료형(ADT – Abstract Data Structure)

프로그래머가 추상적(수학적)으로 정의한 자료형

~ 데이터와 연산이 무엇(what)인지는 정의하지만 어떻게(how) 할지는 모르는 상태

 

가방(Bag)의 추상 자료형

파이썬 내장 함수로 가방의 연산을 구현

해당 함수들로 이렇게 가방의 자료를 관리한다

알고리즘의 성능 분석

1. 알고리즘의 실행 시간을 측정하는 방법

~정확한 측정을 위해 동일한 하드웨어에 실제로 구현해야 하기 때문에 현실적으로 어려움

 

time 모듈로 시간을 측정한다

2. 알고리즘의 복잡도를 분석하는 방법 (가장 일반적인 방법!)

~알고리즘이 수행하는 연산의 횟수를 시간 복잡도 함수 T(n) 로 분석한다

 

방식에 따라 복잡도 차이가 생긴다

복잡도 함수로 표현하는 방법 / 알고리즘의 연산 횟수

n 의 개수에 따른 복잡도 함수의 그래프

이렇게 시간 복잡도 함수로 표현했을 때 실질적인 비중을 고려해

차수가 가장 큰 항만 보는 대략적인 표기법을 빅오 표기법(big-O notation)이라고 한다

 

빅오 표기법의 예시

최악의 경우(복잡도의 상한값)를 가정하는 것이 유의미하다

빅오 표기법의 종류 및 그래프

빅오 표기법과 반대로 하한값을 구하는 빅오메가 표기법과 평균을 구하는 빅세타 표기법도 있다

시간 복잡도 정리

시간 복잡도 분석: 순환 알고리즘

함수가 자기 자신을 다시 호출(재귀)해 문제를 해결하는 순환적 프로그래밍 기법이다

 

대표적으로 정수의 팩토리얼(Factorial)이 있다

순환 알고리즘에는 반드시 종료 조건이 있어야 한다!

일반적인 경우 순환적인 방식은 함수 호출의 오버헤드로 반복문보다 속도가 느리다

거듭제곱처럼 특수한 경우에는 순환이 더 빠를 수 있다

다만 피보나치 수열처럼 대부분의 상황에는 순환이 비효율적이다

일반적으로 반복(for/while)을 사용한다

하노이탑 공략

순환을 이용한 하노이탑 구현