분할정복 알고리즘 (Divide - and - Conquer)정의- 문제의 입력을 분할하여 subproblem을 만든 후 해를 구하는 알고리즘을 subproblem에 적용하여 계산, 해 취합하여 본 문제의 해를 구하는 알고리즘- 분할은 더이상 할 수 없을때까지 진행 한다.- 분할 횟수 구하기 (k): n(입력)은 계속 2등분되며 1개가 될때까지 분할을 진행 한다. 따라서, n/2^k = 1 이고 k = log2n이다. 종류 (문제가 a개로 분할, 크기가 1/b로 감소) a=b=2 : 합병정렬, 최근접 점의 쌍 찾기, 공제선 문제 a=3, b=2: 큰 정수의 곱셈a=4, b=2: 큰 정수의 곱셈a=7, b=2: 스트라센의 행렬 곱셉 알고리즘a=2, b=일정하지 않음: 퀵 정렬a=2, b=2, 하나의 sub..
출처: https://joshuajangblog.wordpress.com/ (번역) 알고리즘을 쉬운 영어로 : 시간 복잡도와 Big-O 표기오늘 번역글은 medium 의 freecodecamp 글입니다. 알고리즘, 시간 복잡도, Big-O 를 사례를 들어가며 이해하기 쉽게 풀어서 설명된 글입니다. 원문 의 모든 부분을 번역하지는 않습니다. 주요 부분만 발췌하여 번역합니다.서론모든 개발자는 자신만의 시간 관념이 있습니다. 개발자들은 대부분의 시간을 사용자들에게 쏟아붓기 때문에, 최대한 시간을 효율적으로 사용하고 싶어하죠. 시간복잡도 를 최소화 함으로써 이게 실현가능해집니다.프로그래밍에서 시간복잡도를 이해하기 전에, 먼저 이 시간복잡도가 알고리즘에서 흔하게 활용된다는 사실을 기억해야합니다.그래서 알고리즘은 ..