|
http://www.hackerschool.org/HS_Boards/zboard.php?id=Free_Lectures&no=8133 [복사]
[알고리즘의 개념]
알고리즘이란 문제를 해결하는 절차이다. 일반적인 요리법에 비교할 수 있다.
아침에 맛있는 토스트 하나를 먹는다고 생각해보자.(나 한테는 매우 맛있다.)
1. 토스트기를 찾고, 잼, 숟가락, 우유, 빵을 준비한다.
2. 빵을 토스트기에 넣어 굽는다.
3. 빵을 꺼내서 숟가락으로 잼을 바른다.
4. 그 위에 빵을 덮고 우유와 함께 냠냠쩝쩝하면 된다.
개념적을 이해하기 매우 쉬울 것이다. ^^
[알고리즘의 중요성]
알고리즘이 왜 중요하다는 것일까? 알고리즘에 따라 문제를 해결하는 속도가 달라진다.
수학 문제를 풀 때를 예를 들어보자.
[문제] 삼각형의 넓이를 구하자!
- 방법 1
1. 인터넷으로 삼각형의 넓이를 구하는 방법을 알아본다.
2. 푼다.
- 방법 2
1. 집을 나간다.
2. 학교 선생님께 찾아간다.
3. 묻는다.
4. 맞는다.
5. 집으로 온다.
6. 교과서를 본다.
7. 푼다.
2가지의 방법 중 여러분은 무엇을 선택하겠는가? 당연히 방법 1이다.
큰 그릇이 만들어지기까지는 오랜 시간이 걸린다고 하면서 방법 2를 택하지는 말자.
실제 프로그램 상에서는 알고리즘의 차이가 답을 구해내는 시간이 1년도 차이가 날 수 가 있다.(사실이다.)
[시간 복잡도 - time complexity(영어 공부도 열심히 하자 ^^)]
시간 복잡도는 알고리즘의 실행시간에 대해 수식으로 나타낸 것이다.
나타내는 방식에 따라 n log n, n제곱, n3제곱 등이 있다.
반복문을 예를 들어 알아보자.
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
단위 연산
}
}
이 경우 단위 연산을 실행하는 횟수는 n * n, 즉 n제곱이다.
다른 경우를 한 번 보도록 하자.
for(i = 1; i <= n; i++) {
for(j = i; j <= n; j++) {
단위 연산
}
}
이 경우 단위 연산을 실행하는 횟수는 (n제곱 + n) / 2라고 한다.
그런데 이렇게 표기하는 것은 한 눈에 알아보기 어렵다.
그래서 시간 복잡도를 나타낼 때 O체계를 나타낸다.
위에서 나타낸 수식은 O체계로는 모두 n제곱으로 표현할 수 있다.
수식에서 최대 차수로 나타낸다는 것을 알 수 있을 것이다.
계수가 1, 1/2로 다르더라도 최대 차수만을 이용한다.
왜 나머지는 무시하고 최대 차수만을 이용하는 것일까?
이유는 당연히 실행 시간에 있다.
시간 복잡도가 100n인 알고리즘과 0.1n제곱인 알고리즘이 있다고 하자.
눈으로 보기에는 후자가 더 빠를 것처럼 보인다.
하지만 n이 커지면 전자가 더 빠른 알고리즘이 된다.
계수 보다는 최대 차수가 알고리즘에 큰 영향을 미친다. |
Hit : 7872 Date : 2015/07/21 01:11
|
1581, 
19/80 
