알고리즘

문제를 해결할 수 있는 잘 정의된 유한시간 내에 종료되는 계산적인 절차

알콰리즈미가 아라비아 숫자를 곱하는 방법에 대한 책을 집필 대수학의 아버지

문제를 해결하는 절차

• 분할정복
• 동적계획
• 탐욕 알고리즘
• 백트래킹
• 분기한정법

문제의 분야에 따라서 방법이 다르다

sorting, searching, cryptography, optimization 등..

예시: 정수의 곱셈 일반화

n자리수 곱하기 n자리수의 프로그램 만들기

O(n2)만큼의 시간이 필요한데

더 빠르게 하는 방법?

divide and conquer

네자리수를 두자리수로 만든다.

두자리수 곱하기 두자리수 4개로 만든다 인수분해

두자리수 곱도 한자리수로 쪼개고..

각 1의 자리수 곱셈은 기억하고 있는다