프로그래밍대회에서 배우는 알고리즘 문제해결전략 정리

알고리즘의 시간복잡도 분석

4.1 도입

빠른 알고리즘을 만들기 위해 가장 먼저 해야할 일은 알고리즘의 속도를 어떻게 측정할지를 정하는 것 이다. 속도를 비교하는 가장 직관적인 방법은 가각의 프로그램으로 구현 후, 입력에 대해 프로그램의 수행 시간을 측정하는 것이다.
그러나 실행시간은 알고리즘의 속도 측정 기준으로 하기엔 부적합하다. 첫째 프로그래밍의 수행 시간은 사용한 프로그래밍 언어, 하으뒈어는 물론이고 운영체제, 컴파일러까지 많은 요소에 따라 바뀔 수 있기 떄문이다. 둘때, 프로그램의 실행 수행 시간은 다양한 입력에 대한 실행시간을 반영하지 못한다

반복문이 지배한다.

지배한다(dominate) : 한 가지 항목이 전체의 대소를 좌지우지 하는 것을 지배한다고 표현
알고리즘의 수행 시간을 지배하는 것은 반복문 이다. 예로 짧은 거리를 달릴 때는 자저거거가 빠를 수 있는 것처럼 입력 크기가 작을때는 반복문 외의 다른 부분들이 갖는 비중이 클 수 있지만, 입력 크키가 커지만 커질 수록 반복문이 알고리즘 수행 시간을 지배한다.
알고리즘 수행 시간을 반복문이 수행되는 횟수 로 측정한다. 이때, 반복문의 수행 횟수는 입력의 크기에 대한 함수로 표현 한다.

4.2 선형 시간 알고리즘

다이어트 현황 파악:이동 평균 계산하기

수행 시간은 N에 정비례 한다. 선형 시간에 실행되는 알고리즘의 경우 대게 우리가 찾을 수 있는 알고리즘 중 가장 좋은 알고리즘인 경우가 많다.

4.3 선형 이하 시간 알고리즘

선형 전 사진 찾기

입력된 자료를 모두 한 번 훑어보는 데에는 입력의 크기에 비례하는 시간, 즉 선형시간이 걸린다.
그러나 입력자료를 다 보지 않고도 빠르게 동작하는 알고리즘이 존재한다.
예) 유명한 연예인이 있는데 코 성형을 언제 했는지 가능한 ㅂ정확하게 알려면 시중에 있는 사진을 몇장이나 확인해야 할까?
- 가장 좋은 법 : 사진들을 항상 절반으로 나누고, 가운데 있는 사진을 본다. 그리고 그 가운데 사진에서 코를 성형하지 않은 상태라면 이전 사진은 보지 않고 이후의 사진들만 체크하면 된다.
- 매번 절반씩 나누니까 log<sub>2</sub> 시간이 걸린다. (줄여서 lg)
- lg는 매우 느리게 증가하는 함수이다.
입력 크기가 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘을 선형 이하 시간 알고리즘 이라고 한다.
이진탐색

4.4 지수 시간 알고리즘

다항 시간 알고리즘

N^{n</sub> 처럼 반복문의 수행 횟수를 입력 크키의 다향식으로 표현 할 수 있는 알고리즘을 다항 시간 알고리즘이라고 한다.}
다항 시간이라는 하나의 분류에 포함되는 알고리즘 간에 엄청나게 큰 시간 차이가 날 수 있다.
알러지가 심한 친구들
예) N명의 친구를 초대하려고 한다. 할줄 하는 M 가지의 음식 중에서 친구들이 각각 알러지때문에 먹지 못하는 음식들을 제외하고 모두가 먹을 수 이:ㅆ는 음식을 만들려면 몇개의 음식을 만들어야 할까?
모든 답 후보를 평가하기
위의 예제의 경우 모든 음식을 한꺼번에 한다면 모두가 음식을 하나씩 먹을 수 있으나, 구체적으로 더 적은 종류의 음식만을 준비하고 싶을 경우 를 찾아보자는 것이다. 이처럼 가장 좋은 답을 찾는 문제들을 풀때 가장 간단한 방법은 모든 답을 일일이 고려하는 것 이다.
재귀호출을 이용하는 방법이있다.

지수 시간 알고리즘

M가지의 음시마다 만든다, 만들지 않는다는 선택지가 있으니 답은 모두 2^M 가지 이다. 이처럼 지수함수는 알고리즘의 전체 수행시간에 엄청난 영향을 미친다.
M이 하나 증가할때마다 걸리는 시간이 배로 증가하는 알고리즘들은 지수 시간 에 동작한다고 한다. 지수 시간은 가장 큰 수행시간 중 하나로, 입력 크기에 따라 다항시간과는 비교도 안되게 빠르게 증가한다.

소인수 분해의 수행 시간

아직 정확하게 무슨 개념인지 감이 안옴

4.5 시간 복잡도

시간 복잡도가 높다 = 입력의 크기가 증가할때 알고리즘 수행시간이 더 빠르게 증가한다는 의미
시간 복잡도가 낮다고 언제나 더 빠르게 동작하는 것은 아니다. 입력 크기가 충분히 작을 때는 시간 복잡도가 높은 알고리즘이 더 빠르게 동작할 수도 있다. 시간 복잡도가 낮은 알고리즘은 입력이 커지면 커실수록 더 효율적이게 된다.

입력 종류에 따른 수행 시간의 변화

입력 크기가 수행 시간을 결정하는 유일한 척도는 아니다. 입력이 어떤 형태로 구성되어 있는지도 수행 시간에 영향을 준다.
입력 종류에 따라 수행시간이 달라지는 경우를 고려하기 위해 최선/최악의 경우, 그리고 평균적인 경우에 대한 수행시간을 따로 계산한다.
- 최선의 수행 시간 : 찾으려는 원소가 맨 앞에 있을 때
- 최악의 수행 시간 : 찾으려는 원소가 맨 나중에 있어서 모든 배열을 반복
- 평균적인 경우의 수행 시간 : 모든 입력의 등장 확률이 모두 같다고 가정
많은 경우 두 기준을 따로 구분하지 않고 쓰는데 여러 알고리즘에서 이 두 기준이 거의 같이 때문

점근적 시간 표기 : O 표기

가장 깊은 중첩된 반복문만을 고려한 것처럼 전체 수행 시간에 큰 영향을 미치지 않는 상수 부부능 무시하고 반복문의 반복 수만 고려한다.
빅 O 표기법 (Big-O Notation) : 알고리즘의 수행 시간을 표기 , 가장 빨리 증가하는 항만을 남기고 나머지를 다 버리는 표기법 - 2^NM = O(2^NM) - N² M + NlgM + NM² = O(N²M + NM²) : 어느쪽이 더 빠르게 증가한다고 볼 수 없기 때문에 둘다 O 표기에 포함 - 42 = O(1) : 상수시간 알고리즘

O 표기법의 의미 : 대략적으로 함수의 상한을 나타냄

시간 복잡도 분석 연습

선택 정렬 : 모든 i 에 대해 A[i…N-1]에서 가장 작은 원소를 찾은 뒤, 이것을 A[i]에 넣는 것을 반복
- 평균적인 경우 : O(N²)
삽입 정렬 : 전체 ㅂ재열 중 정렬되어 있는 부분 배열에 새 원소를 끼어넣는 일을 반복하는 방식으로 동작
- 최선의 경우 : O(N) 처음부터 이미 정렬된 배열이 주어진 경우
- 최악의 경우 : O(N²) 역순으로 배열이 주어진 경우
결과적으로 입력이 임의의 순열이라고 할때, 대부분의 경우 삽입정렬이 선택 정렬보다 빠르다.
시간 복잡도의 분할 상환 분석
문제의 조건에 따라 더 정확한 시간 복잡도를 계산하는 것도 가능한데, 대표적인 것이 분할 상환 분석이다.
N개의 작은 작업들은 순서대로 하는데, 각 작업에 걸리는 시간은 모두 다르지만, 전체 작업에 걸리는 시간이 일정한 경우 이런 방법 가능

4.6 수행 시간 어림짐작하기

주먹구구 법칙

시간 복잡도와 입력 크기만 알고 있더라도 어떤 알고리즘이 시간 안에 동작하는지 대략적으로 짐작하는 것이 가능하다. 시간복잡도는 프로그램의 수행 시간에 가장 큰 영향을 미치는 요소이기 때문

주먹구구 법칙은 주먹구구일 뿐이다.

시간 복잡도이외에도 고려해야 할 사항들
- 시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우
- 반복문의 내부가 복잡한 경우
- 메모리 사용 패턴이 복잡한 경우
- 언어와 컴파일러의 차이
- 구형 컴퓨터를 사용하는 경우
  실제 적용해보기

알고리즘의 시간 복잡도 분석