[자료구조] 자료구조와 알고리즘
자료구조와 알고리즘이란?
프로그램은 자료구조+알고리즘 말한다.
자료구조는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다.
알고리즘이란 컴퓨터로 문제를 풀기 위한 단계적인 절차이다.
알고리즘의 조건
- 입력 : 0개 이상의 입력이 존재해야 한다.
- 출력 : 1개 이상의 출력이 존재해야 한다.
- 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다.
- 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다.
- 유효성 : 각 명령어들은 실행 가능한 연산이어야 한다.
알고리즘의 기술 방법
- 영어나 한국어와 같은 자연어
- 흐름도 (flow chart)
- 의사 코드 (pseudo-code)
- c와 같은 프로그래밍 언어
알고리즘의 성능 분석
- 수행 시간 측정
- 두개의 알고리즘의 실제 수행 시간을 측정하는 것
- 실제로 구현하는 것이 필요
- 동일한 하드웨어를 사용하여야 함
- 알고리즘의 복잡도 분석
- 직접 구현하지 않고서도 수행 시간을 분석하는 것
- 알고리즘이 수행하는 연산의 횟수를 측정하여 비교
- 일반적으로 연산의 횟수는 n의 함수
- 시간 복잡도 분석: 수행 시간 분석
- 공간 복잡도 분석: 수행시 필요로 하는 메모리 공간 분석
수행 시간 측정
복잡도 분석
시간 복잡도는 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 숫자로 표시
빅오 표기법
- 연산의 횟수를 대략적(점근적)으로 표기한 것으로, 빅오는 함수의 상한을 표시한다.
- 자료의 개수가 많은 경우에는 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 무시될 수 있다. 보통 시간복잡도 함수에서 가장 영향을 크게 미치는 항만을 고려하면 충분하다
- 두개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n≥n0에 대하여 |f(n)| ≤ c|g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n)=O(g(n))이다.
빅오 표기법의 예
빅오 표기법의 종류
- O(1) : 상수형
- O(logn) : 로그형
- O(n) : 선형
- O(nlogn) : 로그선형
- O(n2 ) : 2차형
- O(n3 ) : 3차형
- O(n k ) : k차형
- O(2 n ) : 지수형
- O(n!) : 팩토리얼형
시간 복잡도 크기 O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)
최선, 평균, 최악의 경우
¨ 알고리즘의 수행시간은 입력 자료 집합에 따라 다를 수 있다.
¨ 최선의 경우(best case): 수행 시간이 가장 빠른 경우
¨ 평균의 경우(average case): 수행시간이 평균적인 경우
¨ 최악의 경우(worst case): 수행 시간이 가장 늦은 경우
자료형(data type)이란?
데이터의 집합과 연산의 집합이다.
추상 데이터 타입(ADT: Abstract Data Type)은 데이터 타입을 추상적(수학적)으로 정의한 것으로, 데이터나 연산이 무엇(what)인가는 정의되지만 데이터나 연산을 어떻게(how) 컴퓨터 상에서 구현할 것인지는 정의되지 않는다.
- 객체 : 추상 데이터 타입에 속하는 객체가 정의된다.
- 연산 : 이들 객체들 사이의 연산이 정의된다. 이 연산은 추상 데이터 타입과 외부를 연결하는 인터페이스의 역할을 한다.
Ex) 추상 데이터 타입과 TV
▪TV의 인터페이스가 제공하는 특정한 작업만을 할 수 있다.
▪사용자는 TV의 내부를 볼 수 없다.
▪TV의 내부에서 무엇이 일어나고 있는지를 몰라도 이용할 수 있다.
▪사용자들은 ADT가 제공하는 연산만을 사용할 수 있다.
▪사용자들은 ADT 내부의 데이터를 접근할 수 없다.
▪사용자들은 ADT가 어떻게 구현되는지 모르더라도 ADT를 사용할 수 있다.