10989

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.(카운팅 소팅)

어떤 정렬인지 몰라서 나도 다른 블로그 글을 참고했다.

시간복잡도는 O(n) 매우 속도가 뛰어난 정렬방식이다.

하지만 공간복잡도에서 지옥을 경험할 수 있다.

예를 들어서 0과 1억 2개를 정렬한다고 하면 공간복잡도는 1억이다.

메모리 공간으로 따지면 4억 byte를 사용한다는 것이다.

이렇게 최대값에 따라서 공간복잡도가 결정되다보니 string 형 데이터라면 지옥의 공간복잡도를 가질 것이다.

(특히 유니코드처럼 하나의 값이 매우 크다면 더더욱 지옥)

메모리 크기가 무한이거나 디스크IO의 속도가 매우 빨라서 파일로 처리할 수만 있다면 좋을텐데

현실적으로 불가능하니 아마 사용하지 않을 것이라 생각한다.

그리고 이렇게 문제를 여러개로 쪼개서 구하는 방식은 동적계획법(Dynamic programming)에 해당한다.

9일차 리뷰에서 했던 머지 소팅은 2개씩(반씩) 나눠서 가장 작은 단위까지 문제를 쪼개서 계산하고 합쳤지만

동적계획법은 위의 예제의 경우 1 ~ 7까지의 경우를 각각 계산하고 합치는 방식을 택했다.

정확히 보면 작은 문제의 누적합을 통해서 다음 문제를 해결한 것이다.

그래서 동적계획법은 분할정복 방식보다 시간복잡도면에서는 이득이 있지만 공간복잡도가 비효율적으로 사용될때가 있다.

(일부 문제는 동적계획법이 더 느릴 수 있다, 분할정복과 동적계획법 둘 다 답이 아닐 수도 있다는 것!)

동적계획법의 다른 대표적인 알고리즘은 재귀적으로 피보나치(!)을 구하는게 있다.

위키에서 피보나치 코드 예제를 보면

예제 코드대로라면 fib(3) 부터는 기존에 정의/계산된 값을 사용해서 구한다.

fib(3) = fib(1) + fib(2)

fib(4) = fib(2) + fib(3)

...

이렇게 기존에 계산된 값을 재귀적으로 사용한다면 동적계획법이라고 생각하면 된다.

(이렇게 분할정복, 동적프로그래밍 2가지로 풀리는 알고리즘엔 팩토리얼도 있다.)

이제 문제점은 예제방식으로 fib(1000)을 구하기 시작하면 함수 스택이 터지는 문제가 발생한다.

(흔한 스택오버플로우)

이유는 재귀적으로 함수를 호출하다보니 메모리에 함수스택이 쌓이게 되어 정해진 메모리 영역을 초과하는 것인데

프로그램에 할당된 메모리를 늘려 일시적으로 문제를 해결할 수 있지만

꼬리재귀로 함수 스택을 억지로? 사용하지 않는 방식으로 해결할 수 있다.

보통 알고리즘 문제를 해결할때는 꼬리재귀로 스택문제를 해결하지만

어쨌든 이런 재귀방식만 채택하면 정해진 시간 안에 해결할 수 없는 문제가 많다.

(코딩테스트를 보면 대부분 공약수를 제거하거나 하는 다른 해결방식을 겸해야되더라...)

(그래서 길찾기 문제에서는 시간복잡도를 줄이기 위해서 다른 방식을 택하는데 이건 문제를 풀다보면 또 나오겠지...)

결국엔 알고리즘도 답은 없다. 예전에 교수님의 말을 빌리자면 시간복잡도의 정답은 없기 때문에

보통 O(nlogn)면 빠르다라고 한다. 보통 이 정도의 속도를 구하는게 최선이라고 한다.

(최대한 O(n^2)은 피해야된다는 것)

뭔가 많은 내용을 쓰다보니 길어졌는데 어쨌든

알고리즘엔 답이 없다. 어떤 기법을 쓰냐에 따라 분할정복이 빠를 수도 있고 동적계획법이 빠를 수 있다.