알고리즘 기초 1

>알고리즘이란?

알고리즘 : 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법

1부터 100까지 더하는 문제가 있을때, 1+2+3+...+100로 구할 수 있겠지만

(1+100) x 100 / 2로 계산해서 구할 수 있고 이렇게 문제를 해결하는 방법을 알고리즘이라고 한다.

 

>알고리즘 표현법

슈도 코드 : 일반적인 언어로 코드를 흉내 내어 알고리즘을 써 놓은 코드

순서도 : 프로그램이나 작업의 진행 흐름을 순서에 따라 여러가지 기호나 문자로 나타낸 도표

 

>알고리즘 성능 측정 - 무엇이 좋은 알고리즘인가?

1. 정확성 : 얼마나 정확하게 동작하는지

2. 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻는지

3. 메모리 사용량 : 얼마나 적은 메모리를 사용하는지

4. 단순성 : 얼마나 단순한지

5. 최적성 : 더 이상 개선할 여지 없이 최적화 되었는지

 

많은 문제에서 알고리즘의 성능 분석 기준으로 알고리즘 작업량을 비교

덧셈 99번

100x(1+100)/2 3번 연산(덧셈 1번,곱셈 1번, 나눗셈 1번)

실제 걸리는 시간을 측정

실행되는 명령문의 갯수를 계산을 통해 복잡도 계산

 

시간 복잡도 빅오표기법

-최고차항만 선택 후 계수 생략

-O(2n+1) => O(n)

 

시간 복잡도를 통해서 미리 확인 가능함