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



    
     [공지] 강좌를 올리실 때는 말머리를 달아주세요^ㅡ^ [29] 멍멍 02/27 16137
1578   towelroot.c (zip) 코멘팅.[1]     scube
08/18 1404
1577   levitator.c (안드로이드 루팅) 공격 분석 소스 코드 공유.[2]     scube
08/17 1428
1576   무료 정보보안 기술인재 양성 과정 교육생 모집     chanjung111
06/17 1934
1575   K-Shield 주니어 5기 모집     lrtk
06/17 1752
1574   [팁] 파이썬 2소스를 3으로 변경해주는 사이트[3]     한승재
05/13 1651
1573   구글 백링크 작업 질문요     wkatnxka
03/30 1448
1572   [팁] 우분투 미러링서버     한승재
03/09 1689
1571   [자작글] php로 상대방 IP 알아내기 [2]     한승재
02/27 2478
1570 비밀글입니다  감을못잡겠네요ㅜㅜ     잉잉잉
01/15 1
1569   데비안 계열 리눅스 의존성 깨졌을때 해결법     한승재
11/27 1898
1568   해킹길라잡이     한승재
11/02 2683
1567   홍보합니다. 신생 보안커뮤니티입니다.     kimwoojin0952
10/26 2184
1566   신기한 프로그래밍 언어[2]     koreal33t
09/06 2402
1565   윈도우,리눅스에서 내 ip를 확인해 보자 [1]     koreal33t
09/06 1885
1564   CTF 사이트[1]     koreal33t
09/06 2175
1563   자격증 (문제)사이트 [1]     koreal33t
09/06 2083
1562   [퍼온글]리눅스 기본 명령어     한승재
06/06 2669
1561   [동강][퍼온글]C언어로 Hellow world를 출력해보자![1]     한승재
05/23 2242
1560   [동강][퍼온글]가상머신에 우분투를 깔아보자     한승재
05/18 2033
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