문제 해결 알고리즘 기초/완전 탐색 (10) 썸네일형 리스트형 완전 탐색으로 n 개 중 r 개 고르기 (조합) ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 조합 서로 다른 n 개 원소를 가지는 집합에서 순서에 상관없이 r 개의 원소를 선택하는 경우의 수를 계산한다. 이는 n 개 원소를 가지는 집합에서 길이가 r 인 부분 집합을 고르는 문제 그리고 이항 계수와 같다. 완전 탐색으로 풀 수 있을까? 이항 계수의 공식은 n choose r = n! / (r! * (n - r)!) 이고 이는 n 개 원소 중 r 개를 고르는 조합의 가짓수와 같다. 따라서, 주어지는 n 과 r 을 통해 수행 가능성을 짐작해 볼 수 있다. 재귀적으로 생각해보기 재귀 호출을 통해 문제를 해결하려면 동일한 형태의 작업으로 나누어 해결해야 하므로 여러개의 유사한 작업 조각으로 나눈다. r 개를 골라야 하므로 원소를 고르는 작업을.. 완전 탐색 알고리즘에 대해서 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 완전 탐색 간단한 문제를 복잡하게 푸는 것은 효율적이지 않다. 따라서, 문제를 마주하면 가장 먼저 "무식하게 풀 수 있을까?" 를 고민해야 한다. 무식하게 푼다는 것은 컴퓨터의 연산 능력에 기대어 가능한 경우의 수를 일일이 나열하며 답을 찾는 것이다. 완전 탐색의 절차 (재귀 호출) 주어지는 조건의 최대 크기로 입력했을 때 시간 내에 계산이 되는지 짐작한다. 가능하면 풀어야 할 문제를 유사한 형태의 작업 조각으로 나눈다. 그 중 하나로 답의 일부를 만들고 나머지 답을 재귀 호출을 통해 완성한다. 작업 조각이 하나 남거나, 하나도 남지 않은 경우 답을 생성한 것이므로 이를 기저 사례로 선택해 처리한다. (재귀 호출을 언제 멈출지 결정.) 예제:.. 이전 1 2 다음