[Algorithm] 알고리즘 기초
<< 알고리즘 >>
1. 알고리즘은 단계적 절차
2. 프로그램언어로 소스코드를 짜서 원하는 출력 결과를 얻기 위함.
3. 알고리즘은 기본적으로 프로그래밍 언어에 의존적
4. 그러나 언어에 의존적인 것이지 특정한 언어에 종속적인 것은 아님. ( C나 C++이나 JAVA , Perl , Python 등 어느언어로도 가능.)
<< 알고리즘의 기능 >>
검색 ( 데이터의 구조를 검색 ) , 정렬 ( 정해진 기준에 따라 정렬 ) , 삽입[갱신,삭제] ( 어떠한 자료 구조의 리스트에 데이터를 삽입 , 갱신 , 삭제 )
<< 알고리즘의 특성 >>
[ 명확성 ] - 알고리즘은 각각의 단계가 분명하고 명확해야 합니다. 입 출력이 명확해야 하고, 각각의 단계가 명확해야 함.
[ 한정성 ] - 알고리즘은 단계의 끝이 존재 ( 무한루프 X )
[ 가용성 ] - 알고리즘은 최대한 적은 자원을 사용해서 최대의 성능을 끌어내야 함.
[ 독립성 ] - 알고리즘은 각각의 단계가 독립적이어야 하고, 프로그래밍 언어에 독립적.
<<알고리즘 작성법>>
알고리즘에 잘 정의된 표준은 없음. 왜냐하면 알고리즘은 특정 프로그래밍 코드를 지원하기 위해서 작성되어지지 않기 때문.
알고리즘은 다들 잘 알고 있는 ( do , for , while ) , IF 등과 같이 구성.
보통, 단계별로 알고리즘을 작성하지만 항상 그렇지는 않음. 알고리즘 작성은 문제의 주체가 잘 정의 되고 난 다음에 진행되어야 함.
[ 예제 ]
step1. 더하기 시작
step2. a,b의 값을 읽어들인다.
step3. c < - a + b
step4. c를 보여준다.
step5. 종료.
설계 및 알고리즘 분석에서 일반적으로 위의 방법이 사용.
주어진 문제에 대해서 솔루션을 얻을 수 있는 알고리즘을 설계해야 함, 물론, 문제는 하나 이상의 방식으로 해결 될 수 있음.
이러한 이유로, 많은 솔루션 알고리즘은 주어진 문제에 대해서 여러가지 해결 방법이 나올수 있음
다음 단계로는 이러한 여러가지 솔루션 알고리즘을 분석하여 가장 적당한 해결방법을 구현하는 것.
<< 알고리즘 분석 >>
알고리즘의 효율은 구현 전과 구현 후 2개의 다른 단계로 분석 할 수 있음.
- 구현 전 : 알고리즘의 이론적 분석, 알고리즘의 효율은 모든 다른 요인을 고려하여 측정한다.
예를 들면, CPU 의 속도를 일정하게 하고, 구현에 영향을 미칠 수 없도록 한다.
- 구현 후 : 알고리즘의 경험적 분석, 후보 알고리즘 중 선택된 알고리즘은 프로그래밍언어를 사용해 구현하는 것을 뜻함. 실제로 대상 컴퓨터 시스템에서 실행되게 된다. 이 분석에서 시간복잡도와 공간복잡도의 통계가 수집됨.
<< 알고리즘 복잡성 >>
X는 알고리즘이고, n은 입력 데이터의 크기. 알고리즘 X가 사용되는 시간과 공간 (X)의 효율을 결정하는 두개의 주요 요인이 있다.
1. 시간 요소 - 정렬 연산 등에서 사용하는 반복 루프안의 횟수를 셈.
2. 공간 요소 - 공간 알고리즘에 의해 요구되는 최대의 메모리 용량을 계산해서 측정.
<< 공간 복잡도 >>
알고리즘이 진행되는 동안 요구되는 메모리의 공간을 의미함.
요구되는 공간은 다음의 두 요소의 합과 같다.
- C1. 문제의 크기와 무관한 특정 데이터 및 변수를 저장하기 위해 필요한 공간
- C2. 문제의 크기에 따라 변수들에 의해 요구되는 공간 EX ) 동적할당
알고리즘 P의 공간복잡도 S(P)는 S(P) = C + SP(I) 여기서, C는 고정된 부분 ( C1 ) S(I)는 알고리즘의 가변부분 ( C2 )
[ 예제 ]
알고리즘명 : SUM( A , B )
step1. 시작
step2. C <- A + B + 10
step3. 종료
여기서, 위의 알고리즘은 세 개의 변수 A, B, C 와 하나의 상수를 가지고 있음.
따라서 S(P) = 1+3.
이제 공간은 주어진 변수와 상수의 유형, 데이터의 유형에 따라서 달라짐.
<< 시간 복잡도 >>
알고리즘의 시간 복잡도는 알고리즘이 실행완료 까지의 시간의 양을 나타냄.
요구시간은 T(n) 으로 정의하고 T(n)은 각각 단계의 수로 측정 가능하고 각각 단계는 일정 시간을 소모함.
예를 들어, 2개의 integer을 더할때 n 개의 단계를 거친다면, 그결과 총 계산 시간은 T(n) = c * n 이다.
여기서 c는 2개의 integer을 더하는데 걸리는 시간.
여기서 T(n) 의 입력 크기가 증가함에따라서 시간은 선형적으로 증가.