Study 썸네일형 리스트형 [2/19] 07 분할정복 (1) 07 분할정복 (7.1~7.3) 7.1 도입 분할 정복이란?주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산하는 알고리즘 분할 정복과 재귀 호출의 다른 점은?분할 정복은 문제를 거의 같은 크기의 부분 문제로 나누고, 재귀 호출은 문제를 한 조각과 나머지 부분으로 나눈다는 차이가 있다. 분할 정복 구성 요소 3가지1. Divide : 문제를 더 작은 문제로 분할2. Base case : 더 이상 문제를 분할하지 않아도 풀리는 작은 문제 3. Merge : 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합!이 때, 분할 정복을 적용하기 위해서는 ①문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법과 ②.. [2/18] 06 무식하게 풀기 06 무식하게 풀기 6.1 도입 문제를 만났을 때 가장 먼저 할 생각 : 무식하게 풀 수 있을까? (가장 쉽고 간단) 무식하게 풀기 (brute-force) : 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법. 보통 완전 탐색이라고 함. 컴퓨터의 장점인 “속도가 빠르다”는 속성을 가장 잘 이용하는 방법. 6.2 재귀 호출과 완전 탐색재귀 함수(재귀 호출) : 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수 >> [정리] 자신이 해결할 문제를 부분으로 나눈 후 반복되지 않는 부분을 수행하고 반복되는 부분은 자기 자신을 호출해 실행하는 함수.기저 사례 : 쪼개지지 않는 가장 작은 작업. 존재하는 모든 입력이 항상 기저 사.. 이전 1 2 다음
