군대에서_코딩하기_알고리즘_26

또 다시 정말 오랜만의 업로드이다..
이러다가 전역때까지 인프런 수업 다 못듣는건 아닌지... 생각보다 연말이라 이벤트가 매우 많았다..
심지어 일주일전에는 같은 대대내 간부님 한명이 코로나 확진이 되는 바람에 일주일동안 1인 격리를 하고 왔다.. 그 이후에는 잦은 당직근무와.. 야간 근무가 겹쳐서 한동안 사지방 연등을 하지 못했다.. 이렇게 올해가 다 지나가는구나...

한창 코딩 학구열(?)에 불이 붙던 찰나에 갑자기 큰 공백기가 있어서 복기하는데 시간이 조금 걸렸다..특히 DFS의 '꽃'이라고 할 수 있는 병합정렬을 앞두고 공백기가 있었어서.. 하지만 결국 해냈다..

방금 말한대로 이번 문제는 DFS를 이용한 병합정렬이다.

우선 병합정렬이란?

-> (옛날에 알고리즘 수업때 정리해 놓은 것을 참고하겠다..ㅎㅎ 나 생각보다 열심히 정리해놨었네)

병합 정렬(Mergesort)

• 알고리즘의 기본 아이디어
  -> 정렬할 리스트를 앞 뒤로 쪼개어 나눈뒤, 따로따로 정렬하여 합친다. 약간 재귀식으로다가..? 계속 쪼개서 정렬하고 합치고, 정렬하고 합치고를 반복

def merge(A, B):
   if (len(A) == 0):
       return B
   if (len(B) == 0):
       return A
   if (A[0] < B[0]):
       return [A[0]] + merge(A[1:], B)
       #A[1:] 이거 때문에 A가 하나씩 계속 감소하는 것을 알 수 있음
   else:
       return [B[0]] + merge(A, B[1:])

병합의 정확성

• 병합 과정이 정확하게 두 리스트를 정렬하는지에 대한 정확성 증명
• 기본 경우
  -> A,B 둘 중 하나가 비어 있는 경우
  -> 나머지 하나는 이미 정렬되어 있으므로 병합 결과는 그 자신.
• 알고리즘의 진행
  -> 전체 리스트의 앞의 반, 뒤의 반을 병합 정렬을 통해서 정렬

def mergesort(L):
    if (len(L) == 1):
       return L
    return merge(mergesort(L[:int(len(L)/2)]), mergesort(L[int(len(L)/2):]))

병합 정렬의 시간 복잡도

• 실제 정렬은
  -> 맨 마지막에는 원소 하나를 가지는 리스트 (이미 정렬됨)
  -> 정렬된 리스트를 연속으로 병합, 최종 단계에서 정렬 완료
• 점화식
  -> T(n) = 2T(n/2) + n, T(n) = Θ(n log n)
  -> n/2개의 리스트 2개를 정렬하고, 이를 합치는데 n번 비교
• 특징
  -> 입력의 형태에 상관없이 언제나 같은 시간 복잡도 보장
  -> 언제나 문제의 크기가 1/2로 줄어듬. (참고: 퀵 정렬)
  -> 실제로는 원소들이 더 자주 움직이므로 시간이 더 많이 걸림
  -> 퀵 정렬의 경우, 일단 순서가 정해진 원소는 움직이지 않는다.

이때까지만해도 병합정렬을 구현은 커녕, 제대로 100프로 이해하지도 못했다.. 코드 또한 교수님이 설명해주신 것을 거의 복붙? 해서 참고한것!

이처럼 병합정렬은 재귀식으로 반으로 쪼개고 쪼개서 재귀식으로 정렬하는 것을 말한다.

우선 내가 c++로 작성한 코드는 다음과 같다.

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int nums[101], result[101], p1, p2, p3; 
//처음에 숫자를 받아줄 배열 nums와 최종적으로 출력해줄 배열 result를 전역 변수로 선언하였다.
//why? -> 함수에서 간편하게 사용하려고

void merge_sort(int lt, int rt){
    //lt는 처음에 1 고정, 그리고 rt는 배열의 크기를 뜻한다.
    if(lt<rt){
        int mid = (lt+rt)/2; //계속해서 반으로 쪼개줘야하기 때문에 mid가 필요
        merge_sort(lt, mid); //왼쪽 자식에는 lt부터 mid까지
        merge_sort(mid+1, rt); //오른쪽 자식에는 mid+1부터 rt까지
        p1 = lt;
        p2 = mid+1; //이게 조금 헷갈렸는데.. 왜 mid+1까? 에 대해서.. 근데 생각해보면
                    //당연한게 오른쪽 자식은 mid+1에서 rt까지니까 p2는 mid+1이어야 한다.
        p3 = lt;
        //얘네가 참 중요한 친구들인데, 포인터라고 생각하면 편하다.
        //계속해서 배열에 삽입을 해줘야하는데, 그 위치를 바꿔주는 포인터..?
        while(p1<=mid&&p2<=rt){   //p1은 lt를 의미하니까 lt가 mid보다 작고, 
            if(nums[p1]<nums[p2]){//p2는 mi+1을 의미하니까, p2가 rt보다 작을 때를 의미한다
                result[p3++] = nums[p1++];   
            }
            else{
                result[p3++] = nums[p2++];
            }
        }
        //여기 밑의 while문 두개는, 남은 것들을 처리하는 while문
        while(p1<=mid){
            result[p3++] = nums[p1++];
        }
        
        while(p2<=rt){
            result[p3++] = nums[p2++];
        }
        
        for(int i=lt; i<=rt; i++){
            nums[i] = result[i];
        }
    }

}



int main(){
    
    int N, i;
    
    cin>>N;
    //배열의 크기
    
    for(i=1; i<=N; i++){
        cin>>nums[i];
        //랜덤으로 된 배열의 인덱스 받기
    }
    
    merge_sort(1, N);
    
    for(i=1; i<=N; i++){
        cout<<result[i]<<" ";
    }
}

주석은 구체적으로 달아놨다...
보기에는 간단하지만 개인적으로 좀 많이 어려웠다...
조만간 다시 한번 복습할 예정..
그나저나 진짜 병합정렬 이렇게 쉬운 코드로 짜놓은 사람 몇 없을듯..