알고리즘 수업 - 병합 정렬 1 파이썬 풀이

요즘 취업반 재미반 목적으로 포트폴리오를 만들고있다

내 공부결과를 피피티로써 만들다보니 비슷한 기록목적으로 작성하는 블로그에 흥미가 많이 떨어졌다

 

그래도 주가예측 관련 포스팅은 마지막에 하나 올리는게 좋을것같긴하다

 

요즘 백준 단계별풀이에 새로운 문제가 많이 등장했다

 

내가 가장 싫어하는 문제유형은 바로 문제 설명에 파이썬이 아닌 다른코드가 올라와있는 경우이다

솔직히 잘 이해가 안된다 왜 문제풀이에 코드를 집어넣는것일까 다른 언어 이용자들은 알수가없다

왜 프로그램언어라고 불리겠는가 이것은 마치 일본어로 설명되어있는 수학문제를 푸는것과 같다

 

이 문제도 그런유형인데 문제가 이해조차 안되었다

 

오늘 오랜만에 다시보는데 문제이해가 드디어 좀 된것같아서 풀어보려고한다

 

병합정렬에 대한 설명은 이분 포스팅을 보고 참고했다

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

코드에 대한 이해없이 예제만을 보고 이해해보자

배열의 크기가 홀수일경우 누가더 많이 가져가나?

예제를 보면 왼쪽이 더 많이 가져가는것같다그것으로 예제를 설명 할수있기때문이다

먼저 분할하는 단계이다

45132 => (451) (32)

 

따라서 병합 단계에서는 다시 역순으로

451끼리 정렬을하고 그후 32를 정렬하게 된다

 

저장이라고 하는것의 기준은 무엇일까?

배열의 크기만큼의 리스트가 있고 배열의 요소들이 수정될때마다 그것을 저장이라고 표현하는것같다

 

분할정복구현해보기

문제를 떠나서 나는 정렬방법중 하나인 분할정복을 코드로 구현해보고싶었다

병합정렬과 분할정복은 같은말같은데 나는 분할정복이 더좋으니 앞으로 이단어를 사용하겠다

 

구현 방법에 대해서는 생각을 좀해봤는데 분할이라는 함수와 합병이라는 함수를 만들어서 

구현하는 방식을 생각해보았다

 

분할은 재귀함수이며 이런식으로 이루어질것이다

 

return 합병(분할(451), 분할(32))

def 분할(array)
	...
	return 합병(분할(array_a), 분할(array_b))

분할은 배열의 길이가 1이되면 더이상 재귀하지않는다

자기자신을 return  한다

 

먼저 합병 코드를 구현해보았다

def 합병(array1, array2):
    array=[]
    while True:
        if len(array1)==0 or len(array2)==0:
            array.extend(array1)
            array.extend(array2)
            break
        
        if array1[0]>=array2[0]:
            array.append(array2.pop(0))
        else:
            array.append(array1.pop(0))
    return array

합병([1,4,5],[2,3])

잘 작동한다  비교를하다가 한쪽대상이 없어지면 그냥 모두다 넣는걸로 했다 그게 시간절약이 될것같아서

 

하지만

문제에서 말하는 저장이라는 개념은 저 합병 array에 append 될때마다 이니까 

extend보다 그냥 append를 쓰는게 좋겠다

일단 이부분은 조금있다보고 이제 분할을 구현해보자

# 병합정렬

def merge(array1, array2):
    array=[]
    while True:
        if len(array1)==0 or len(array2)==0:
            array.extend(array1)
            array.extend(array2)
            break
        
        if array1[0]>=array2[0]:
            array.append(array2.pop(0))
        else:
            array.append(array1.pop(0))
    return array

def merge_sort(array):
    length=len(array)
    if length==1:
        return array
    
    half=length//2
    
    if length%2==0:
        array1=array[:half]
        array2=array[half:]
    
    else:
        array1=array[:half+1]
        array2=array[half+1:]
    return merge(merge_sort(array1), merge_sort(array2))


merge_sort([5,4,3,2,1])

잘 작동하는 모습이다 오우!!

이름도 그냥 영어로 바꿨다

이제 그놈의 '저장'개념을 구현해보자

# 병합정렬
import sys
ans=[]

def merge(array1, array2):
    global ans
    array=[]
    while True:
        if len(array1)==0:
            for i in array2:
                array.append(i)
                ans.append(i)
                if len(ans)==number:
                    print(ans[-1])
                    sys.exit()
            break
        
        elif len(array2)==0:
            for i in array1:
                array.append(i)
                ans.append(i)
                if len(ans)==number:
                    print(ans[-1])
                    sys.exit()                
            break

        
        
        if array1[0]>=array2[0]:
            ans.append(array2[0])
            if len(ans)==number:
                print(ans[-1])
                sys.exit()            
            array.append(array2.pop(0))
        else:
            ans.append(array1[0])
            if len(ans)==number:
                print(ans[-1])
                sys.exit()                
            array.append(array1.pop(0))
    return array

def merge_sort(array):
    length=len(array)
    if length==1:
        return array
    
    half=length//2
    
    if length%2==0:
        array1=array[:half]
        array2=array[half:]
    
    else:
        array1=array[:half+1]
        array2=array[half+1:]
    return merge(merge_sort(array1), merge_sort(array2))

# 입력받기
size, number=map(int, input().split())
array=list(map(int, input().split()))
merge_sort(array)
print(-1)

간결하고 이뻣던 코드가 번잡해졌다

쓸대없는 시간낭비를 막기위해

저장횟수를 채우면 저장된수?를 출력하고 프로그램이 종료되는식으로 구현해보았다

 

하지만 시간초과가 떳다ㅠ

이것만풀고 롤하고 싶은데

 

시간초과 해결

일일이 append하는 방식도 extend로 바꾸었다 훨씬 코드가 깔끔해졌다 속도에도 개선이 있을것이라 생각하였지만 똑같은 지점에서 시간초과가 발생했기때문에 왜인지는 모르겠으나 시간차이는 별로 안나는듯하다

 

후에 분할정복 정렬법을 이용해 정렬하는 부분을 파이썬에서 제공하는 sort()를 이용하는 방식으로 바꿔주웠다

# 병합정렬
import sys
ans=[]

def merge(array1, array2):
    global ans
    array=array1+array2
    array.sort()
    ans.extend(array)
    if len(ans)>=number:
        print(ans[number-1])
        sys.exit()
    return array

def merge_sort(array):
    length=len(array)
    if length==1:
        return array
    
    half=length//2
    
    if length%2==0:
        array1=array[:half]
        array2=array[half:]
    
    else:
        array1=array[:half+1]
        array2=array[half+1:]
    return merge(merge_sort(array1), merge_sort(array2))

# 입력받기
size, number=map(int, input().split())
array=list(map(int, input().split()))
merge_sort(array)
print(-1)

지금까지 봐왔던 대부분의 경우에서 직접구현하는것보다 파이썬에서 제공하는 함수를 이용하는게 훨씬 빨랐기때문이다

이번에는 정답처리되었다 솔직히 실버4치고는 어려운문제라고 생각한다