1581, 72/80 회원가입  로그인  
   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 : 7726     Date : 2015/07/21 01:11



    
161   C언어 getch()문     tjdans174
05/20 8375
160   모의해킹쪽 근무하시는 멘토쫌해주실분없나요?? 기술가르쳐달라는건아니고요..[3]     gurals53
06/04 8327
159   해킹 자문 구합니다      negro
06/10 7423
158   해킹 해주실분 구합니다     hitemple
06/12 8804
157   소스값과 극한을 이용한 확률 lim x가 극한으로 가는 사건의 필연성     jjang2437
06/14 8104
156   해킹에대해[3]     kbh2790
07/04 7364
155   arp스푸핑에 관해[1]     alscjf7612
07/17 8126
154   ARP스푸핑과 ARP캐시 포이즈닝의 차이점     alscjf7612
07/17 9223
153   잘 부탁드립니다.     alscjf7612
07/17 7189
152   잘부탁드려요~~     alscjf7612
07/17 7113
151   매우 기초적으로 알아야 할 레지스터 정보 요약[2]     disnwkdl420
07/21 7988
  알고리즘에 대해     disnwkdl420
07/21 7725
149   웹해킹 6번 문제[2]     disnwkdl420
07/21 9464
148   컴활 2급[1]     disnwkdl420
07/21 8720
147   해커 스승 구합니다[5]     dayt0612
08/23 8116
146   저기요제가해킹을배울려고하는데뭐부터시작해야할지모르겠어요 ;;[4]     paaaaa7895
08/26 8774
145   안녕하세요^^     kakaman
09/11 6408
144   네트워크 OSI7계층 간단정리[1]     poiu2069
09/16 8619
143   2-Tier , 3-Tier 간단 설명     poiu2069
09/16 7443
142   [JAVA] 에서 abstract 와 interface 차이점     poiu2069
09/16 6571
[1]..[71] 72 [73][74][75][76][77][78][79][80]

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