6. 무식하게 풀기

6.1 도입

전산학에서 **무식하게 푼다(brute-force)**는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법
이렇게 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 완전 탐색(exhaustive search) 이라고 한다.
- 이는 가장 간단하지만, 컴퓨터의 장점을 가장 잘 이용하는 방법이다.

컴퓨터가 하는 작업들은 대개 작은 조각들로 나누어 볼 수 있다.
우리가 들여다보는 범위가 작아지면 작아질수록 각 조각들의 형태가 유사해지는 작업들을 많이 볼 수 있다.
이런 작업을 구현 할 때, 유용하게 사용되는 개념이 바로 재귀 함수, 재귀 호출이다.
재귀 함수: 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤, 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수
모든 재귀 함수는 ‘더 이상 쪼개지지 않는’ 최소한의 작업에 도달 했을 때, 답을 곧장 return 하는 조건문을 포함해야한다.
- 이때, 가장 작은 작업들을 가리켜 재귀 호출의 base case(기저 사례) 라고 한다.
기저 사례를 선택할 때는 존재하는 모든 입력이 항상 기저 사례의 답을 이용해 계산할 수 있는지 신경써야 한다.
기저 사례 조건의 순서는 바뀌면 안 된다.
입력이 잘못되거나 범위에서 넘어가는 경우를 기저 사례에 맨 처음에 두면 편리하다.
중첩 반복문을 재귀 호출 함수로 대체 해서, n개 중 몇 개를 고르든지 조합을 찾을 수 있다.
- 이를 통해, 재귀 호출로 완전 탐색을 구현하기 용이하다.

재귀 호출을 논의할때 ‘문제‘란 항상 수행해야 할 작업과 그 작업을 적용할 자료의 조합을 의미한다.
- 주어진 자연수 수열을 정렬하라: 문제 x
- {1,2,200,3,5} 을 정렬하라: 문제 o
- {1,2,3}을 정렬하라, {3,2,1}을 정렬하라는 서로 다른 문제이다.
원래 **문제(problem)**에서 한 조각이 원래 문제의 일부 일 때, 이런 문제들을 **부분 문제(subproblem)**라고 한다.
- 부분 문제가 원래 문제를 푼 결과이고, 원래 문제와 형식이 같을 때

답을 중복으로 세는 경우 방지: 항상 특정 형태를 갖는 답만 세기
- 흔한 방법: 사전 순으로 가장 먼저 오는 답 하나만 세기, (2,3), (0,1) 은 세지 않고, (0,1), (2,3) 만 센다.
- 이 속성을 강제하기 위해서는 각 단계에서 남아 있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아 주도록 하면 된다.

블록을 놓는 순서는 중요하지 않다. 특정한 순서대로 답을 생선하도록 강제할 필요가 있다.
- 각 재귀 호출마다, 가장 윗 줄, 가장 왼쪽에 있는 칸을 덮도록만 한다.

경우의 수 문제와 달리, 답이 하나가 아니라, 여러 개 이고, 그 중 어떤 기준에 따라, 가장 ‘좋은’ 답을 찾아 내는 문제를 통칭해 최적화 문제라 한다.
- 최대화, 최소화, 최단 경로, 최소 비용 등등
이런, 최적화 문제를 푸는 여러 방법 중 기초적인 것은 완전 탐색이다.
- 가능한 답을 모두 생성하고, 그 중 가장 좋은 것을 찾아내면 되기 때문이다.

주어진 원소로 만들 수 있는 모든 순열 만들기(경우의 수), 순열, nPn = n!, n이 10을 넘어가면 보통 시간 초과
주어진 원소 중 R개를 골라낼 수 있는 방법 만들기(경우의 수), 조합
2^n 가지 경우의 수 만들기
- n개의 질문에 대한 답이 yes/no 일 때, 가능한 답의 모든 조합의 수는 2^n 가지이다.
- 각 조합을 하나의 n비트 정수로 표현하면, 재귀 호출을 사용할 것 없이 1차원 for문 하나로 이 조합들을 간단하게 모두 시도할 수 있다.
  - 16장: 비트마스크