자료구조
자료구조란 자료들을 표현하여 정리한 구조를 말한다. 즉 자료구조 + 알고리즘 = 프로그램이 되는 것이다.
예를 들어 최대값을 구하는 프로그램은 배열(자료구조) + 순차탐색(알고리즘)를 통해 만들 수 있다.
일상생활에서의 예 |
해당하는 자료구조 |
그릇을 쌓아서 보관하는 것 |
스택 |
마트 계산대의 줄 |
큐 |
버킷 리스트 |
리스트 |
영어사전 |
사전 |
지도 |
그래프 |
컴퓨터의 디렉터리 구조 |
트리 |
알고리즘
컴퓨터로 문제를 풀기 위한 단계적인(순차적인) 절차를 말한다.
문제를 풀기 위해 해야 할 일은 두가지가 있다.
1. 문제를 해결할 수 있는 방법을 고안.
2. 컴퓨터가수행할 단계 절차를 기술하는 것.
자료구조와 알고리즘은 미접한 관계가 있어서 자료구조가 결정되면 그 자료구조에서 사용할 수 있는 알고리즘이 결정된다.
알고리즘의 조건
- 입력 : 0개 이상의 입력이 존재해야함
- 출력 : 1개 이상의 입력이 존재해야함. //y? 문제를 해결했다는 것은 결과를 도출했다는 의미 도출한 것으 출력으로 볼 수 있게!
- 명백성 : 모호하지 않고 명확해야한다.
- 유한성 : 한정된 수의 단계 후에는 반드시 종료되야 한다.
- 유효성 : 실행 가능한 연산이여야 한다.
알고리즘을 기술하는 방법 4가지가 있다. => 1. 자연어 2. 흐름도 3. 의사코드(pseudo-code) 4. 프로그래밍언어
이 중 의사코드를 사용하여 알고리즘을 기술하는 것을 권장한다.
=>y? 1번을 사용할 경우 약간의 모호성이 존재한다.
2번의 경우 단순하고 보기 편하지만 코드가 복잡해질 수록 기술하기 힘들다.
4번의 경우 명백한 의미를 가지고 있어 알고리즘을 기술할 때 안성맞춤이지만 알고리즘의 핵심내용에 집중하기 어렵다.
3번의 경우로 작성할 경우 알고리즘의 핵심 내용에 집중할 수 있다는 장점이있다! //대입연산자(=)를 <-로 표현
의사코드를 이용하여 배열에서 최대값을 찾는 알고리즘을 표현한 예
ArrayMax(list N):
largest <- list[0]
for i <- 1 to N-1 do
if(list[I] > largest
then largest <-list[i]
return largest
추상자료형(ADT:abstract data type)
자료형은 데이터의 종류를 의미한다. 스택, 큐, 리스트, 트리와 같은 새로운 자료형을 추가하여 나타낸 것을 말한다.
즉, 추상적, 수학적으로 자료형을 정의한 것으로. 데이터나 연산이 무엇(what)인지는 정의되지만 데이터나 연산을 어떻게(how) 컴퓨터 상에서 구현할 것인지는 정의되지 않는다. //C++의 클래스의 추상화 & 정보은닉과 비슷한 느낌
ex) 선풍기 사용설명서에 정지, 미풍, 강풍 등의 기능설명과 사용법은 나와있지만(what)
버튼을 눌렀을 때 어떻게(how) 작동하는지는 나와있지 않는다.
추상자료형을 만들 때 어던 데이터를 이용하여 어떻게 연산할지 파악하고 체크하는 것이 필요하다.
자료형은 데이터집합과 연산집합을 갖는다.
알고리즘의 성능분석
알고리즘의 성능 분석은 복잡도를 이용하여 구할 수 있다.
복잡도에는 1. 시간복잡도와 2. 공간복잡도로 나뉜다. 1은 수행시간을 2는 메모리 공간을 얼만큼 차지 하는지에 따라 좌우된다.
왜? 성능을 분석해야할까?
첫 번째 이유는 데이터 수에 구애받지 않는 좋은 알고리즘을 모색하기 위해서. 두 번째 이유는 사람들이 빠른 프로그램을 선호하기 때문이다. 그래서 수행시간이 짧으면서 컴퓨 내의 자원을 덜 사용하는 효율적인 알고리즘을 모색해야한다!
프로그램이 작을 댄 직접 수행해보며 소요시간을 예측할 수 있지만 크고 코드가 복잡할 경우에는 비효율적이다.! 그래서 알고리즘 복잡도 분석(complexity analysis)를 이용하여 구한다.
- 시간 복잡도 함수
연산의 수행 횟수를 이용하여 알고리즘을 분석한다. // 연산 수행 수가 적을 수록 좋은 알고리즘
알고리즘 a |
알고리즘 b |
알고리즘 c |
sum <- n*n; |
for i<-1 to n do |
for i<-1 to n do |
a의 연산 수행 횟수는 *와 = 총 2번,
b의 연산 수행 횟수는 + n번, = n번 (for문 도니까) 2n번,
c의 연산 수행 횟수는 + n^2번, = n^2번 총 2n^2번
이런 삭으로 연산횟수를 이용하여 비교하고 결과를 바탕으로 효율적인 알고리즘을 선택할 수 있음.
시간의 복잡도를 표현하는 표기법
1. 빅오 표기법 // 최대의 연산을 정하는 것(n의 값에 따라 함수의 상한 표시)
- 입력 자료의 개수가 큰 경우 시간 복잡도 함수T(n)의 차수가 큰 항이 전체 값을 주도한다.
- 차수가 큰 항만 고려한다.
- 알고리즘이 n에 비례하는 수행시간을 가진다 == 알고리즘의 시간 복잡도가 O(n)이다. //O(n)은 "빅오 of n"
- ex) f(n) = n+1, g(n) = C ( f(n) )이다. c를 상수라 할 대 f(n) <= Cg(n) C가 1이면 ==, C가 1이상이면 <.
//시간 복잡도 함수를 구하려는 f(n)은 결국 g(n)보다 크거나 작다. 빅오로 표현하면 O(g(n)) //g(n)보단 작게 걸린다는 의미.
빅오 표기법은 입력의 개수에 따른 기본 연산의 수행 횟수를 개략적으로 나타낸 것이므로 이것을 이용하면 알고리즘의 대략적인 수행시간을 추정해 볼 수있다.
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)
2. 빅오메가 표기법 //n의 값에 따른 함수의 하한 표시
- ex) 3n + 3 >= 3n 일때, f(n) >= g(n). 3n + 3 = 오메가(n)
3. 빅세타 표기법 //n의 값에 따른 함수의 상, 하한 표시 -가장 정밀함 그러나 빅오 표기법을 많이 사용함.
본 내용은 C언어로 쉽게 풀어쓴 자료구조 개정 3판. 생능출판사을 출처로 한다.
댓글