알고리즘1 알고리즘 강의 2주차 - 분할 정복, 합병 정렬 분할 정복 - 주어진 문제를 더이상 나눌 수 없을 때까지 나누고, 나누어진 문제를 각각 풀어 답을 얻는 알고리즘 규칙은 정해져있지 않고 개발자의 창의력, 독창성, 경험에 달려있다 분할 정복 알고리즘을 설계하는 요령 분할 - 2개이상의 하위문제로 나눈다 정복 - 하위문제가 여전히 분할 가능하다면 하위집합에 대해 분할을 다시 수행, 아니라면 하위 문제를 푼다. 결합 - 위 두 과정에서 정복된 답을 취합한다. 부분문제 - 분할된 입력에 대한 문제 부분해 - 부분 문제의 해 문제해 - 부분해를 취합 합병 정렬 Merge Sort n개의 숫자들을 n/2개씩 2개의 부분 문제로 분할 각각의 부분문제를 재귀적으로 합병 정렬한 후, 2개의 정렬된 부분을 합병하여 정렬(정복) 합병 정렬의 시간 복잡도 (층수)xO(n) .. 2021. 10. 8. 이전 1 다음 반응형