2-1. 브루트 포스(주먹구구식), N중 for문

Brute Force

• 브루트 포스는 모든 경우의 수를 계산해보는 방법이다.
• 단, 경우의 수를 계산하는 데 걸리는 시간이 주어진 문제의 시간 제한을 넘지 않아야 한다.

Brute Force 방식으로 문제를 풀 때

• 가능한 경우의 수를 모두 계산해본다.
  • 직접 계산을 통해서 구하며, 대부분 손으로 계산해볼 수 있다.
• 모든 방법을 찾는다. 대표적으로는 직접 계산하는 방법, 반복문 사용, 순열 사용, 재귀 호출, 비트마스크를 사용하여 직접 계산하는 방법이 있다.
• 각각의 방법을 이용해 답을 구해본다. 그리고 시간 제한을 초과하지 않는 방법을 찾는다.

Brute Force 문제의 시간복잡도는 보통 O(경우의 수*방법 1개를 시도해보는데 걸리는 시간 복잡도)가 된다.

일곱 난쟁이

• 일곱 난쟁이, 백준 온라인 저지
• 아홉명의 난쟁이 중, 키의 합이 100인 7명의 난쟁이를 찾는 문제
• 9명 중에서 7명을 고르는 것은 9명 중에서 2명을 제외하는 것과 같다.
• 난쟁이의 수를 N이라고 했을 때 두 명을 고르는 시간 복잡도는 O(N^2)이며, 나머지 7명의 키를 합산하는 데 걸리는 시간 복잡도는 O(N)이다. 따라서 이 문제를 Brute Force 방법으로 풀어내는 데 걸리는 시간복잡도는 O(N^3)이 된다.

날짜 계산

• 날짜 계산, 백준 온라인 저지
• 1<=E<=15, 1<=S<=28, 1<=M<=19를 만족하는 E, S, M이 주어졌을 때, 몇 년인지 구하는 문제
• E의 범위는 115, S의 범위는 128, M의 범위는 1~19이다. 따라서 ESM연도로 표현할 수 있는 값은 최대 7980년이다. 이에 해당하는 모든 경우를 계산해보면 된다.
• 모듈러 연산을 이용해서 코드를 간결하게 구현할 수 있다.
• 이 문제는 중국인의 나머지 정리로도 풀 수 있지만, 수학적 배경지식을 필요로 한다.

테트로미노

• 테트로미노, 백준 온라인 저지
• NxM개의 종이 위에 테트로미노를 하나 놓아서, 테트로미노가 놓여있는 칸에 쓰인 숫자의 합이 최대가 되게끔 만드는 문제
• 테트로미노는 총 19가지가 있고, 하나의 테트로미노당 놓을 수 있는 방법의 갯수는 약 O(NM)가지이다. 경우의 수가 많지 않으므로, 각각의 테트로미노를 모든 칸에 놓아보는 방법으로 최대값을 구할 수 있다.

---

N중 for문

• N개 중에 일부를 선택하는 경우에 많이 사용하며, 재귀호출이나 비트마스크를 사용하여 간결하게 코드를 작성할 수 있기 때문에 사용할 일은 많지 않다.

1, 2, 3 더하기

• 1, 2, 3 더하기, 백준 온라인 저지
• 정수 N이 주어졌을 때, 이 정수를 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제
• N은 10보다 작거나 같기 때문에 최대 10개 이하로 표현이 가능하다. 따라서, 10중 for문을 사용하면 구할 수 있다.
• 10중 for문을 사용하여 코드를 구현하게되면 시간복잡도는 O(3^N)이라는 결과가 나오게 되는데, 재귀를 이용해서 코드를 간결하게 표현하더라도 시간복잡도는 줄어들지 않는다. 코드가 복잡하기 때문에 실수할 가능성이 높기는 하지만, 시간복잡도가 변하지 않는다는 점에서 10중 for문도 좋은 알고리즘이라고 볼 수 있다.