파이썬 알고리즘 인터뷰 분할 정복 알고리즘 간단 정리

분할 정복

• 분할 정복 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임 직접 해결할 수 있을 정도로 간단한 문제가 될 때 까지 문제를 재귀적으로 쪼개나간 다음 그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어내는 알고리즘 병합 정렬 알고리즘이 예
  • 알고리즘
    • 분할 문제를 동일한 유형의 여러 하위 문제로 나눔
    • 정복 가장 작은 단위의 하위 문제를 해결하여 정복
    • 조합 하위 문제에 대한 겨로가를 원래 문제에 대한 결과로 조합
• // 연산자 결과가 실수일 때 내림 처리를 하고 동일한 자료형을 리턴해주는 파이썬 특유의 편리한 연산자
• append() vs extend() append() 는 리스트에 또 다른 리스트 삽입 시 리스트 전체를 또 다른 엘리먼트로 처리 extend() 는 삽입 대상의 리스트를 풀어서 각각의 엘리먼트로 확장해 삽입