9일차 리뷰

2019/01/17 - [프로그래밍/알고리즘] - 8일차 리뷰

최근에 명절 + 면접절차 중이라 글을 못썼다;;

그리고 방금도 면접을 보고 왔는데 또 멍청한 소리를 하고 온 것 같다;;

준비를 열심히해도 눈치가 없어서 큰일이네.... 또 다 된 밥상은 뒤엎고 나온거 같다.

기회는 또 있을테니 공부라도 열심히해야지...

문제는 예전에 풀었는데 이제서야 정리한다;;

step9 정렬해보기2

---

2751

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

내 풀이 : https://github.com/gnidoc327/one-day-one-problem/commit/e8df0795b605822deaa66c4aeb4b82f8b7a26646

오랜만에 짜려고 하니 개념이 헷깔렸다.

반씩 쪼개가면서 쪼갠걸 합쳐가며 정렬을 한다는 것이다.

애초에 쪼개졌던 다른 2개의 배열을 합치는 것도 정렬이 필요할텐데 이게 무슨 소리지 라는 생각이 들었다.

분할 정복

일단 머지소팅은 알고리즘 설계 기법 중 분할 정복(Divide and Conquer)에 해당 한다.

모든 알고리즘 문제는 나눠서 하나하나 해결하고 이를 병합하면 해결할 수 있다는 방법이다.

이쯤해서 갑자기 글을 날려먹어서 쳐다보기 싫었지만 다시 쓴다... ㅂㄷㅂㄷ

보통 분할 정복 방식으로 해결한다라고 하면 재귀형태로 많이 문제를 해결한다.

왜냐하면 분할했던 문제를 병합하기 위해서는 재귀형태로 푸는게 편하기 때문이다.

그리고 옛날에 교수님이 말씀하시기로 모든 문제는 분할 정복으로 풀 수는 있다고 했다.

(답은 구할 수 있지만 시간복잡도가 매우 클 수 있다는 소리다)

머지소팅

아무튼 머지소팅이 되는 방식을 그림으로 표현하면 다음과 같다.

맨 위에서 순서가 없는 배열을 2개로 쪼갠 후에 더이상 쪼갤 것이 없는 구간이 중간이고

이 중간을 기점으로 합쳐가며 정렬을 한다는 것이다.

내가 이해가 안된 부분은 중간 이후 합치면서 정렬을 한다는 것이다.

(정렬이 안됐는데 어떻게 합쳤을때 정렬이 되지???)

가능한 이유는 여기에 있다.

가장 마지막까지 쪼개진 2개의 정수는 합칠때 정렬이 가능하다.

왜냐하면 2개의 정수를 정렬하는 법은 대소비교만 하면 되기 때문이다.

예를 들어 [38], [27]은 대소비교를 하면 [27, 38]로 정렬된다.)

그럼 2개의 정수를 가진 2개의 배열을 합칠때는??

2개의 배열은 이미 각각 정렬이 된 상태이기 때문에 별도의 정렬 알고리즘은 필요없다.

2개의 배열 중 각각 작은 숫자부터 대소를 비교해서 4개의 배열에 집어 넣으면 되기 때문이다.

예를 들어 [27, 38], [3, 43]은 왼쪽이 제일 작으므로 작은 정수부터 비교한다.

[27, 38], [3, 43] - 시작

[27, 38], [43] -> [3] - 3과 27 중 3이 작음

[38], [43] -> [3, 27] - 27과 43 중 27이 작음

[], [43] -> [3, 27, 38] - 38과 43 중 38이 작음

[3, 27, 38, 43] - 완성

이렇게 머지 소팅은 가장 작게 배열을 쪼개므로써 정렬된 배열끼리의 정렬을 하기 때문에

정렬된 배열끼리 정렬하는 시간 복잡도는 O(n)의 시간이 걸리고

합치는 과정에 대한 시간 복잡도는 트리구조인 O(logn)의 속도가 걸리기 때문에

 O(nlogn)의 시간 복잡도를 가진다.

트리구조는 왜 O(logn)인가?

뭔가 트리구조라고 하면서 합치는 과정에 대한 시간 복잡도를 건너 뛰었는데

보통 트리 구조를 사용한 알고리즘은 O(logn)의 시간 복잡도를 가진다.

왜냐하면 

N개의 데이터가 있다고 보면 이걸 머지소팅과 같이 K번 만큼 반으로 쪼개서 1개가 남을때까지 반복해보자

(당연히 위의 그림과 동일할테니 이진 트리의 형태가 될거다)

1차 시행 후 , 2차 , 3차 .....

그럼 K차 시행 후에는  개가 남을 것이다.

그렇다면 탐색이 끝나는 시점은 남은 자료가 1개가 남게 될텐데 결과적으론

  이런 공식을 남기게 된다.

그래서 이게 뭐?라고 생각할텐데

여기서의 K가 바로 우리가 원하는 시간복잡도이다.

그럼 K에 대해 식을 풀면 결국

이런 공식이 나온다.

만약에 자료를 나눌때 2개가 아닌 3개, 4개로 나눈다면?? 더 빨라지지 않을까?

하지만 우리는 빅오를 사용한다. 즉, 로그의 밑수가 2든 3이든 큰 차이가 없다.

그렇기 때문에 트리 구조의 알고리즘에서 시간 복잡도는 

이 되는 것이다.

내 방식

그래서 나는 시간복잡도를 구할때 이렇게 간단하게 생각해서 구한다.

• 트리 구조면 O(logn) 
• for문을 k번 중첩하면 O(n^k)

아직까진 다른 방식으로 풀어본 문제가 없어서 더 생각해보진 않았지만

이정도만 해도 충분했었다.

아무튼 힙소팅도 이와 비슷하게 트리 구조로 구현하는거지만 

원리를 알고 있고 다른 블로그에서도 기술된 내용들이니 굳이 따로 풀고 기술하진 않았다.

확실히 옛날에 했었지만 다시 풀려고 하니 막히는 부분도 있었고

알고리즘 기법에 대해서 복습되는거 같아 좋은거 같다.

일단 이직될때까지 감을 잃지 않기 위해서 계속 풀어야겠다.