알고리즘/분류 (22) 썸네일형 리스트형 분할 정복 솔루션 [1. 개요] 문제를 한 조각과 나머지 전체로 나누는 완전 탐색과 달리 거의 같은 크기의 부분 문제로 나누는 점에서 분할 정복은 완전 탐색과 다르다고 볼 수 있다. 분할 정복을 사용하는 알고리즘은 보통 아래와 같은 형태로 구성된다. 문제를 분할 하는 과정 (Divide) 분할하여 해결 한 답을 전체의 답으로 병합하는 과정 (Merge) 더 이상 분할하지 않고 바로 풀 수 있는 작은 문제 (Base case) => 꼭, 더 이상 분할 할 수 없는 경우가 아니더라도 => 이 구간 혹은 이번 부분 문제에서 원하는 답을 구할 수 없겠다 싶으면, => 더 이상 분할하지 않고 넘어 갈 수 있다. 단, 이 구간에서 초기화 해야 될 값이 있으면, 스킵으로 인해 이 값이 적절히 초기화는 시켜주어야 한다. 구현 패턴 기저.. 완전 탐색 솔루션 [1. 개요] 재귀 호출 등을 이용하여 모든 경우의 수를 탐색하여 원하는 답을 구한다. 최대 값 최소 값... 반복문 중첩 대신 재귀 호출로 해결해야 하는 이유는 물리적으로 반복문 N 번 중첩하는 코드를 작성 할 수 없기 때문이며, 재귀적으로 작성하는 편이 더 간단함. 재귀 함수는 반드시(?) 아래와 같이 구현하도록 한다. 자신만의 작성하는 패턴이 있도록 한다. 부분 문제를 정의한다. => 함수의 프로토 타입을 선언 (입력, 출력) => 전체 문제 중 일부 문제를 해결한다. 재귀 함수의 종료를 함수 상단에 두도록 한다. => 보통, 함수의 입력이 배열의 인덱스로 사용 되는데, =>> 배열의 범위를 벗어나는 입력 등인 경우 종료 시키도록 한다. =>> 특정 조건을 만족하는 경우 종료 시키도록 한다. (가지.. 이전 1 2 3 다음