2주차 1번(병합정렬)

Hyo Kyun Lee·2021년 5월 31일

알고리즘

스파르타코딩클럽-스파르탄365

목록 보기

9/9

1.문제 링크

https://www.acmicpc.net/problem/2751

2. 풀이 전 계획과 생각

병합정렬의 개념과 알고리즘을 정확히 이해한다.
재귀함수/math 메소드를 통해 로직을 구현해본다.

2-1. 병합정렬의 핵심

분할정복

큰 문제를 쪼개어 작은 문제로 나누고, 작은 문제를 통해 해답을 구한다.

2-2A. Reference Code(로직순서파악)

import sys
import math

def merge(sub_left_list,sub_right_list):
    print('sub_left and sub_right is ', sub_left_list, sub_right_list)
    result = []
    left = 0
    right = 0
    #왼쪽배열과 오른쪽배열을 합치는 과정
    #하다가 한쪽 배열의 result append가 완료되면 탈출
    while left < len(sub_left_list) and right < len(sub_right_list) :
        if sub_left_list[left] < sub_right_list[right]:
            result.append(sub_left_list[left])
            print('result_appendend_by_sub_left ', result)
            left += 1
        else:
            result.append(sub_right_list[right])
            print('result_appended_by_sub_right ', result)
            right += 1
    #병합후에 남아있는 요소들을 병합하는 과정
    #왼쪽배열/오른쪽배열을 비교하면서 넣는 과정
    #이미 배열들은 정렬이 완료된 상태로
    #왼/오른쪽 배열 비교하면서 병합이 다 완료된 이후에
    #남아있는 배열은 이미 정렬이 되어있기때문에 그대로 넣어주면 된다.
    print('sub_left_list[left:] ', sub_left_list[left:])
    print('sub_right_list[right:] ', sub_left_list[right:])
    print('result', result)
    result += sub_left_list[left:]
    print('result_sub_left_list[left:] ', result)
    result += sub_right_list[right:]
    print('result_sub_right_list[right:] ', result)
    return result

def merge_sort(num_list):
    print('num_list is', num_list)
    if len(num_list) <= 1: #즉 재귀를 수행하면서 요소가 1이될때까지 반복
        return num_list

    mid = math.floor(len(num_list)/2)
    print('num_list[:mid]_before_sorted is ', num_list[:mid])
    print('num_list[mid:]_before_sorted is ', num_list[mid:])
    sub_left_list = merge_sort(num_list[:mid])
    print('num_list[:mid] is ', num_list[:mid])
    sub_right_list = merge_sort(num_list[mid:])
    print('num_list[mid:] is', num_list[mid:])
    return merge(sub_left_list, sub_right_list)

n = int(sys.stdin.readline())
array = []
for _ in range(n):
    array.append(int(sys.stdin.readline()))

array = merge_sort(array)

for i in array:
    print(i)

2-2B Reference Code 출력과정

5
5
4
3
2
1
num_list is [5, 4, 3, 2, 1]
num_list[:mid]_before_sorted is  [5, 4]
num_list[mid:]_before_sorted is  [3, 2, 1]
num_list is [5, 4]
num_list[:mid]_before_sorted is  [5]
num_list[mid:]_before_sorted is  [4]
num_list is [5]
num_list[:mid] is  [5]
num_list is [4]
num_list[mid:] is [4]
sub_left and sub_right is  [5] [4]
result_appended_by_sub_right  [4]
sub_left_list[left:]  [5]
sub_right_list[right:]  []
result [4]
result_sub_left_list[left:]  [4, 5]
result_sub_right_list[right:]  [4, 5]
num_list[:mid] is  [5, 4]
num_list is [3, 2, 1]
num_list[:mid]_before_sorted is  [3]
num_list[mid:]_before_sorted is  [2, 1]
num_list is [3]
num_list[:mid] is  [3]
num_list is [2, 1]
num_list[:mid]_before_sorted is  [2]
num_list[mid:]_before_sorted is  [1]
num_list is [2]
num_list[:mid] is  [2]
num_list is [1]
num_list[mid:] is [1]
sub_left and sub_right is  [2] [1]
result_appended_by_sub_right  [1]
sub_left_list[left:]  [2]
sub_right_list[right:]  []
result [1]
result_sub_left_list[left:]  [1, 2]
result_sub_right_list[right:]  [1, 2]
num_list[mid:] is [2, 1]
sub_left and sub_right is  [3] [1, 2]
result_appended_by_sub_right  [1]
result_appended_by_sub_right  [1, 2]
sub_left_list[left:]  [3]
sub_right_list[right:]  []
result [1, 2]
result_sub_left_list[left:]  [1, 2, 3]
result_sub_right_list[right:]  [1, 2, 3]
num_list[mid:] is [3, 2, 1]
sub_left and sub_right is  [4, 5] [1, 2, 3]
result_appended_by_sub_right  [1]
result_appended_by_sub_right  [1, 2]
result_appended_by_sub_right  [1, 2, 3]
sub_left_list[left:]  [4, 5]
sub_right_list[right:]  []
result [1, 2, 3]
result_sub_left_list[left:]  [1, 2, 3, 4, 5]
result_sub_right_list[right:]  [1, 2, 3, 4, 5]
1
2
3
4
5

Process finished with exit code 0

2-3. 풀이

import sys
import math

T = int(sys.stdin.readline())
array_for_test = []
for i in range(T):
    array_for_test.append(int(sys.stdin.readline()))

def merge_sort(left_side, right_side):

    left = 0
    right = 0
    result = []

    while left < len(left_side) and right < len(right_side):
        if left_side[left] < right_side[right]:
            result.append(left_side[left])
            left = left + 1
        else:
            result.append(right_side[right])
            right = right + 1

    #left_side와 right_side 중 하나는 반드시 모두 정렬이 완료
    #두 배열중 빈상태가 아니더라도 이미 정렬이 된 상태로, 그대로 이어붙여주면 된다.
    #result = result + left_side[left:]방식도 되지만
    #메소드를 이용하여 붙이도록한다.
    result.extend(left_side[left:])
    result.extend(right_side[right:])

    return result

def dividing(array_for_test):
    #별도 else문 작성없이 if문으로 기본조건을 기재
    if len(array_for_test) == 0 or len(array_for_test) == 1:
        return array_for_test

    mid = len(array_for_test) // 2
    #위 조건으로부터 array_for_test는 요소가 1이될때까지 반복한다.
    #left_side에는 왼쪽요소, right_side에는 오른쪽요소가 저장
    left_side = dividing(array_for_test[:mid])
    right_side = dividing(array_for_test[mid:])

    return merge_sort(left_side, right_side)

for i in dividing(array_for_test):
    print(i)

4. 풀이의 핵심

분할정복을 하는 로직의 핵심은 재귀함수이다.
▶ 요소가 1개씩(left_side/right_side) 남을때까지 반복
▶ 요소가 1개씩 남는다면 dividing의 최종 return이 된다!
▶ 그 return된 left_side/right_side가 저장되어 merge_sort을 호출!
요소 1개부터 시작하여 merge_sort를 시작한다.
▶ merge_sort 로직이후의 result는 이미 정렬이 완료된 배열이다.
▶ left_side 및 right_side 두 배열중 하나는 반드시 정렬이 완료된다.
▶ 정렬을 하면서 sort되므로, 잔여배열역시 정렬이 완료된 상태이다.
merge_sort후, 기존배열의 나머지(오른쪽) 부분에 대해 분할정복 시작.
▶ dividing > merge_sort > 잔여배열의 dividing...
▶ 배열의 모든 부분에 대해 로직이 완료될 때까지 반복
알고리즘을 구현하는데 너무 시간이 오래걸린다
다른 방향으로 생각하는 것도 중요하지만, 시간을 절약하는 것도 매우 중요하다.
10분내외로 생각하고 알고리즘 구현하는 것까지 가능하도록 꾸준히 연습해보자.