알고리즘 공부 Part1

알고리즘이란 무엇인가?

알고리즘이란 주어진 문제를 해결하기 위한 잘 정의된 동작들의 유한 집합 입니다.

알고리즘을 개발하는데 가장 먼저 선행되어야 할 것은 바로 주어진 문제를 잘 이해하는 것입니다. 주어진 문제 뿐만 아니라 문제가 주어지는 상황은 문제를 해결하는 데 이용 할 수 있는 자원이 됩니다.

알고리즘과 자료구조

알고리즘을 가장 적절히 한글로 표현한다면 '방법'이라고 할수 있습니다.
예를 들어 '무엇을 어떻게 하라' 라고 한다면
'무엇을'은 자료(data) : 어떠한 조직을 가지게 되는데 이를 자료구조라 합니다.
'어떻게 하라'는 알고리즘이 됩니다.

어떤 알고리즘을 선택할 것인가?

절대적으로 최상의 알고리즘은 없습니다.
알고리즘의 속도와 메모리 소요의 관계를 이해 해서 사용해야 합니다.
퀵 정렬이 빠르지만 재귀 호출이나 스택에 필요한 정보를 저장하는 방식으로 부가적인 메모리가 필요하고
선택정렬은 느리지만 메모리가 추가적으로 필요없습니다.

따라서, 상황에 따라 알맞는 것을 선택하여 사용 해야합니다.
그리고 사용빈도가 낮은 곳에는 효율성이 떨어지더라도 간단한 알고리즘이 좋습니다.

알고리즘의 분석

알고리즘을 분석하는데는 2가지 분석법이 있습니다.
바로 경험적 분석과 수학적 분석 입니다.
경험적 분석 : 흔히 쉽게 코드를 작성하여 실행시켜 비교해보는 것
수학적 분석 : 알고리즘 자체로만 분석하는 것

알고리즘은 최악의 경우와 최선의 경우를 따집니다.

최악의 경우(Worst Case) : 가장 많은 시간과 공간을 사용하는 경우
최고의 경우(Best Case) : 시간과 공간을 적게 사용하는 경우
평균적 경우(Average Case) : 평균적인 시간과 공간을 필요로하는 경우
그리고 이를 표현할때는 빅오(Ο-표기법을 사용)라는 표기법을 사용합니다.

알고리즘 분석의 단계

1.알고리즘을 판단할 수 있는 입력할 자료를 결정 합니다.

1. 알고리즘을 구성하는 동작들을 추상적이고 기본적인 동작들로 분해하여 수행시간을 분석 (CPU의 동작시간 비교)합니다.
2. 수학적으로 알고리즘을 분석 합니다.

알고리즘의 유형

1 : 입력 자료의 수에 관계 없이 일정한 실행 시간을 갖는 알고리즘
logN : 만약 입력 자료의 수에 따라 실행시간이 logN의 관계를 만족한다면 N이 증가함에 따라 조금씩 증가함
N : 입력 자료의 수에 따라 선형적으로 실행시간이 걸리는 경우
N log N : 커다란 문제를 독립적인 작은 문제로 쪼개어 각각에 대해 독립적으로 해결하고 나중에 다시 그것들을 모으는 경우
N²: 루프내에 루프
N³ : 삼중 루프
2^n : 알고리즘을 처음 개발할때 나타나는 극히 드문 현상

Ο 표기법(Big-Oh notation)

보통Ο(N²) 이런식으로 표기 최악의경우

다른 표기법

Ω(오메가) 최선의 경우
Θ(세타) 최선과 최악이 동등할때 사용

시간 소요량과 공간 소요량

공간은 메모리 혹은 디스크 사용량
시간은 실제 소요되는 시간