문제 가장 멤버가 많은 아이돌 그룹으로 기네스 북에 올라 있는 혼성 팝 그룹 하이퍼시니어가 데뷔 10주년 기념 팬 미팅을 개최했습니다. 팬 미팅의 한 순서로, 멤버들과 참가한 팬들이 포옹을 하는 행사를 갖기로 했습니다. 하이퍼시니어의 멤버들은 우선 무대에 일렬로 섭니다. 팬 미팅에 참가한 M명의 팬들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며 멤버들과 하나씩 포옹을 합니다. 모든 팬들은 동시에 한 명씩 움직입니다. 아래 그림은 행사 과정의 일부를 보여줍니다. a~d는 네 명의 하이퍼시니어 멤버들이고, 0~5는 여섯 명의 팬들입니다. 하지만 하이퍼시니어의 남성 멤버들이 남성 팬과 포옹하기가 민망하다고 여겨서, 남성 팬과는 포옹 대신 악수를 하기로 했습니다. 줄을 선 멤버들과 팬들..

7. 분할 정복 7.1 도입 분할 정복( Divide & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로, 각개 격파라고 설명할 수 있음 주어진 문제를 둘 이상의 부분 문제로 나눈 후, 재귀 호출을 이용해 각각의 답을 계산하고, 부분 문제의 답을 이용해 전체의 답을 계산하는 방식 알고리즘 구성 divide 문제를 더 작은 문제로 분할 merge 각 문제의 답을 전체 문제의 답으로 병합 base case 더이상 답을 분할하지 않고 풀 수 있는 매우 작은 문제 적용가능한 문제의 특성 문제를 부분 문제로 나누는 자연스러운 방법이 존재해야함 부분 문제의 답을 조합해 전체 문제의 답을 계산하는 효율적인 방법이 있어야함 장점 대부분의 경우에서 작업을 빠르게 처리해줌 예제 : 수열의 빠른 합과 행렬의 빠른..