[파이썬 알고리즘 인터뷰] 분할 정복

• 분할 정복: 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임
  • 직접 해결할 수 있을 정도로 간단한 문제가 될 때 까지 문제를 재귀적으로 쪼개나간 다음(분할), 그 하위 문제의 결과(정복)들을 조합하여 원래 문제의 결과로 만듦(조합)
  • 재귀를 활용하는 대표적인 알고리즘, 최적 부분 구조

 

169. Majority Element

- 브루트 포스 -> 하나하나 count() 메소드로 세다가 과반수인 요소 나오면 리턴

- 다이내믹 프로그래밍 -> 리스트 순회하며 처음 출현한 요소는 count()메소드로 세고, 나왔던 요소는 과반수인지 확인

- 분할 정복 -> 재귀적으로 쪼갠 후 과반수 후보 하나만 상위로 계속 리턴

※ 비교 연산자로 true | false 반환하여 1 | 0으로 활용

- 리스트를 정렬하면 정가운데 인덱스에는 무조건 과반수 요소가 위치함

- 내 풀이: Counter() 활용

 

241. Different Ways to Add Parentheses

- 분할 정복 -> 연산자를 기준으로 분할할 수 있는 모든 경우만큼 재귀적으로 분할하여 정복

* eval('4+5') == 9

• a.extend(b) ↔ a += b, a와 b는 리스트