Brute-Force

Brute-Force

• brute: 무식한, force: 힘 → 무식한 힘.
  완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져옴. 컴퓨터의 빠른 계산 능력 이용 (컴퓨터의 장점을 가장 잘 이용함)

• 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법

• brute-force는 '해가 하나 이상 존재한다'라는 가정을 세우고 모든 경우의 수를 구함

• 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, breadth first search)이 가장 기본적인 도구 *너비 우선 탐색이 부르트포스와 더 관련이 깊음

• 선형 : {1, 2 , 3, 4 ,5 , 6, 8, 9} 이런것들

ex) 10명 줄을 세우는데, 3명이 사이가 안좋아 떨어뜨려 놓는 줄을 세우는 방법은?
→ 모든 경우의 수를 전부다 구해서 세명이 떨어져 있는 경우의 수를 구함

재귀호출

• 컴퓨터가 수행하는 작업을 작은 조각들로 나누어 볼 수 있는데, 쪼개는 범위가 작아지면 조각들의 형태가 유사해지는 작업들을 볼 수 있음. 이런것을 바로 '재귀 함수'라고 함

• 재귀함수는 여러형태의 조각으로 쪼개 한 조각 수행하고 나머지는 자신을 호출하여 실행함수를 가리킴 (내가 볼땐 자기자신 = 실행 함수)

ex)

int recursiveSum(int n)
	if(n == 1) return 1;
	return n + recursiveSume(n-1)

• n이라는 조각으로 나누어 실행

★ 더 이상 쪼개 지지 않는 최소한의 작업에 도달 했을 때 답을 곧장 반환하는 조건물을 포함해야 됨 → '재귀호출의 기저 사례' ★

• 재귀 호출의 기저 사례를 선택할 때는 모든 이력이 항상 기저 사례의 답을 이용해 계산할 수 있도록 신경 써야됨

• 재귀 호출을 사용하여 특정 조건을 만족하는 조합을 모두 생성하는 코드를 쉽게 작성 → 완전 탐색을 구현 할 때 아주 유용한 도구

• 재귀 호출을 논의할 때 '문제'란 항상 수행해야 할 작업과 그 작업을 적용할 자료의 조합을 의미