Brute Force (무식하게 풀기)

1. 개요

• 사람들이 가장 많이 하는 실수는 쉬운 문제를 어렵게 푸는 것
• 문제를 마주하고 나면 가장 먼저 무식하게 풀 수 있을까 라는 질문을 스스로에게 하자
• 말 그대로 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법
• 이런 방법을 흔히 완전 탐색 이라고 부르고, 왜 굳이 언급할까 싶지만, 컴퓨터의 장점은 결국 속도가 빠르다는 것이기에 장점을 잘 활용하는 것이기도 하다.

2. 재귀 호출과 완전 탐색

2-1. 재귀 호출(함수)

• 재귀 호출(함수) 란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킴

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  // 1부터 n까지의 합을 구하는 반복문과 재귀함수 int sum(int n) { int ret = 0; for(int i = 1; i <= n; i++) { ret += i; } return ret; } int recursiveSum(int n) { if(n == 1) { return 1; } return n + recursiveSum(n-1); }

• 재귀함수의 경우 if 문에 주목을 하면, 이 조건문이 없으면 함수가 제대로 동작을 하지 않을 것입니다. n=1 이면 조각이 하나 뿐이니, 한 개를 빼고 나면 더 이상 처리할 작업이 없기 때문.

• 모든 재귀 함수는 이와 같이 더이상 쪼개지지 않는 최소한의 작업에 도달햇을 때 답을 곧장 반환하는 조건문을 포함해야 하는데. 이를 기저 사례 (base case) 라고 한다.

• 기저 사례를 선택할 때는 존재하는 모든 입력이 항상 기저 사례의 답을 이용해 계산될 수 있도록 해야함. 만약에 n 이 1인 경우를 확인하는 게 아니라 2라면 3을 반환한다고 하면 입력이 2 이상일 때는 문제가 없지만, 1이 들어오면 문제가 생김

2-2. 예제) 보글 게임

• 5x5 크기의 알파벳 격자를 가지고 하는 게임으로 상하좌우/대각선으로 인접한 칸들의 글자를 이어 단어를 찾아내는 게임

• hasWord(x, y, word) = 보글 게임판의 (y,x)에서 시작하는 단어 word 의 존재여부를 반환한다.

  U	R	L	P	M
  X	P	R	E	T
  G	I	A	E	T
  X	T	N	Z	Y
  X	O	Q	R	S

• 문제의 분할

  1. 가장 자연스러운 방법은 각 글자를 하나의 조각으로 만드는 것
  2. 함수 호출시에 단어의 시작 위치를 정해 주기 때문에 첫 글자가 다르면 바로 false
  3. 그 이후의 word[1..] 의 시작 위치는 첫 글자의 위치에서 인접한 8칸 중 하나 이므로, 여덟 경우를 모두 시도하여 답을 찾으면 됨

• 기저 사례의 선택

  1. 위치 (y,x) 에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패
  2. (1번에 해당하지 않을 경우) 원하는 단어가 한 글자인 경우 항상 성공
  3. (팁) 입력이 잘못되거나, 범위에서 벗어난 경우도 기저 사례로 선택해서 벗어나게 하는 방법이 있음

• 구현

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

  private int[8] dx = {-1, -1, -1, 1, 1, 1, 0, 0} private int[8] dy = {-1, 0, 1, -1, 0, 1, -1, 1} public boolean hasWord(int y, int x, String word) { //기저 사례 1 : 시작 위치가 범위 밖이면 무조건 실패 if(!inRange(y, x)) { return false; } //기저 사례 2 : 첫 글자가 일치하지 않으면 실패 if(board[y][x] != word.charAt(0)) { return false; } //기저 사례 3 : 단어 길이가 1이면 성공 if(word.length() == 1) { return true; } //인접한 여덟 칸을 검사 for(int direction = 0; direction < 8; direction++) { int nextY = y + dy[direction]; int nextX = x + dx[direction]; // 다음 칸이 범위 안에 있는지, 첫 글자는 일치하는지 확인할 필요 없음 if(hasWord(nextY, nextX, word.substring(1))) { return true; } } return false; }

  시간 복잡도 분석

  • 시간 복잡도를 계산하는 것은 비교적 단순하다. 가능한 답 후보들을 모두 만들어 보기 떄문에 시간 복잡도를 계산하기 위해서는 가능한 후보의 수를 전부 세어 보기만 하면 됨
  • 현재 검사하는 후보의 수는 최대 8^N-1 = O(8^N)이 되고, 이것이 시간 복잡도가 됨
  • 후보의 수는 단어의 길이에 따라 지수적으로 증가하기 때문에 단어의 길이가 짧은 경우에만 하도록하고, 단어의 길이가 조금이라도 길어질 경우 동적 계획법 등을 사용해야 함

3. 관련 문제

• 모든 순열(permutation) 만들기
• 모든 조합(combination) 만들기
• 2^n 가지 경우의 수 만들기