알고리즘(Algorithm)이란?

처음에 내가 프로그래밍에 재미를 느끼게 된 것이 알고리즘(Algorithm) 때문이 었다.

군대 제대후 공부를 하기 위해 처음 들어간 동아리가 ACM-ICPC 대회를 준비하는 동아리였고 C언어를 처음 배우고

ACM 문제를 접하며 프로그래밍에 재미를 느꼈다. 

그후 멤버십 생활 현재 회사에 들어와서까지 어딜가나 알고리즘은 항상 중요시 생각 되는부분이었다.

C언어를 배우고 처음 접한게 ACM문제 였고 나름 동아리 생활을 통해 대회도 나가보고 멤버십에서 시험도 많이 봤지만 

문제를 엄청 잘 풀지는 못하였다. 

문제를 많이 풀어보는 것도 코드를 잘 짜는 것도, 중요하지만 알고리즘에 원론적인 내용과 이론적인 부분을 잘 알지 못한 까닭이라고 생각한다.

그래서 지금부터 알고리즘에 대한 원론적인 내용부터 여러가지 이론들까지 처음부터 꼼꼼하게 다시 공부해보려고 한다.

1.알고리즘

-어떠한 문제를 해결하기 위한 여러 동작들의 유한한 모임

위키백과에 나와있는 알고리즘에 대한 내용이다. 

여기서 중요한 것은 어떠한 문제를 해결하기 위한  여러 동작들의 유한한 모임이란것 이다.

내가 지금까지 생각했던 것과는 약간 틀리다. 나는 알고리즘의 정의는  어떠한 문제를 해결하기 위한 최선,최적의 방법이라고 생각하고 있었지만

실제 정의는 저것이다.

-알고리즘의 조건

• 입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.
• 출력 : 적어도 1개 이상의 결과를 내어야 한다.
• 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.
• 유한성(종결성) : 유한 번의 명령어를 수행 후(유한 시간 내)에 종료한다.
• 효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다.

다음은 알고리즘의 조건이다. 위의 조건만 만족하면 알고리즘이라 정의할 수 있겠다.

물론 조건에 없다고 알고리즘이 문제를 해결하기만 하면 되는 것은 아닌거 같다

좀더 성능이 좋은 알고리즘은 수행시간이 짧아야하고 효율적이어야 한다.

2.알고리즘의 성능 

알고리즘의 성능이란 같은 알고리즘이라도 계산속도가 좀더 빠르고 메모리가 적게드는 것을 말한다.

요즘에 컴퓨터가 많이 발전해서 연산속도가 빠르고 메모리가 크지만 그렇다고 계산속도와 메모리를 생각하지 않고 프로그램을 짜면 안된다.

그럼 무조건 빠른것만 중요할까?

다음 두개의 코드를 비교해보자

                             

다음은 똑같이 Hello를 10번찍는 두개의 프로그램중 어떤 것이 더 성능이 좋은 프로그램일까?

누가봐도 2번째 코드가 더 좋은 코드일 것이다. 

하지만 연산속도로만 보면 첫번째 코드가 더 빠르다 for문 연산이 없기때문에

그렇다면 왜 2번째 코드가 더 좋은 코드일까?

10번찍엇을 때를 말고 수억번을 찍었을 때를 생각해보면 물론 코드의 간결성도 있고 여러가지 이유가 있지만 제외하고 메모리만 생각해보았을때

실제 명령어가 수억줄이나 메모리에 코드섹션에 들어가기 때문에 

훨씬더 무거운 프로그램이 될 것이다.

이토록 성능이좋은, 보다 효율적인 알고리즘이란 시작하여 결과가 나올 때까지의 실행시간이 짧으면서 메모리의 자원을 덜 사용하는 알고리즘이다.

물론 알고리즘에서 실행 시간이 메모리 공간보다 훨씬 더 중요하게 생각되지만 메모리를 적게 쓰는 것도 생각해야 할 부분이다.

-알고리즘의 분석기준

• 정확성 : 적당한 입력에 대해서 유한 시간내에 올바른 답을 산출하는가를 판단.
• 작업량 : 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정. 해결하고자 하는 문제의 중요 연산이 여러개인 경우에는 각각의 중요 연산들의 합으로 간주하거나 중요 연산들에 가중치를 두어 계산
• 기억 장소 사용량
• 최적성 :그 알고리즘보다 더 적은 중요 연산을 수행하는 알고리즘은 없는가? 최적이란 가장 '잘 알려진' 이 아니라 '가장 좋은'의 의미이다
• 복잡도.

3.알고리즘의 복잡도 분석 방법 

여러가지 알고리즘 중에서 제일 효율적인 하나를 선택해야 하는 경우에, 직접 구현하지 않고서도 대략적으로 알고리즘의 효율성을 비교할 수 있는 방법이

알고리즘의 복잡도 분석(complexity analysis)이다.

알고리즘의 복잡도 분석은 구현하지 않고도 모든 입력을 고려하는 방법이고, 실행하드웨어나 소프트웨어 환경과는 관계없이 알고리즘의 효율성을 평가할 수 있다.

알고리즘의 분석에서는 2가지 측면을 고려할수 있다

 1.시간복잡도(time complexity)

 2.공간복잡도(space complexity)

 대게 알고리즘의 복잡도를 이야기할 때는 시간복잡도를 말한다. 이유는 위에서 언급했듯이 알고리즘은 시간을 더 중요시 생각하기 때문이다.

1)시간복잡도(time complexity)

-시간 복잡도는 알고리즘의 절대적인 실행 시간을 나타내는 것이 아니라 알고리즘을 이루고 있는 연산들이 몇 번이나 실행되는지를 

숫자로 표시한다.

-연산의 실행횟수는 입력의 개수 n에 따라게 변하게 된다. 연산의 개수를 입력의 개수 n의 함수로 나타낸 것을 시간 복잡도 함수라 하고

 T(n)이라고 표기한다.

Ex) n*n을 계산해보자

A는  그냥 n*n으로 계산한 방법

B는  n을 n번 더한 방법

C는 1을 n*n번 더한 방법이다.

       

       위의 3가지 알고리즘 중에서 가장 효율적인 알고리즘을 선택하기 위하여, 알고리즘을 구현하지 않고 알고리즘 분석

       기법을 통해 실행속도를 예측해보자 

       예를 들어 입력이 10이라고 했을 때 A는 2번 B는 21번 C=201번을 연산한다.(for 문의 연산을 제외했을 때) n의 숫자가 커지면 커질수록 연산의 횟수는

       더크게 차이나여 알고리즘 실행속도는 더 크게 차이난다.

2) 빅오 표기법

시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 

빅오 표기법(big-oh notation)이라고 한다.

빅오 표기법은 n의 값에 따른 함수의 상한 값을 나타내는 방법이다. 이론은 빅오표기법의 정의를 보면 알 수 있지만

귀찮으니 생략한다.

시간복잡도 함수가 f(n)=5  이면 O(1)이다.

시간복잡도 함수가 2n+1이면 O(n)이다.

시간복잡도 함수가 f(n) = 3n^+100 이면 O(n^)이다.

빅오 표기법을 사용하면 시간 복잡도 함수의 증가에 많이 기여하지 못하는 항을 생략함으로써 시간 복잡도를 간단한게 표시할 수 있다.

빅오표기법을 얻는 간단한 방법은 최고차 항만 남기고 다른 항들과 상수를 버리는것이다. 궁극적으로 최고차 항의 계수도 버리고 최고차 항의 

차수만을 사용한다. 

이처럼 최고차 항만 남기고 다른 항들과 상수를 버리는 것은 다른 항들과 상수는 시간 복잡도 함수의 증가에 많이 기여하지 못한다는 뜻이다

입력 값이 작을 때는 영향을 끼칠 수 있겠지만 입력값이 커지면 커질수록 다른항들이나 상수가 실행속도에 영향을 미치는 부분은 미비하다.

많이 쓰이는 빅오 표기법 (실행시간이 빠른 순)

• O(1) : 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘 (상수형)
• O(log N) : 입력 자료의 크기가 N일경우 log₂N 번만큼의 수행시간을 가진다. (로그형)
• O(N) : 입력 자료의 크기가 N일경우 N 번만큼의 수행시간을 가진다. (선형)
• O(N log N) : 입력 자료의 크기가 N일경우 N*(log₂N) 번만큼의 수행시간을 가진다. (선형로그형)
• O(N²) : 입력 자료의 크기가 N일경우 N² 번만큼의 수행시간을 가진다. (2차형)
• O(N³) : 입력 자료의 크기가 N일경우 N³ 번만큼의 수행시간을 가진다. (3차형)
• O(2ⁿ) : 입력 자료의 크기가 N일경우 2^N 번만큼의 수행시간을 가진다. (지수형)
• O(n!) : 입력 자료의 크기가 N일경우 n*(n-1)*(n-2)... * 1(n!) 번만큼의 수행시간을 가진다. ex)외판원 문제(TSP)의 기본적인 해법(팩토리얼형)

빅오표기법은 최소 차수를 상한으로 표시한 표기법이다

이위에도 함수를 하한으로 표시하는 빅오메가 표기법 

동일한 함수로 상한과 하한을 만들수 있는 빅세타 표기법 등이 있다

3개의 표기법 중에 가장 정밀한 것은 빅세타 표기법이다 (상한과 하한 )

그러나 통상적으로 빅오 표기법을 많이 사용한다. 단, 빅오 표기법에서는 최소 차수로 상한을 표시한다고 가정한다.