분할 정복(Divide and Conquer)

분할 정복 말 그대로 분할해서 정복하는 알고리즘이다!
그대로 해결할 수 없는 문제를 작은 문제들로 분할하여 문제를 해결하는 방법이다
분할된 작은 문제들은 원래 문제와 같은 형태를 가지고, 작은 문제는 큰 문제의 일부가 된다
작은 문제들을 재귀적으로 해결하고, 작은 문제들을 결합하여 큰 문제를 해결하는 방식이다

DP와의 차이

분할 정복에 관한 설명을 보고 나서 DP와 유사하다는 생각이 들었다
그럼 두 알고리즘은 뭐가 다를까?

DP 블로깅

공통점

• 문제를 작게 쪼개서 가장 작은 문제로 나눔

차이점

• DP : 부분 문제는 중복 → 상위 문제에서 재활용, memoization 기법 사용
• 분할 정복 : 부분 문제는 중복이 안됨, memoization 기법 사용 안함

가장 큰 차이는 memoization 방식을 사용하나 안하나의 차이라고 한다
분할 정복은 부분 문제가 중복되지 않기 때문에 따로 저장할 필요가 없다고 이해했다

과정

1. 분할(Divide) : 큰 문제를 작은 문제들로 나눔
2. 정복(Conquer) : 작은 문제들을 재귀적으로 해결 → 작은 문제를 더 이상 나눌 수 없으면 탈출하는 조건을 정하고 해결
3. 병합(Combine) : 정복한 문제들을 합쳐서 원래 문제의 답을 구함

장점

• 큰 문제를 작은 문제로 분할하고 해결해서 전체 문제를 해결하는 데에 걸리는 시간을 줄일 수 있음
• 작은 문제를 병렬적으로 문제를 해결할 수 있음

단점

• 재귀적으로 호출돼서 추가적인 메모리를 필요로 할 수 있음
• 최악의 경우 빠른 해결책을 적용하지 못할 수 있음
• 재귀 함수 호출로 오버헤드가 발생할 수 있음

어느정도 알아봤으니 이제 문제를 풀어보자!

백준 11582번 : 치킨 TOP N

문제 링크

문제

인하대 주변 치킨칩의 맛의 정도를 측정해 수치화하는 동아리 C.T.P(Chicken Tastes Perfect)의 회장 민호는 치킨집의 맛의 수치를 감소하지 않는 순으로 정렬을 하고 싶었다. 하지만 치킨집이 너무 많아 혼자 정렬을 하기에는 많은 시간이 걸려 C.T.P 회원들을 활용하기로 했다. 치킨집이 N개 있다고 가정을 하자. N개의 치킨의 수치를 무작위로 놓은 뒤 N/2명의 C.T.P 회원이 차례대로 2개의 치킨집을 선택해 정렬을 한다. 그 뒤 N/4명이 차례대로 바로 전 단계의 사람이 정렬한 두 개의 그룹을 차례대로 선택 하여 치킨집을 정렬을 한다. 계속해서 N/8명, N/16명이 정렬을 진행하다가 마지막 사람이 두 개의 정렬된 그룹을 합병하여 작업을 완료한다.
.
작업을 진행하던 중 문득 민호는 작업의 중간단계가 궁금해졌다. 현재 단계에서 k명의 회원이 정렬을 진행할 때 정렬을 마친 뒤 결과를 출력해라.

입력

첫 번째 줄에 치킨집의 개수 N(4 ≤ N ≤ 220)이 주어진다. N은 항상 2의 거듭제곱 꼴이다.
두 번째 줄에는 N개의 치킨집의 맛의 수치들이 빈칸을 구분으로 주어지며 이 값은 10억보다 작거나 같은 자연수 또는 0이다.
세 번째 줄에는 현재 정렬을 진행중인 회원들의 수 k(1 ≤ k < N)가 주어진다. k 또한 2의 거듭제곱 꼴이다.

출력

현재 단계에서 k명이 정렬을 진행한다고 할 때, 현재 단계가 완료한 상태를 출력하라.

문제가 길다!
그래도 어떻게 풀지 이해를 하면 그렇게 어렵지는 않은 문제였다

결국 출력해야 하는 부분은 k명이 정렬을 진행할 때의 상태를 구하면 된다

2개의 치킨집끼리 정렬을 한 후 다음 단계에서 4개의 치킨집끼리 정렬, ... 해서 총 N개의 치킨집을 정렬하는 방식이다

이 문제는 그렇게 크지 않아서 바로 정렬을 해줘도 된다

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        String inputScore = br.readLine();
        List<Integer> scores = Arrays.stream(inputScore.split(" "))
            .map(Integer::parseInt)
            .collect(Collectors.toList());

        int k = Integer.parseInt(br.readLine());
        int size = n / k;

        int start = 0;

        for (int i = 0; i < k; i++) {
            Collections.sort(scores.subList(start, start + size));

            start += size;
        }

        for(int i : scores){
            System.out.print(i + " ");
        }
    }

근데 지금 설명하고 보니까 이건 분할정복 문제인데 내가 그 방식으로 풀지 않은것 같다.. 다시 풀어봐야겠다