네, 반갑습니다. 오늘 이 영상을 끝까지 보신 후엔 '디바이드 앤 컨커'의 개념을 이해하게 되고요.

그리고 '머지 솔트'에서 '디바이드 앤 컨커'가 어떻게 적용이 되는지 알게 됩니다.

자, 그럼 오늘도 고고씽! 먼저 '디바이드 앤 컨커'가 무엇인지 소개하도록 할게요.

'디바이드 앤 컨커'란 문제를 해결하는 전략 중의 하나입니다.

그러니까 우리가 프로그래밍을 하다 보면 여러 가지 해결해야 될 문제들이 있는데요.

이런 문제들을 해결하기 위해서 다양한 전략들이 존재할 수 있어요.

이 '디바이드 앤 컨커'는 그런 전략들 중에 하나입니다. 그러면 얘는 어떤 식으로 문제를 해결하는 전략이냐 하면 이 '디바이드 앤 컨커'는 예를 들어서 어떤 프로그램이 있습니다.

어떤 문제가 있는데 이 문제를 그 문제와 유사한 형태를 가지는 더 작은 크기의 서브 프라블럼들로 나눕니다.

그렇게 나눈 뒤에 각각의 서브 프라블럼들을 재귀적으로 동일한 방식으로 해결한 뒤에 그 결과를 활용을 해서 원래의 문제를 해결하는 방식을 디바이드 앤 컨커라고 합니다.

그래서 이해하기 쉽게 좀 더 그림으로 설명을 해 보면 여기 지금 이렇게 시각화를 했습니다.

이런 형태의 문제가 있다고 했을 때 이런 문제들을 유사한 형태지만 더 작은 크기의 서브 프로블럼으로 나누어요.

그래서 이런 식으로 더 잘게 작은 크기의 서브 프로블럼으로 문제가 쪼개지는 거죠.

그렇게 서브 프라블럼으로 문제를 나눈 뒤에 이들 서브 프로블럼 각각을 다시 또 재귀적으로 같은 방식으로 해결하는 겁니다.

그러니까 이게 이 서브 프로블럼이 4개가 생긴 거잖아요.

그러면 이 4개에 대해서 다시 또 재귀적으로 같은 방식으로 접근을 하는 거예요.

그래서 예를 들어서 이 서브 프로블럼의 경우에 얘를 또다시 쪼갤 수 있으면 쪼개 보는 거죠.

얘도 마찬가지로 똑같이 더 작은 서브 프라블럼으로 쪼갤 수 있으면 쪼개 보는 거고 얘도 그리고 얘도 쪼갤 수 있으면 쪼개 보는 겁니다.

그래서 지금 이 각각의 서브 프로그램을 사실 더 작은 크기의 서브 프로그램으로 쪼개 보면 이제 이런 모습이 되는 거죠.

그러면 또다시 얘네들 각각에 대해서 다시 또 재귀적으로 같은 방식으로 쪼갤 수 있으면 쪼개 보는 건데.

그런데 예를 들어서 이제 이 상황에서 더 이상 쪼갤 수 없다고 해 볼게요.

이런 상황에서 더 이상 쪼갤 수 없다면 이제 이때는 다이렉트로 이 문제를 해결하는 겁니다.

그래서 다이렉트로 문제를 해결해서 나오는 솔루션이 있을 거예요.

그러면 이 각각을 해결할 솔루션들이 이제 생겼을 거고 그러면 이제 솔루션들을 합쳐서 이제 원래의 프로그램에 대한 솔루션들을 만드는 거예요.

어떤 말인지 이해가 되시죠? 이 각각의 서브 프로그램들의 솔루션들을 활용을 해서 원래의 프로그램의 솔루션을 얻고 하는 겁니다.

이런 방식으로 원래 프로그램의 솔루션들을 구해 보면 이제 이 프로그램 들에 대한 솔루션들이 나온 거죠.

그럼 이제 이 프로그램의 솔루션들을 바탕으로 다시 또 원래의 프로그램에 대한 솔루션을 만드는 겁니다.

그러면 최종적으로 맨 처음 프라블럼의 솔루션이 나오는 거죠.

이런 방식을 디바이드 앤 컨커라고 합니다.

그래서 정리를 하면 디바이드 앤 컨커는 디바이드, 컨커, 컴바인이라는 이 3단계로 구성이 되는데요.

먼저 디바이드 같은 경우에는 원래의 프로그램을 더 작은 크기의 서브 프라블럼들로 나누어 줍니다.

그렇게 나누어 준 뒤에 각 서브 프라블럼들을 컴페어해야 되는데요.

이때 컨커는 어떤 의미냐면 이 서브 프로그램들을 동일하게 재귀적인 방식으로 해결하는 겁니다.

그러니까 이 서브 프로그램 각각에 대해서 이 디바이드 컨커를 다시 또 적용한다는 의미예요.

그런데 만약에 이 서브 프로그램의 사이즈가 너무 작아서 더 이상 나눌 수가 없다면, 더 이상 쪼갤 수가 없다면 그럼 이 때는 다이렉트로 직접 해결해야 됩니다.

어쨌든 이런 식으로 해결하고 나니에 그러면 이제 각 서브 프로그램들에 대한 솔루션들이 생길 거잖아요?

그럼 이제 이 마지막 단계는 바로 컴바인입니다.

그래서 이 서브 프로그램들의 솔루션들을 합쳐서 원래의 오리지널 프로그램의 솔루션을 만드는 것.

어렵지 않죠? 그러면 이 디바이드 앤 컨커는 어디서 활용이 되느냐? 우리가 공부하면서 흔히 쉽게 접하는 사례는 머지 소트나 퀵 소트, 혹은 우리가 시간 복잡도 영상에서 배웠던 바이너리 서치 이런 것들이 디바이드 앤 컨커를 활용한 그런 사례입니다.

그러면 오늘 우리가 한번 배워 볼 거는 머지 소트인데요, 이 머지 소트가 어떻게 이 디바이드 앤 컨커를 활용했는지 이걸 이제 같이 살펴보도록 하겠습니다.

머지 소트라는 것은 그 이름에서도 알 수 있듯이 정렬 알고리즘이에요.

여러 개의 데이터들이 이렇게 배열에 혹은 리스트에 저장이 되어 있을 때 얘네들을 어떻게 정렬시킬 수 있을까?

이게 이제 정렬 알고리즘이고, 머지 소트는 이 정렬 알고리즘 중에 하나인 겁니다.

그러면 이 Merge Sort는 Divide & Conquer를 활용해서 동작한다고 했기 때문에 이렇게 인풋이 주어졌을 때 인풋을 서브 프라블럼으로 나누어서 재귀적으로 해결할 거예요.

Divide & Conquer를 활용하는 거니까요.

그럼 얘는 어떻게 하냐? 사이즈를 이렇게 반으로 나눕니다.

그러면 이제 두 개의 서브 프로그램이 생긴 거잖아요. 이 두 개의 서브 프로그램 각각에 대해서 Merge Sort를 수행을 하는 겁니다.

그러면 현재는 얘들이 이렇게 정렬이 되어 있지 않은 상태인데 이 각각에 대해서 Merge Sort를 수행한 이후에는 얘네들이 이제 정렬이 되어 있을 겁니다.

그래서 이렇게 Merge Sort를 수행한 후에는 얘네들 각각은 순서대로 오름차순으로 정렬이 되어 있다라는 것을 볼 수 있고요.

그러면 이렇게 서브 프라블럼 에 대한 솔루션들이 이렇게 생긴 거잖아요.

그러면 이 솔루션즈를 바탕으로 뭘 해야 되냐면 원래 오리지널 프라블럼의 솔루션을 구하기 위해서 서브 프라블럼의 솔루션들을 활용을 합니다.

그래서 이 솔루션들을 바탕으로 오리지널 프라블럼을 해결하는 거죠.

즉, 오리지널 프라블럼의 솔루션을 구하는 거죠.

그러면 어떻게 이 솔루션을 구할 수 있냐? 지금 이 솔루션과 이 솔루션 각각은 이미 정렬이 이렇게 되어있는 상태이기 때문에 그러면 순서대로 하나씩 확인을 하면서 차곡차곡 차례대로 작은 값들 부터 저장을 하면 되는 겁니다.

그렇게 해서 최종적으로 나온 결과가 바로 보시는 것처럼 이렇게 정렬이 된 형태를 만들 수 있는 거죠.

자, 지금은 이제 머지 소트가 어떻게 동작하는지 큰 그림을 그리기 위해서 개념적으로 간단하게 설명을 한 거라면 이제부터는 좀 더 구체적으로 자세히 이 머지 소트 의 동작 방식을 살펴보도록 하겠습니다.

자, 이 배열에 대해서 머지 소트를 수행을 할 건데 디바이드 앤 컨커로 동작을 하기 때문에 얘를 이렇게 반으로 딱 나눠서 절반 크기의 서브 프라블럼 2개를 만듭니다.

그래서 이렇게 두 개의 서브 프로그램이 생겼으며 이제 재귀적으로 이 각각에 대해서 merge sort를 수행을 해야 되는 겁니다.

그러면 차례대로 먼저 이 왼쪽 서브 프로그램에 대해서 merge sort를 수행을 해야 돼요.

그러면 이 서브 프로그램에 대해서 merge sort를 수행하려고 하다 보니까 얘는 또 다시 재귀적으로 동작을 하게 되는 거잖아요.

이 merge sort를 이 프로그램에 대해서 수행을 하는 거니깐요.

그러면 얘는 또 다시 이렇게 반으로 사이즈를 나눕니다.

그러면 또다시 이 두 개의 서브 프로그램이 생겼어요. 그러면 다시 이 각각의 서브 프로그램에 대해서 merge sort를 수행을 할 수 있는 거죠.

마찬가지로 얘도 차례대로 merge sort를 수행을 하기 위해서 이 왼쪽에 있는 서브 프로그램에 대해서 merge sort를 먼저 수행을 할 겁니다.

그래서 재 귀적으로 이렇게 merge sort를 수행을 하는데 얘도 마찬가지로 또다시 이 서브 프로그램으로 나눌 수가 있죠.

이렇게 두 개의 서브 프로그램이 생겼고 이 두 개 중에 이 친구에 대해서 먼저 머지 소트를 수행을 할 겁니다.

그러면 얘에 대해서 머지 소트를 수행을 하는데 얘에서 또다시 서브 프라블럼으로 나눌 수가 있어요.

그러면 얘는 개수를 1 가지는 서브 프로블럼 두 개로 나눠진 겁니다.

그러면 이 상황에서는 예부터 먼저 머지 소트를 수행을 하는데 얘는 이제 더 이상 쪼갤 게 없어요.

그럼 연예에 대한 머지 소트는 끝나는 겁니다.

그래서 이에 대한 머지 소트의 결과는 그대로 100이 되고 이제 얘에 대한 머지 소트가 끝났기 때문에 그러면 이제 이 친구에 대한 머지 소트를 또 수행을 해야 되는 거잖아요.

그런데 얘도 개수가 하나밖에 없기 때문에 더 이상 서브 프라블럼으로 쪼갤 수가 없어요.

나눌 수가 없습니다. 그러면 얘도 그냥 그대로 50으로 끝나는 거죠.

결국 얘에 대한 머지 소트의 솔루션은 그냥 이 50 그 자체가 되는 거예요.

자, 그러면 이제 중요합니다. 이 친구에 대해서 머지 소트를 수행하려고 얘를 반으로 나눠서 얘에 대해서 머지 소트하고 얘에 대해서 머지 소트를 해서 준다 이제 이렇게 결과가 나온 거잖아요.

솔루션이 나온 거잖아요. 그러면 이제 이 두 개의 솔루션을 합쳐져야 됩니다.

머지를 해줘야 되는 거죠. 컴바인을 해줘야 되는 겁니다. 그러면 얘를 어떻게 합쳐주냐?

이게 이제 머지 소트에서 중요한 부분인데요. 얘와 똑같은 배열을 이렇게 만들고 그다음에 얘와 똑같은 배열을 이렇게 만듭니다.

그리고 나서 이제 이 두 개를 비교해 100과 50을 비교를 해서 더 작은 걸 찾는 거죠.

그럼 50이 더 작잖아요. 그러면 이제 이 백의 자리에 50이 들어가게 되는 겁니다.

그리고 이제 50에 대한 처리는 끝이 나는 거죠.

그러면 남은 건 100이잖아요. 그럼 이제 남아있는 자리에 100이 들어가게 되는 겁니다.

그리고 200에 대한 처리도 끝이 났어요.

그러면 결과를 놓고 보면 이제 이 자리는 어떻게 바뀌었냐? 원래 150 이었는데 이제는 이렇게 50 - 되는 겁니다.

결국 이 두 개에 대해서는 이제 정렬이 끝이 난 거예요.

그런데 이 두 개에 대한 정렬이 끝이 났다는 것은 이 부분에 대한 머지 소트를 할 때에 이 머지 소트의 서브 프로블럼이 어떤 이 부분에 대한 머지 소트가 끝났다는 얘기인 거잖아요.

그럼 이제 이 부분에 대한 머지 소트를 또 해줘야 되는 겁니다. 그래서 이제 이 부분에 대한 머지 소트를 시작을 해보면 이 서브 프로블럼 을 해결하기 위해서 다시 또 재귀적으로 머지 소트를 하는 거잖아요.

그러면 예를 또 반으로 나눠서 이 서브 프로블럼과 이 서브 프로블럼 각각에 대해서 머지 소트를 또 해줘야 되는데, 먼저 예부터 머지 소트를 하게 되면 얘는 지금 아이템이 하나밖에 없기 때문에 더 이상 쪼갤 수가 없어요.

그러면 32가 그냥 그대로 끝이 납니다. 그래서 이 위치에 대한 머지 소트는 이대로 종료가 되고요.

이제 그러면 이어서 또 이 위치에 대해서 머지 소트를 해야 되겠죠.

근데 얘도 지금 아이템이 하나이기 때문에 더 이상 쪼갤 수가 없어요.

그러면 얘도 그대로 그냥 끝이 나는 겁니다.

그래서 67 상태 그대로 이 부분에 대한 머지 소트도 끝이 났고 그러면은 다시 돌아와서 지금 이 부분에 대한 머지 소트를 하기 위해서 얘를 반으로 나눠서 이 서브 프로그램과 이 서브 프로그램에 대해서 머지 소트를 수행을 한 거잖아요.

그러면 이제 이 각각에 대한 머지 소트는 끝이 났기 때문에 이 부분에 대한 머지 소트를 완성시키기 위해선 이 각각의 솔루션을 머지를 시켜 줘야 됩니다.

컴바인을 시켜 줘야 되는 거죠. 그러면 마찬가지로 이와 똑같은 형태의 배열을 이렇게 만들고 또 예와 똑같은 형태의 배열을 이렇게 만듭니다.

그리고 나서 이 두 개를 비교를 해요. 어느 게 더 작은지.

근데 32가 더 작습니다. 그럼 요기다 32를 적어 줘야 되는데 어차피 똑같죠.

그러면 32에 대한 처리가 끝이 난 거예요. 이 다음에 한번 비교할 게 없으니까 바로 67 남은 거라서 남은 공간에 67을 써주면 됩니다.

그러면 얘는 원래의 오리지널과 차이가 없죠. 그러면 최종적인 결과는 이런 형태가 되는 겁니다.

이제 이 부분에 대해서는 정렬이 된 거예요.

자 그러면 이 부분에 대해서 정렬이 됐다는 것은 요 부분에 대한 머지 소트가 끝났다는 얘긴 거잖아요.

divide and conquer, 분할정복이라고 하죠~ 개념과 동작 방식을 설명하구요, merge sort를 통해 divide & conquer가 어떻게 동작하는지 살펴봅니다~

8년차 백엔드 개발자가 배워서 남주려고 만든 채널이에요

알기 쉽게 설명합니다

함께 성장했으면 좋겠어요 :)


#컴공맛집 #백엔드전문채널


divide and conquer, 분할정복이라고 하죠~ 개념과 동작 방식을 설명하구요, merge sort를 통해 divide & conquer가 어떻게 동작하는지 살펴봅니다~

Scripts