Brute Force

개념

• 정답을 무조건 구하는 치트키
• 문제를 해결하기 위해 가능한 경우의 수를 모두 탐색
• 특히 backtracking, 재귀 함수를 활용해야 하는 문제
• 모든 코딩 테스트에서, 부분 점수라도 얻기 위해서 기본적으로 접근할 수 있어야 함
• 일반적으로 시간복잡도가 높은 편

 

종류 (문제 유형)

• N개 중에서
  • 중복을 허용하면서
  • 중복을 허용하지 않고
• M개를
  • 순서에 따라 나열하라
  • 골라라

 

N개 중에서 중복을 허용하면서 M개를 순서에 따라 나열하라

BOJ 15651 - N과 M (3)

static StringBuilder sb = new StringBuilder();
static int N, M;
static int[] selected;

static void recursive(int k) {
	if (k == M + 1) {
    	for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
        sb.append('\n');
    } else {
    	for (int candidate = 1; candidate <= N; candidate++) {
        	selected[k] = candidate;
            recursive(k + 1);
            selected[k] = 0;
        }
    }
}

public static void main(String[] args) {
	recursive(1);
    System.out.println(sb.toString());
}

※ 지면을 아끼기 위해 import하는 부분이나, input 값들을 받아오는 로직은 생략했습니다. 😅

• 난이도 : 2
• 시간복잡도 : O(Nⁿ) = 7⁷ = 약 82만
• 공간복잡도 : O(M)
• if문은 M개를 전부 골랐을 때 결과값을 모아주는 연산
• else문은 M개가 아직 안 모였을 때 k번째부터 M번째 원소를 조건에 맞게 고르는 모든 방법 시도

 

N개 중에서 중복을 허용하지 않고 M개를 순서에 따라 나열하라

BOJ 15649 - N과 M (1)

static void recursive(int k) {
	if (k == M + 1) {
    	for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
        sb.append('\n');
    } else {
    	for (int candidate = 1; candidate <= N; candidate++) {
        	if (used[candidate] == 1) continue;
            selected[k] = candidate;
            used[candidate] = 1;
            recursive(k + 1);
            selected[k] = 0;
            used[candidate] = 0;
        }
    }
}

※ 뭔가 상당히 생략되었는데・・・ 😅

• 난이도 : 2
• 시간복잡도 : O(P) = O(N! / (N-M)!) = 8! / 0! = 40320
• 공간복잡도 : O(M)
• 이전 문제에서 used 라는 배열을 추가로 사용해서 어떤 숫자가 쓰였는지 여부를 기록
  • 위 코드에서는 0이면 사용 가능, 1이면 사용중

 

N개 중에서 중복을 허용하면서 M개를 골라라

BOJ 15652 - N과 M (4)

static void recursive(int k) {
	if (k == M + 1) {
    	for (int i = 1; i <= M; i++) sb.append(seleceted[i]).append(' ');
        sb.append('\n');
    } else {
    	int start = selected[k - 1];
        if (start == 0) start = 1;
        for (int candidate = start; candidate <= N; candidate++) {
        	selected[k] = candidate;
            recursive(k + 1);
            selected[k] = 0;
        }
    }
}

• 난이도 : 2
• 시간복잡도 : O(Nⁿ) = 8⁸ ≅ 약 1677만
• 공간복잡도 : O(M)
• start 라는 변수를 가능한 최소 숫자 값으로 참조

❖ 비내림차순이란?

: (2,3), (3,2) 둘 다 가능하지 않고 (2,3) 하나로만 가능

 

N개 중에서 중복을 허용하지 않고 M개를 골라라

BOJ 15650 - N과 M (2)

static void recursive(int k) {
	if (k == M + 1) {
    	for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
        sb.append('\n');
    } else {
    	for (int candidate = selected[k - 1] + 1; candidate <= N; candidate++) {
        	selected[k] = candidate;
            recursive(k + 1);
            selected[k] = 0;
        }
    }
}

• 난이도 : 2
• 시간복잡도 : O(C) = O(N! / M!(N-M)!) = 8! / 4! * 4! = 70
• 공간복잡도 : O(M)

 

종류별 복잡도 정리

중복 여부	순서 여부	시간복잡도	공간복잡도
O	O	O(Nⁿ)	O(M)
X	O	O(P) = O(N! / (N-M)!)	O(M)
O	X	O(Nⁿ) 보다 작음	O(M)
X	X	O(C) = O(N! / M!(N-M)!)	O(M)

 

응용 문제

BOJ 9663 - N-Queen

static boolean attackable(int r1, int c1, int r2, int c2) {
	if (c1 == c2) return true;
    if (r1 - c1 == r2 - c2) return true;
    if (r1 + c1 == r2 + c2) return true;
    return false;
}

static void recursive(int row) {
	if (row == N + 1) answer++;
    else {
    	for (int c = 1; c <= N; c++) {
        	boolean possible = true;
            for (int i = 1; i <= row - 1; i++) {
            	if (attackable(row, c, i, col[i])) {
                	possible = false;
                    break;
                }
            }
            if (possible) {
            	col[row] = c;
                recursive(row + 1);
                col[row] = 0;
            }
        }
    }
}

public static void main(String[] args) {
	recursive(1);
    System.out.println(answer);
}

• 난이도 : 2
• N개 중에서 중복을 허용하면서 순서대로 나열하는 문제 = O(Nⁿ)
• row + col 값이 서로 같으면 같은 우상향 대각선에 있다는 뜻
• row - col 값이 서로 같으면 같은 좌상향 대각선에 있다는 뜻

 

⭐️ backtracking의 핵심은 재귀 함수를 올바르게 정의하는 것!!!