4.2.1 분할 및 정복 전략 이해하기
큰 문제를 서로 독립적인 여러 개의 하위 문제로 쪼갭니다. 각 하위 문제를 푸는 하위 해결책을 도출한 다음, 이를 모두 모으면 전체 문제에 대한 해결책이 됩니다. 이를 분할 및 정복(divide and conquer) 전략이라고 합니다.
데이터셋 d를 가진 문제 P가 있다고 생각해 보겠습니다. 문제 P를 k개로 쪼개서 하위 문제 P1 ~ Pk를 만듭니다. 각 하위 문제는 데이터셋 d의 일부를 사용합니다. 즉 P1은 d1을, Pk는 dk를 사용해 해결하는 것입니다.
구체적인 사례를 통해 더 자세히 알아봅시다.
활용 사례 - 아파치 스파크
아파치 스파크는 분할 및 정복 전략을 이용해 복잡한 문제를 풀어내는 오픈 소스 프레임워크입니다. 스파크는 전체 문제를 여러 개의 작은 하위 문제로 쪼갠 다음, 각 하위 문제를 독립적으로 처리합니다. 간단한 사례로 리스트에 담긴 단어의 개수를 세어 봅시다.
리스트에 다음과 같은 단어들이 들어 있습니다.
[in :]
wordsList = [python, java, ottawa, news, java, ottawa]
우리의 목적은 각 단어의 빈도를 계산하는 것입니다. 분할 및 정복 전략을 사용하면 이를 효율적으로 처리할 수 있습니다.