알고리즘의 존재 이유이자 최종 목적은 제한시간 안에 얼마나 효율적으로 문제를 계산해 낼 수 있으냐이다.
따라서, 모든 알고리즘 문제에서 수의 입력 범위를 확인하는 것은 중요한 일이다. 입력 범위가 충분히 작다면 굳이 어려운 방법으로 문제를 풀 필요가 없다는 뜻이된다. 컴퓨터는 1초에 1억번 정도의 연산을 해낼 정도로 계산에 최적화된 기계이다. 그렇다면 이 문제에서는 얼마만큼의 연산량이 필요할까?
문제를 읽어보면 확인할 수 있겠지만, 입력으로 주어지는 전체 판의 크기는 50 x 50이다. 여기에서 기준이 되는 매트릭스 좌측 상단의 색깔이 'W', 'B' 두가지 케이스에, 검사해야 하는 maxtrix의 크기인 8x8이다.
총 계산량은 ? 아무리 크게 잡아도 32만을 넘기 어렵다. 그렇다면 우리가 이 문제를 풀 때 복잡하게 풀어야 한다? 아니다. 그냥 전체 경우의 수를 탐색하면 되는 문제다.
Number of Operation = 50 * 50 * 2 * 64 = 320,000
BruteForce란 말을 들어본 적이 있는가? 이런 전체를 탐색하는 알고리즘 기법은 Brute Force라는 알고리즘으로 지칭한다. 맨 처음 알고리즘 문제를 접해본 이들은 Brute Force가 알고리즘도 아니라는 반응을 보이기 마련이지만, 아래 인용글에서 확인할 수 있듯이 가장 확실하고 무서운 방법이며, 컴퓨터를 가장 컴퓨터 스럽게 해결해 내는 가장 기본적인 방법이다. 유명한 알고리즘 풀이를 하는 사람중에 한명이 하는 말이 자기는 무조건 먼저 Brute Force를 적용해서 풀이방법이 맞는지 계산량이 얼마나 나오는지를 먼저 확인해 본다고 하였다. 요즘에 와서 느끼는 거지만, Brute Force는 기본 중에 기본이다. 꼭 기억해 두고 자주 익히도록 하자.
영어로 brute는 "짐승 같은, 난폭한"이라는 뜻이고, brute-force는 "난폭한 힘, 폭력"이라는 뜻이다. 오래 걸리는 데다 자원이 엄청나게 들어서 얼핏 보면 무식하다고 생각할 수도 있겠지만,
항상 정확도 100%를 보장
한다는 점에서 암호 해독법 중 가장 확실하고 무서운 방법이다. 이론적으로 가능한 모든 경우의 수를 다 검색해 보는 것이라 정확도 100%가 항상 보장되니, 암호학에서는 가장 확실한 방법으로 통용되고 있다. 무엇보다도 암호 확인 작업은 손으로 입력한 문자열의 동일 여부를 확인하는 것이기 때문에, 가능한 경우의 수를 하나씩 대입하다 보면 언젠가는 암호를 찾을 수 있게 되는 식이다. 다만 정말로 그냥 무식하게 때려 박는 건 아니고, 숫자만 섞어서 대입해 보기 한 번, 로마자만 섞어서 대입해 보기 한 번 이런 식으로 하다가 안 되면 나머지를 순차적으로 하는 식으로 특정 규칙에 따라 우선순위를 두고 하기도 한다. - 나무 위키
그럼 실제로 문제를 풀어보자. 입력 부분에서는 어떤 부분을 먼저 생각해야 할까? 어떻게 해야 Black & White를 효율적으로 표현할 수 있느냐 이다. Black & White는 이진 분류와 같이 True or False로 구분되는 개념이기 때문에 순자로 쉽게 구분할 수 있도록 0과 1로 나누어서 표현해 보도록 한다. 이후에 계산할 떄에서 variable%2를 통해서 0과 1을 체크해 나갈 수 있기 때문에 좋은 방법이라고 볼 수 있다.
def input_data():
n, m = map(int, rdln().split())
t_map = []
for i in range(n):
temp = rdln().strip()
a = []
for val in temp:
# 'W'를 1값으로, 'B'를 0으로 계산
if val == 'W':
a.append(1)
else:
a.append(0)
t_map.append(a)
return n, m, t_map
Main Brute Force 함수 부분이다.
def brute_force():
ans = 100
for i in range(n-8+1):
for j in range(m-8+1):
# 체스판 시작 위치에서의 값 'W'또는 'B'
for p in range(2):
cnt = 0
# 8행, 8열 체스판 완전 탐색
for k in range(8):
for l in range(8):
# 체스판 시작 위치에서의 값p를 기준으로
# l열, k행만큼 진행할 경우의 예상값 계산 ((p + l) + k) % 2
# 값이 맞으면 skip, 아니면 cnt에 1더해줌
if t_map[i+k][j+l] == ((p + l) + k) % 2: continue
cnt += 1
# print("cnt: " cnt)
ans = min(ans, cnt)
return ans다 틀려도 64개이기 때문에 ans의 초기값을 넉넉하게 100으로 잡아두고 i는 전체 보드의 행, j는 전체 보드의 열로 전체탐색한다. 8*8의 크기를 탐색하기 때문에, range최대 범위에서 8을 빼주는 것을 생각해 주어야 한다. p는 8*8 크기의 체스판 테스트를 시작할 때의 black or white의 기준값을 테스트하는 것으로 0 또는 1이다. 처음 풀이를 하다보면 그냥 전체 보드에 있는 수를 기준으로 하면 되는 것이 아닌가 라는 생각이 들 수도 있겠지만, 교묘하게 아래와 같은 케이스가 나오게 된다면 낭패를 보게 된다.
8 8
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBW
BruteForce는 전체 탐색이므로 조건을 줄이는 최적화를 과하게 할 필요가 없다는 것을 항상 염두에 두자. k와 l은 전체 보드에서 (i, j)로 시작되는 시작위치에서 p의 색깔로 시작하는 체크보드의 행, 열을 표현하는 것으로 모든 경우를 탐색해가면서 원래 나와야 할 값 ((p + l) + k) % 2과 보드위치에서의 값 t_map[i+k][j+l] 이 같은지 확인하고 같으면 바꿀 필요없고 다르다면 cnt를 1증가시켜서 바꿔야 할 총량을 계산하는 것이다. 여기에서 원래 나와야 할 값을 천천히 생각해 보면 아래와 같은 수식에 도달할 수 있다.
((p + l) + k) % 2
현재 위치 기준값(p)에서 열방향으로 l만큼, 행방향으로 k만큼 증가할 때의 값의 2로 나눈 나머지가 바로 흑과 백이 번갈아가면서 나오는 배열을 나타내는 값임을 확인 가능하다. (생각해 보자)
최종 코드를 첨부해 본다.
https://github.com/Koo82/Algotirhm/blob/main/%5BBRF%5DBJ_1028.py
'알고리즘 > BruteForce' 카테고리의 다른 글
| [BruteForce] 백준 28215, 대피소 (1) | 2023.10.30 |
|---|
