1579, 8/79 회원가입  로그인  
   disnwkdl420
   알고리즘에 대해

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 : 5722     Date : 2015/07/21 01:11
[불법/스팸글로 신고하기]



    
1439   네트워크 OSI7계층 간단정리     poiu2069
09/16 6593
1438   안녕하세요^^     kakaman
09/11 4662
1437   저기요제가해킹을배울려고하는데뭐부터시작해야할지모르겠어요 ;;[4]     paaaaa7895
08/26 6508
1436   해커 스승 구합니다[5]     dayt0612
08/23 6000
1435   컴활 2급[1]     disnwkdl420
07/21 6073
1434   웹해킹 6번 문제[2]     disnwkdl420
07/21 6999
  알고리즘에 대해     disnwkdl420
07/21 5721
1432   매우 기초적으로 알아야 할 레지스터 정보 요약[2]     disnwkdl420
07/21 6030
1431   잘부탁드려요~~     alscjf7612
07/17 5161
1430   잘 부탁드립니다.     alscjf7612
07/17 5133
1429   ARP스푸핑과 ARP캐시 포이즈닝의 차이점     alscjf7612
07/17 7253
1428   arp스푸핑에 관해[1]     alscjf7612
07/17 5954
1427   해킹에대해[3]     kbh2790
07/04 5507
1426   소스값과 극한을 이용한 확률 lim x가 극한으로 가는 사건의 필연성     jjang2437
06/14 6199
1425   해킹 해주실분 구합니다     hitemple
06/12 6662
1424   해킹 자문 구합니다      negro
06/10 5510
1423   모의해킹쪽 근무하시는 멘토쫌해주실분없나요?? 기술가르쳐달라는건아니고요..[3]     gurals53
06/04 6505
1422   C언어 getch()문     tjdans174
05/20 6486
1421   잘 가르쳐 주실분 한분 구해요 ㅠㅠ [3]     dss02158
05/18 6785
1420   해커스승구해요..잘부탁드리겠습니다     dkssud1058
05/04 6579
[1][2][3][4][5][6][7] 8 [9][10]..[79]

Copyright 1999-2021 Zeroboard / skin by Hackerschool.org / Secure Patch by Hackerschool.org & Wowhacker.com