코드잇 Divide and Conquer 알고리즘 문제

---

1. 1부터 n까지의 합

구상 12분

start와 end를 사용한 반값을 활용

구현 12분

def consecutive_sum(start, end):
    # 코드를 작성하세요
    # base cass
    if start == end:
        return start

    # recursive case
    else:
        half = (start + end) // 2
        return consecutive_sum(start, half) + consecutive_sum(half +1, end)
    
# 테스트
print(consecutive_sum(1, 10))
print(consecutive_sum(1, 100))
print(consecutive_sum(1, 253))
print(consecutive_sum(1, 388))

---

2. merge 함수 작성

구상 5분

1. 각 리스트의 길이가 1이 될 때까지 divide
2. 리스트의 쌍의 길이가 1이하인 것부터 시작해서 combine을 하는데 combine하는 규칙은 두 리스트의 0번 인덱스에 위치한 값을 비교ㅕ해서 작은 것을 새리스트에 append

구현 44분

def merge(list1, list2):
    # 코드를 작성하세요.
    
    
    # # divide
    # if 1 < len(list1):
    #     half = len(list1) // 2
    #     merge(list1[:half],list2[:half])
    #     merge(list1[half:],list2[half:])
    
    # # conquer
    # elif len(list1) < 2 and len(list2) < 2:

    return sorting(list1, list2)
        
def sorting(list1, list2):
    
    result = []
    for i in range(len(list1)+len(list2)):

        if len(list1) == 0:
            small = list2.pop(0)
            result.append(small)
        elif len(list2) == 0:
            small = list1.pop(0)
            result.append(small)
        elif len(list2) == 0:
            result.append(list1)
            break
        elif list1[0] < list2[0]:
            small = list1.pop(0)
            result.append(small)
        else:
            small = list2.pop(0)
            result.append(small)
    return result
    
    
    
    
# 테스트
print(merge([1],[]))
print(merge([],[1]))
print(merge([2],[1]))
print(merge([1, 2, 3, 4],[5, 6, 7, 8]))
print(merge([5, 6, 7, 8],[1, 2, 3, 4]))
print(merge([4, 7, 8, 9],[1, 3, 6, 10]))

테스트 케이스에 맞춰서 풀기?

• 합병정렬의 list1과 list2가 정렬이 되어 있지 않다고 생각을 하고 푸는 문제인 줄 알고 각 리스트의 길이가 1이 되도록 나눈 다음 원래의 리스트 두 개 길이의 합만큼 길이가 되는 리스트가 되도록 combine을 어떻게 재귀적으로 해주어야 될지 고민하다가 방법이 떠오르지 않아 답안을 보니 합병정렬의 list1과 list2가 정렬이 되어 있다고 생각을 하고 푸는 문제였다... 알고리즘 문제 풀이시 테스트케이스를 내가 생각한 대로 고려해서 긁어 부스럼을 만들 필요는 없는 듯하다. 일단 융통성 있게 주어진 테스트케이스만 고려해서 알고리즘이 작동하게 푸는 것이 효율적인 학습 방법일듯하다.

---

3. 합병 정렬 구현하기

1차 - 실패

• 구상

  1. divide - 받은 리스트를 반으로 나눈다.
  2. conquer - 정렬이 된 두개 리스트를 구한다.
  3. combine - 정렬이 된 두개의 리스트를 정렬이 된 하나의 리스트로 합친다.

• 구현 - 실패

  • 재귀적으로 어떻게 divide, conquer, combine를 버무릴지 머릿속에서 방법을 못찾았다.

답안 참고

• 구현해보기

# def merge(list1, list2):
#     # 이전 과제에서 작성한 코드를 붙여 넣으세요!
#     result = []
#     for i in range(len(list1)+len(list2)):

#         if len(list1) == 0:
#             small = list2.pop(0)
#             result.append(small)
#         elif len(list2) == 0:
#             small = list1.pop(0)
#             result.append(small)
#         elif len(list2) == 0:
#             result.append(list1)
#             break
#         elif list1[0] < list2[0]:
#             small = list1.pop(0)
#             result.append(small)
#         else:
#             small = list2.pop(0)
#             result.append(small)
#     return result
# 합병 정렬
def merge_sort(my_list):
    # 코드를 입력하세요.
    if len(my_list) < 2:
        return my_list
    
    left = my_list[:len(my_list)//2]
    right = my_list[len(my_list)//2:]
    return merge(merge_sort(left), merge_sort(right))📌
    
    

# # 테스트
# print(merge_sort([1, 3, 5, 7, 9, 11, 13, 11]))
# print(merge_sort([28, 13, 9, 30, 1, 48, 5, 7, 15]))
# print(merge_sort([2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]))

📌 divide, conquer, combine을 재귀적으로 버무리는 방법

return merge(merge_sort(left), merge_sort(right))📌

• 미리 구현해둔 merge 함수를 merge_sort 함수 내부에 구현함으로써 merge_sort와 merge 함수들을 재귀적으로 합쳐서 동시에 호출 하면 되는 거였다!
• recursive case의 return 부분이 combine 부분과 관련이 높아 보이니 재귀 함수 구현시 참고 할 것