introduction to algorithm

1. Review- 분할 정복(Divide & Conquer)중 하나인 Strassen Algorithm에 대해서 알아보자.- 우리는 앞서 4-1 에서 행렬곱을 계산하는 알고리즘에 대해서 알아보았다.- 이때 코드를 다시한번 바라봐보자.A = [[1,2],[3,4]]B = [[5,6],[7,8]]C = [[0,0],[0,0]]for i in range(2): for j in range(2): for k in range(2): C[i][j] += A[i][k]*B[k][j]C------------------------------------------------------[[19, 22], [43, 50]]- 이를 시간 복잡도로 표현하면 O(n^3)과 같다.- 그 이유는 ..

1. Introduction- 알고리즘은 다양하게 선택가능하다. - 예를들어 Insertion Sort는 Incremental method(증분 방법)을 사용한다.- 이번 챕터에선 분할 정복(divide and conquer) 이라는 설계 방법을 간단하게 다루게 된다. - 자세한 방법은 챕터 4때 알아보도록 하자. 2. Divide and Conquer(분할 정복)- 많은 유용한 알고리즘들은 재귀적(recursive) 구조를 가지고 있음.- 주어진 문제를 해결하기 위해, 이들은 스스로 한번 이상 호출하여 하위문제들을 해결함- 일반적으로 분할 정복(Divide & Conquer)을 따름- 문제를 원래 문제와 유사하지만 더 작은 크기의 여러 하위 문제로 나누고, - 하위 문제를 재귀적으로 해결한 뒤 이러한 ..