자료구조 : 사람들이 사물을 정리하여 저장하는 것과 마찬가지로 프로그램에서도 자료들을 정리하여 보관하는 여러 가지 구조들이 있다.
스택 : 식당에서 그릇을 쌓는 것처럼 자료들을 쌓아서 정리하는 구조 맨 위에서만 자료를 추가하거나 제거할 수 있다.
큐 : 마트 계산대의 줄에 해당하는 자료구조 먼저 도착한 자료가 먼저 빠져나감
알고리즘 : 컴퓨터로 문제를 풀기 위한 단계적인 절차, 특정한 일을 수행하는 명령어들의 집합
컴퓨터 프로그램 = 자료구조 + 알고리즘
아래는 배열에 저장된 점수들 중 가장 높은 점수를 returnreturn 하는 함수이다. 아래 함수를 통해 책에서는 자료구조와 알고리즘을 주석으로 표시하여 보았다.
int get_max_score(int n) // 학생의 숫자는 n
{
int i, largest;
largest = scores[0]; // 알고리즘
for (i = 1; i < n; i++) {
if (scores[i] > largest) {
largest = scores[i];
}
}
return largest;
}
알고리즘에는 입력, 출력, 명백성, 유한성, 유효성이 있어야 한다고 한다.
입력 : 0개 이상의 입력이 존재하여야 한다.
출력 : 1개 이상의 출력이 존재하여야 한다.
명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다.
유효성 : 각 명령어들은 종이와 연필, 또는 컴퓨터로 실행 가능한 연산이어야 한다.
알고리즘을 기술하는 데 4가지 방법이 있다고 한다.
1. 한글이나 영어 같은 자연어
2. 흐름도(flowchart)
3. 의사 코드(pseudo-code)
4. 프로그래밍 언어
아래는 배열에서 최댓값을 찾는 알고리즘을 의사코드로 표현한 예이다..
ArrayMax(list, N) :
largest<-list[0]
for i<-1 to N-1 do
if list[i]>largest
then largest<-list[i]
return largest알고리즘의 성능 분석
1. 효율성 : 처리해야 할 자료의 양이 많기 때문에 알고리즘의 효율성이 더욱 중요하게 된다.
2. 수행속도 : 사용자들은 여전히 빠른 프로그램을 선호한다.
다음은 프로그램의 수행시간을 측정하는 코드이다.
/*
start 측정 시작 시간 stop 측정 종료 시간
duration = 종료시간에서 시작시간을 빼서 초로 나눈 것
프로그램의 수행시간을 측정하는 알고리즘
단점 : 반드시 똑같은 하드웨어와 실제로 구현하고 테스트가 필요함.
간단한 코딩이라면 가능 하겠지만 어마어마한 코딩이라면...
*/
int main(void)
{ clock_t start, stop;
double duration;
start = clock(); // 측정 시작
for (int i = 0; i < 1000000; i++) // 의미 없는 반복 루프
;
stop = clock(); // 측정 종료
duration = (double)(stop - start) / CLOCKS_PER_SEC;
printf("수행시간은 %f초입니다.\n", duration);
return 0;
}시간복잡도 : 알고리즘의 수행시간 분석
공간복잡도 : 알고리즘이 사용하는 기억공간 분석
시간복잡도 함수 T(n) : 연산의 수를 입력의 개수 n의 함수로 나타낸 것 n이 커질수록 알고리즘 간의 차이는 커지게 된다.
빅오 표기법 간단한 방법 : 다항식의 최고차항만을 남기고 다른 항들과 상수항을 버리는 것 계수도 버리고 단지 최고차항의 차수만 사용
아래는 빅오 표기법에 의한 알고리즘의 수행시간을 비교한 것이다.
O(1) < O(log(n)) < O(n) < O(n * log(n)) < O(n ^ 2) < O(2 ^ n) < O(nl)
빅오메가 : 빅 오메가는 빅 오와는 반대되는 개념, 대개 최선의 경우 빅오는 "너는 언젠가 내 안의 함수보다 작아지게 될 거야"라고" 의미하는 것이라면, 빅 오메가는 "너는 언젠가 내 안의 함수보다 커질 거야" 정도로 해석
빅세타 : 빅 세타는 빅 오와 빅 오메가의 공통부분, 최소와 최악의 중간인 평균적인 복잡도, 빅 세타는 "너는 내 안의 함수와 동등한 비율로 증가해"라고" 의미하는 것
최악 : 알고리즘의 수행시간이 가장 오래 걸리는 경우
최선 : 수행시간이 가장 적은 경우
평균 : 모든 입력을 고려 각 입력이 발생하는 확률을 고려하여 평균적인 수행시간 의미
보통 최악의 경우를 통해 아무리 느려도 이 정도는 안 된다 이런 느낌..?
관심이 있으신 분들에게 유용한 정보였길 바라며
다음은 1장 퀴즈와 연습문제 해설을 가져오도록 하겠습니다.