네 반갑습니다 오늘 이 영상을 끝까지 보신 후엔 디바이드 앤 컨커의 개념을 이해하게 되구요 그리고 뭐지 솔트

에서 디바이드 앤 컨커가 어떻게 적용이 되는지 알게 됩니다 자 그럼 오늘도 고고씽 먼저 디바이드 앤 컨커 가 무엇인지

소개하도록 할게요 디바이드 앤 컨커 란 문제를 해결하는 전략 중의 하나입니다 그러니까 우리가 프로그래밍을 하다

보면 여러 가지 해결해야 될 문제들이 있는데요 이런 문제들을 해결하기 위해서 다양한 전략들이 존재할 수 있어요 이 디바이드 앤 컨커 는 그런

전략들 중에 하나입니다 그러면 얘는 어떤 식으로 문제를 해결하는 전략이 냐 며 이 디바이드 앤 컨커 는

예를 들어서 어떤 프로그램이 있습니다 어떤 문제가 있는데 이 문제를 그 문제 유사한 형태를 가지는 더 작은

크기의 서브 문제들로 나눕니다. 그렇게 나눈 뒤에 각각의 서브 프로그램들을 재귀적으로 동일한

방식으로 해결한 뒤에 그 결과를 활용해서 원래의 문제를 해결하는 방식을 디바이드 앤 컨커라고 합니다.

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

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

식으로 더 잘게 작은 크기의 서브 프로그램으로 문제가 쪼개지는 거죠. 그렇게 서브 문제들로 문제를

나눈 뒤에 이들 서브 프로그램 각각을 다시 또 재귀적으로 같은 방식으로 해결하는 겁니다. 그러니까 이게 2

서브 프로그램 이 얘기가 생긴 거잖아요 그러면 이 4개의 대해서 다시 또 재귀적으로 같은 방식으로 접근을 하는 거예요 그래서 예를

들어서 2 서브 프로 블럭의 경우의 예를 또다시 쪼갤 수 있으면 좋게 보는 거죠 얘도 마찬가지로 똑같이 더

작은 서브 프라블럼으로 쪼갤 수 있으면 좋게 보는 거고 얘도 그리고 얘도 쪼갤 수 있으면 좋게 보는

겁니다 그래서 지금 이 각각의 서브 프로그램을 사실은 더 작은 크기의 서브 프로그램으로 쪼개 보면 이제

이런 모습이 되는 거죠 그러면 또다시 얘네들 각각에 대해서 다시 또 재귀적으로 같은 방식으로 쪼갤 수

있으면 좋게 보는 건데 그런데 예를 들어서 이제 이 상황에서 더 이상 쪼갤 수 없다고 해 볼게요 이런

상황에서 더 이상 쪼갤 수 없다며 이제 이 때는 다이렉트로 이 문제를 해결하는 겁니다. 그래서 다이렉트로 문제를 해결해서 나우 솔루션을 얻을

거예요. 그러면 이 각각을 해결할 솔루션들이 이제 생겼을 거고 그러면 이제 솔루션들을 합쳐서 이제 원래의

프로 블럭의 대한 솔루션들을 만드는 거예요. 어떤 말이 이해가 되시죠? 이 각각의 서브 프로그램들의 솔루션들을

활용을 해서 원래의 프로그램의 솔루션을 얻고 하는 겁니다. 이런 방식으로 원래 트롤러 메 솔루션의

들을 구해 보며 이제 ef 로 블룸 들에 대한 솔루션들이 나온 거죠. 그럼 이제 1% 블룸의 솔루션들을 바탕으로

다시 또 원래의 프로그램에 대한 솔루션을 만드는 겁니다. 그러면 최종적으로 맨처음 프라블럼 의

솔루션이 나오는 거죠 이런 방식을 '디바이드 앤 컨커'라고 합니다 그래서 정리를 하면 '디바이드 앤 컨커'는 '디바이드'

'컨커' 컴바인 이란이 3단계로 구성이 되는데요 먼저 디바이드 같은 경우에는 원래의 프로그램을 더 작은 크기의

서브 프로그램들로 나누어 줍니다 그렇게 나누어 준 뒤에 각 서브 프로그램들을 컴페어 해야 되는데요 이때

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

서브 프로그램 각각에 대해서 이 '디바이드 앤 컨커'를 다시 또 적용한다는 의미에요 그런데 만약에 이 서브

프로그램의 사이즈가 너무 작아서 더 이상 나눌 수가 없다면 더 이상 쪼갤 수가 없다면 그럼 이 때는

다이렉트로 직접 해결해야 됩니다. 어쨌든 이런 식으로 해결하고 나니 에 그러면 이제 각 서브 프로그램들에

대한 솔루션들이 생길 거 잖아요. 그럼 이제 이 마지막 단계는 바로 컴바인 입니다. 그래서 이 서브 프로그램들의

솔루션들을 합쳐서 원래의 오리진을 프로 블러 메 솔루션을 만드는 거 어렵지 않죠. 그러면 이 디바이드

앤 컨커는 어디서 활용이 되는 야 우리가 공부하면서 1 쉽게 접하는 사례는 멀티 소트 나 퀵 솔 즉 혹은 우리가

시간 복잡도 영상에서 배웠던 바이너리 서치 이런 것들이 디바 2 된 컬을 활용한 그런 사람입니다. 그러면 오늘

우리가 한번 배워 볼 거는 뭐 제 솔트웨어 이 뭐지 소프트가 어떻게 이 디바이드 앤 컨커 를 활용 했는지

이걸 이제 같이 살펴보도록 하겠습니다. 뭐 어제 쇼트 하는 것은 그 이름에서도 알 수 있듯이 정렬 알고리즘이에요. 여러 개의

데이터들이 이렇게 배열에 혹은 리스트에 저장이 되어 있을 때 얘네들을 어떻게 정렬시킬 수 있을까 이게 이제 정렬 알고리즘이고 멀티

스포츠는 이 정렬 알고리즘 중에 하나인 겁니다. 그러면 2 멀티 소프트는 디바이드 앤 컨커를

활용해서 동작한다고 했기 때문에 이렇게 인풋이 주어졌을 때 임프 슬 서브 프라블럼으로 나누어서

재귀적으로 해결할 거예요. 디바이드 앤 컨커를 활용하는 거니까요. 그럼 얘는 어떻게 하냐 사이즈를 이렇게

반으로 나눕니다. 그러면 이제 두 개의 서브 프로그램이 생긴 거잖아요. 이 두 개의 서브 프로그램 각각에 대해서 뭐

제 소스를 실행하는 겁니다. 그러면 현재는 얘들이 이렇게 정렬이 되어 있지 않은 상태인데 이 각각에 대해서

뭐지? 포트를 실행한 이후에는 얘네들이 이제 정렬이 되어 있을 겁니다. 그래서 이렇게 멋있게 틀을 실행한 후에는

얘네들 각각은 순서대로 오름차순으로 정렬이 되어 있다라는 것을 볼 수 있구요. 그러면 이렇게 있어 버프로 블

럼에 대한 솔루션들이 이렇게 생긴 거잖아요. 그러면 이 솔루션즈를 바탕으로 뭘 해야 되냐면 원래 a

오리지널 프라블럼의 솔루션을 구하기 위해서 이 프라블럼의 솔루션들을 활용을 합니다. 그래서 이 솔루션들을

바탕으로 오리지널 프라블럼을 해결하는 거죠. 즉 오리지널 프라블럼의 솔루션을 구하는 거죠. 그러면 어떻게

이 솔루션을 구할 수 있냐 지금 이 솔루션과 이 솔루션 각각은 이미 정렬이 이렇게 되어있는 상태이기

때문에 그러면 순서대로 하나씩 확인을 하면서 차곡차곡 차례대로 작은 값들부터 저장을 하면 되는 겁니다 그렇게

해서 최종적으로 나온 결과가 바로 보시는 것처럼 이렇게 정렬이 된 형태를 만들 수 있는 거죠 자 지금은 이제 뭐지 소트가 어떻게 동작하는지

큰 그림을 그리기 위해서 개념적으로 간단하게 설명을 한 거라 며 이제부터는 좀 더 구체적으로 자세히 이 뭐지 소스

의 동작 방식을 살펴보도록 하겠습니다 자 이 배열에 대해서 뭐지 소프트를 수행을 할 건데 디바이드 앤 컨커

동작을 하기 때문에 예를 이렇게 반으로 딱 나눠서 절반 크기의 서브 프로 물론 2개를 만듭니다 그래서

이렇게 두 개의 서브 프로그램이 생겼으며 이제 제 기적으로 이 각각에 대해서 뭐지 포트를 수행을 해야 되는 겁니다 그러면 차례대로 먼저 이 왼쪽

서브 프로그램에 대해서 뭐지 포트를 수행을 해야 돼요 그러면 이 서브 프로그램에 대해서 멋있어 틀을 쌩

하려고 하다 보니까 얘는 또 다시 재귀적으로 동작을 하게 되는 거잖아요 뭐지 포트를 이 프로그램에 대해서

수행을 하는 거니깐요 그러면 얘는 또 다시 이렇게 반으로 사이즈를 나눕니다 그러면 또 다시 이 두 개의 서브

프로그램이 생겼어요 그러면 다시 이 각각의 서브 프로그램에 대해서 뭐지 소스를 수행을 할 수 있는 거죠

마찬가지로 얘도 차례대로 뭐지 소스를 수행을 하기 위해서 이 왼쪽에 있는 서브 프로그램에 대해서 멋있어 틀을

먼저 수행을 할 겁니다 그래서 잭 유적으로 이렇게 뭐지 수트를 수행을 하는데 얘도 마찬가지로 또다시 2

서브 프로그램으로 나눌 수가 있죠 이렇게 두 개의 서브 프로그램이 생겼고 이 두 개 중에 이 친구에 대해서

먼저 뭐지 포트를 수행을 할 겁니다 그러면 예에 대해서 뭐지 수트를 수행을 하는데 에서 또다시 서브 프로그램으로 나눌 수가 있어요

그러면 얘는 개수를 1 가지는 서브 프로그램을 2개로 나눠진 겁니다 그러면 은 이 상황에서 는 예부터

먼저 뭐지 솥을 수행을 하는데 얘는 이제 더 이상 쪼갤 게 없어요 그럼 연예에 대한 뭐지 포트는 끝나는

겁니다 그래서 이에 대한 머리 솥에 결과는 그대로 100이 되고 이제 얘 에 대한 뭐지 소치가 끝났기 때문에

그러면 이제 이 친구에 대한 뭐지 소스를 또 수행을 해야 되는 거잖아요 그런데 얘도 개수가 하나밖에 없기

때문에 더 이상 서브 프로그램으로 쪼갤 수가 없어요 나눌 수가 없습니다 그러면 얘도 그냥 그대로 50으로 끝나는 거죠 결국 예에

대한 뭐지 소스 솔루션은 그냥 2 50 그 자체가 되는 거예요 자 그러면 이제 중요합니다 이 친구에 대해서 뭐지 솥을 쇠하려고 얘를 반으로

나눠서 얘에 대해서 멋있어 트라고 얘에 대해서 뭐지 포트를 해서 준다 이제 이렇게 결과가 나온 거잖아요

솔루션이 나온 거잖아요 그러면 이제 이 두 개의 솔루션을 합쳐져야 됩니다 뭐지 를 해줘야 되는 거죠 컴파일을

해 줘야 되는 겁니다 그러면 얘를 어떻게 합쳐질 야 이게 이제 뭐지 솥에서 중요한 부분인데요 얘와

똑같은 배열을 이렇게 만들고 그 다음의 예와 똑같은 대여를 이렇게 만듭니다 그리고 나서 이제 이 두 개를

비교해서 액과 50을 비교를 해서 더 작은 걸 찾는 거죠 그럼 52가 더 작잖아요 그러면 이제 이 백의

자리의 52가 들어가게 되는 겁니다 그리고 이제 50에 대한 처리는 끝이 나는 거죠 그러면 남은 건 102잖아요 그럼 이제 남아있는 자리에

102가 들어가게 되는 겁니다 그리고 200에 대한 처리도 끝이 났어요 그럼 이 결과를 놓고 보면 이제 이 자리는 어떻게 바뀌었냐 원래 150

이었는데 이제는 이렇게 50이 되는 겁니다 결국 이 두 개에 대해서는 이제 정렬이 끝이 난 거예요 그런데

이 두 개에 대한 정렬이 끝이 났다는 것은 이 부분에 대한 뭐 g 스포트를 할 때에 이 뭐지 소프트웨어 서버 프로

블룸이 어떤 이 부분에 대한 뭐지 소프트가 끝났다는 얘기인 거잖아요 그럼 이제 이 부분에 대한 뭐지

소스를 또 해줘야 되는 겁니다 그래서 이제 이 부분에 대한 뭐지 소스를 시작을 해 보며 e 서브 프로 블룸

을 해결하기 위해서 다시 또 재귀적으로 뭐지 소스를 하는 거잖아요 그러면 예를 또 반으로 나눠서 2 서브 프로 블룸과 2 서브 프로그램

각각에 대해서 뭐지 소스를 또 해줘야 되는데 먼저 예부터 뭐지 수트를 하게 되면 얘는 지금 아이템이 하나 밖에

없기 때문에 더 이상 쪼갤 수가 없어요 그러면 32가 그냥 그대로 끝이 납니다 그래서 이 위치에 대한 뭐지 소천의 이대로 종료가 되구요

이제 그러면 이어서 또 이 위치에 대해서 뭐지 솥을 해야 되겠죠 근데 얘도 지금 아이템이 하나이기 때문에

더 이상 쪼갤 수가 없어요 그러면 얘도 그대로 그냥 끝이 나는 겁니다 그래서 67 상태 그대로 이 부분에

대한 뭐지 소주도 끝이 났고 그러면은 다시 돌아와서 지금 이 부분에 대한 뭐 제 포트를 하기 위해서 얘를 반으로 나눠서 이제 버프로 블룸과 2

서브 프로그램에 대해서 뭐지 스포츠 수행을 한 거잖아요 그러면 이제 이 각각에 대한 뭐지 스포츠는 끝이 났기

때문에 이 부분에 대한 뭐지 포트를 완성시키기 위해선 이 각각의 솔루션을 뭐지 를 시켜 줘야 됩니다 컴바인을

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

배열을 이렇게 만듭니다 그리고 나서 이 두 개를 비교를 해요 얻는 게 더 작은지 근데 32가 더 작습니다

그럼 요기다 30일 적어 줘야 되는데 어차피 똑같죠 그러면 32에 대한 처리가 끝이 난 거예요 이 다음에

한번 비교 할게 없으니까 바로 67 남은 거라서 남은 공간에 67을 써주면 됩니다 그러면 얘는 원래의

오리지널과 차이가 없죠 그러면 최종적인 결과는 이런 형태가 되는 겁니다 이제 이 부분에 대해서 정렬이 된 거예요 자 그러면 이

부분에 대해서 정렬이 됐다는 것은 요 부분에 대한 뭐지 포트가 끝났다는 얘긴 거잖아요 그 말은 전체 이

부분에 대한 뭐지 소트를 수행하기 위해서 반으로 나눠서 이에 서브 프라블럼을 멋이 소스 시켰고 또

이 서브 프라블럼을 뭐지 솔트 시켜서 이 두 개의 각각은 정렬이 됐다는 얘기예요 그러면 이제 해줘야 될

것은 뭐죠 이 두 개를 이제 뭐지 시켜 주는 것 컴바인 시켜 주는 겁니다 이 두 개를 합쳐 줘야 되는 거죠 그러면

마찬가지로 이해와 똑같은 배열을 이렇게 하라 만들고 또 예와 똑같은 배열을 이렇게 하나 만듭니다 그리고

나서 이 앞에서부터 이렇게 비교를 하는 겁니다 50과 31일 비교를 하는데 뭐가 더 작은지 32가 더 작죠 그러면 이 첫 번째 자리에는

이제 50이 아니라 32가 들어가게 되는 겁니다 그리고 나서 이 아래쪽에서는 32에 대한 처리가 끝이 났기 때문에 그러면 이어서 이제

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

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

알기 쉽게 설명합니다

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


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


쉬운코드

소개 및 개요: 디바이드 앤 컨커(Divide and Conquer) 전략

영상을 통해 디바이드 앤 컨커 개념과 솔트에서의 적용을 이해한다.

디바이드 앤 컨커는 문제 해결 전략 중 하나이다.

프로그래밍 문제 해결을 위한 다양한 전략 중 하나이다.

문제를 유사한 형태의 더 작은 서브 문제로 나누어 재귀적으로 해결 후 결과를 합쳐 원래 문제를 해결한다.

그림을 통해 문제 분할 및 재귀적 해결 과정을 시각적으로 설명한다.

디바이드 앤 컨커의 3단계: 분할(Divide), 정복(Conquer), 결합(Combine)

디바이드 앤 컨커는 '분할', '정복', '결합'의 3단계로 구성된다.

디바이드: 원래 문제를 더 작은 서브 문제로 나눈다.

컨커: 각 서브 문제를 재귀적으로 동일한 방식으로 해결한다.

더 이상 나눌 수 없을 때는 직접 문제를 해결한다.

컴바인: 각 서브 문제의 해결 결과를 합쳐 원래 문제의 해결책을 만든다.

머지 소트(Merge Sort) 알고리즘 분석

머지 소트는 디바이드 앤 컨커를 활용한 정렬 알고리즘이다.

입력 데이터를 서브 문제로 나누어 재귀적으로 정렬한다.

데이터를 절반으로 나누고 각각에 대해 머지 소트를 실행한다.

정렬된 서브 문제들의 결과를 이용하여 원래 문제를 해결한다.

정렬된 서브 문제들을 합쳐 최종 정렬 결과를 얻는다.

머지 소트 동작 과정 상세 분석 (코드 설명 포함)

재귀적 호출을 통해 서브 문제들을 반복적으로 분할하고 정렬한다.

서브 문제들의 정렬 결과를 병합하는 과정을 자세히 설명한다.

재귀적 호출을 통해 서브 문제들을 반복적으로 분할하고 병합하는 과정을 보여준다.

파이썬 코드를 통해 머지 소트의 재귀적 동작을 보여준다.

코드의 파라미터 (배열, 시작 인덱스, 끝 인덱스)를 설명한다.

머지 소트의 시간 복잡도 및 결론

머지 소트는 디바이드 앤 컨커 방식으로 구현되어 있다.

입력 데이터의 형태에 관계없이 항상 같은 시간 복잡도를 가진다.

디바이드 앤 컨커와 머지 소트에 대한 복습 및 다음 영상 예고 (다이나믹 프로그래밍).