dlng23

12-1 공간으로 시간을 살 수 있나요?시간과 공간의 효율성은 충돌하는 요소 많은 경우 시간 효율성이 더 중요하게 인식되기 때문에 많은 메모리를 사용하여 처리시간을 줄이려는 다양한 전략들이 개발됨 가능한 모든 입력에 대한 답을 미리 다 구해서 저장→ 대부분은 가능한 모든 입력이 거의 무한하게 많아 미리 계산하기 어렵고, 답을 저장할 공간도 턱없이 부족그러나, 현실적인 수준에서 이 전략을 사용하는 알고리즘도 다수 존재함기수 정렬이 위 전략에 해당, 미리 버킷을 많이 준비해두고, 입력 데이터를 배분하는 방법으로 정렬입력의 제한이 존재하지만 거의 선형(O(n))에 가까운 성능문자열 매칭 문제에서도 사용 가능, 효율적인 탐색을 위한 전처리로 테이블을 만들어 두어 더 효율적으로 문자열 매칭 가능동적 계획법도 부분..

11-1 동적 계획법이란?동적 계획법도 분할 정복과 같이 문제를 더 작은 부분으로 나눈 후 답을 계산하여 답들로부터 원래 문제의 해답을 구하는 구조동적 계획법은 부분 문제들의 답을 어딘가에 저장해 둔 뒤 필요할 때 다시 꺼내서 사용하는 전략을 사용한다는 점에서 차이 존재 피보나치 수열 문제n번째 피보나치 수를 구하는 fib(n)은 위와 같이 순환 관계로 나타낼 수 있음 순환 관계는 분할 정복을 이용하여 해결할 수 있으나, 심각한 계산 중복 문제가 발생하고, 시간 복잡도가 O(2^n) 동적 계획법은 구한 답을 저장하여 재사용 → 다시 풀어야 할 때는 저장된 해답을 이용부분 문제의 해를 저장하는 방법에는 메모이제이션과 테이블화가 있음 메모이제이션을 이용한 피보나치 수열메모이제이션(memoization): 함..