brute(무식한) force(힘)
컴퓨터의 엄청난 연산 속도를 이용해 무식하게 문제를 푼다.
문제의 정답의 범위를 a~b로 정해놓고, 이 안에 답이 존재할 때
a~b에 속하는 모든 값을 전부 시도하며 정답을 찾는다.
알고리즘에 대한 지식 없이 문제를 풀어본 적이 없다면 지금까지 브루트 포스로 문제를 풀었을 가능성이 높다.
완전 탐색이라고도 한다.
아래 문제를 풀어보자.
https://www.acmicpc.net/problem/2798
n, m = map(int,input().split())
cards = [i for i in map(int, input().split())]
maxsum = 0
for i in range(0, n):
for j in range(i+1, n):
for k in range(j+1,n):
if m>=cards[i]+cards[j]+cards[k]>maxsum:
maxsum = cards[i]+cards[j]+cards[k]
print(maxsum)브루투포스 문제의 특징은 모든 경우의 수를 탐색해야해 입력 데이터의 크기가 적다.
문제의 입력 범위가 작다면, 브루트 포스 풀이를 생각하고 시간 복잡도를 생각해보자.
backtracking
완전 탐색 알고리즘의 일종이다. 중간에 답이 안되는 것을 깨달으면 멈추고 다시 돌아간다. 시간을 줄일 수 있다.
문제의 해답이 (a, b, c.. 이렇게 조합의 형태로 되어있어 모든 조합을 다 시도해보려는 경우
위 블랙잭 문제의 해답은 3장을 무조건 더하는데, 이는 비효율적이라는 것을 알 수 있다.
만약 1장을 뽑았는데 그 수가 이미 m 이상이거나, 2장을 뽑았는데 이미 m 이상일 수도 있다.
아래는 개선된 코드이다.
n, m = map(int,input().split())
cards = [i for i in map(int, input().split())]
maxsum = 0
for i in range(0, n):
if cards[i]>=m+1:#만약 현재카드가 5인데 6을 넘지 말아야 한다면 안된다. 두 장의 카드는 최소 1이기 떄문에. 지금 생각난건데 만약 중복카드가 없다면 그냥 m+2로 해도 될듯하네요. 1두장이 남았을 가능성은 없으니
continue#아래 코드 실행하지 않고 건너 뛴다.
for j in range(i+1, n):
if cards[i]+cards[j]>=m:
continue
for k in range(j+1,n):
if m>=cards[i]+cards[j]+cards[k]>maxsum:
maxsum = cards[i]+cards[j]+cards[k]
print(maxsum)블랙잭 문제는 해답이 3개 수의 조합으로 구성되었다: 3중 반복문으로 조합을 구성
만약, 조합을 구성하는 원소의 개수가 정해져 있지 않다면: 재귀함수로 조합을 구성.
백트래킹은 재귀함수를 사용하는 경우가 많다.
아래 문제를 풀어보자.
https://www.acmicpc.net/problem/15649
idea:
M개 수열을 구성하려면 M중 반복문을 작성해야하는데,
반복문 중첩 개수를 입력에 따라 동적으로 작성하기는 힘들다.
재귀를 사용하자.
hint:
재귀 함수는 지금까지의 수열을 매개변수로 받는다.
basecase: 수열의 길이가 m이면 출력하고 현재 함수 종료.
else: 1부터 n까지 반복문을 돌며 s에 있지 않은 수를 새로 추가하고 이를 다시 재귀호출.
예를 한번 들어보자 n = 3 m = 3
그림..
n, m = map(int, input().split())
def combi(seq):
#base case
if len(seq)==m:
print(*seq)
return#현재의 함수만 종료. 전체함수를 종료하는 것이 아님.
for i in range(1, n+1):#시작 숫자가 1부터 n까지
if i not in seq:
combi(seq + (i,))#(i)라고 쓰면 튜플이 아니라 괄호로 감싼 식이로 인식.
#(i,)s는 하나의 값 i를 생성하는 표현이다.
combi(tuple())
라이브러리와 함수를 잘 안다면 아래와 같은 풀이도 가능하다.
from itertools import permutations
n, m = map(int, input().split())
numbers = list(range(1, n+1))
for c in permutations(numbers, m):
print(*c)#리스트를 공백으로 구분하여 출력permutation(순열) 외에도 product(데카르트 곱=카테시안 곱), combination(조합), combination_with_replacement(중복조합) 등이 있다.
from itertools import permutation
for p in permutation(range(1,5),3):
print(*p)
모든 순열들이 프린트된다.
for p in product(range(1,5), repeat = 3):
print(*p)
1부터 4까지의 숫자를 순서 있게 뽑는다. 중복 허용.
for p in combinations(range(1,5),3):
1부터 4까지 3개를 뽑는 조합. 순서 고려 x
for p in combinations_with_replacement(range(1,5),3):
1부터 4까지 3개를 뽑는 조합. 순서 고려x 중복 허용
다음문제도 풀어보자
N - Queen
https://www.acmicpc.net/problem/9663
모든 경우의 수를 다 해보면 n=15만 되어도 225C8.
#퀸을 한 번 배치하면 그 퀸의 가로 세로 대각에는 새로운 퀸 배치 불가.
#한 줄에 하나의 퀸을 배치해야 하는 것이 자명하다.
#퀸을 특정 가로줄에서 몇 번째 세로줄에 배치할 지 생각.
#i-1번째 줄까지 퀸을 배치한 세로줄 위치 조합이 주어지면
#i번째 줄에서 퀸을 배치할 수 있는 세로줄 위치를 찾음
#만약 현재 줄에서 모든 세로줄에 퀸을 배치하지 못한다면
#답이 될 수 없으므로 이전 단계로 되돌아가
#다른 새로운 위치 조합 시도(backtracking)
#정리하자면, 가로줄마다 하나씩 배치해야하므로
#세로줄 위치에 대한 조합을 모두 시도해보자.
#row는 현재 처리중인 행
#pos는 퀸의 위치를 기록
def n_queen(row, pos):
global answer#이제 이 함수 내에서 answer 사용 가능. 외부의 변수 접근
if row == n:
answer+=1
return
for i in range(n):
possible = True
for check_pos in pos:
if check_pos[1] ==i: #같은 열 퀸 있으면 pass
possible = False
break
if abs(check_pos[0]-row)==abs(check_pos[1]-i):#abs는 절댓값absolute. 대각선이 겹치는 경우.
#원래 퀸의x좌표와 가로줄의 차이가 원래 퀸의 y좌표와 세로줄의 차이가 같으면 안됨.
possible = False
break
if possible:
#다음 행으로 진행.현재 열을 pos에 추가
n_queen(row+1,pos+((row, i),))
#아니면 다음 for문으로 넘어간다.
n = int(input())
answer = 0
n_queen(0,tuple())
print(answer)
위는 좌표를 직접 이용한 반면 아래는 인덱스를 x좌표로 이용하였다.
def n_queen(row, pos):
global answer
if row == n:
answer += 1
return
for i in range(n):
possible = True
for r in range(row):
if pos[r] == i: # 같은 열에 퀸이 있으면 안 됨
possible = False
break
if abs(r - row) == abs(pos[r] - i): # 대각선에 퀸이 있으면 안 됨
possible = False
break
if possible:
# 다음 행으로 진행, pos에 현재 열을 추가
n_queen(row + 1, pos + [i])
n = int(input())
answer = 0
n_queen(0, [])
print(answer)
아래처럼
N – Queen 문제를 풀 때 직접 N x N 2차원 배열을 만들고 퀸을 배치할 수 있는지 여부를 True / False로 저장하여 문제를 풀 수도 있다. 이렇게 푼다면, 백트래킹을 하여 뒤로 돌아갈 때 기존에 변경했던 상태를 원래대로 되돌려 놓아야 하는 점을 유의하자.
def n_queen(row, board):
global answer
if row == n: # 모든 퀸을 배치한 경우
answer += 1
return
for i in range(n): # 현재 행(row)에서 퀸을 놓을 수 있는 열을 찾는다
# (row, i)에 퀸을 놓을 수 있는지 체크
if board[row][i] or column[i] or diagonal1[row + i] or diagonal2[row - i + (n - 1)]:
continue
# (row, i)에 퀸을 놓기
board[row][i] = True
column[i] = True
diagonal1[row + i] = True
diagonal2[row - i + (n - 1)] = True
# 다음 행으로 진행
n_queen(row + 1, board)
# 되돌리기 (백트래킹)
board[row][i] = False
column[i] = False
diagonal1[row + i] = False
diagonal2[row - i + (n - 1)] = False
n = int(input()) # 퀸의 수
answer = 0
# board, column, diagonal1, diagonal2 배열 초기화
board = [[False] * n for _ in range(n)]
column = [False] * n # 각 열에 퀸을 배치할 수 있는지 여부
diagonal1 = [False] * (2 * n - 1) # 왼쪽에서 오른쪽으로 향하는 대각선 (row + col)
diagonal2 = [False] * (2 * n - 1) # 오른쪽에서 왼쪽으로 향하는 대각선 (row - col + n-1)
n_queen(0, board)
print(answer)
다음 문제도 풀어보자
맨해튼 거리(택시거리) 문제. 참고로 우리가 쓰는 거리는 유클리드 거리다.
https://www.acmicpc.net/problem/15686
모든 도시의 칸은 빈 0칸, 치킨집2, 집1 중 하나.
도시의 크기가 작고 치킨집의 수도 적다.(최대 13개)
1. 남겨둘 치킨집을 선택하는 모든 경우의 수를 돌면서
2. 모든 집에 대해 치킨 거리를 구한다.
3. 치킨 거리의 합을 기존 정답과 비교하여 갱신
모든 집에 대해 치킨거리를 구할 때 매번 2차원 배열에서 탐색하는 것은 비효율적.
모든 집과 치킨집의 위치를 배열에 저장하자.
n, m = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(n)]
집과 치킨집의 위치(x,y)를 미리 리스트에 저장
houses = []
chickens = []
for i in range(n):
for j in range(n):
if board[i][j] ==1:
houses.append((i,j))
elif board[i][j] ==2:
houses.append((i,j))
def calculate_chicken_dist(house_pos, chicken_combi):
dist = 987654321#이걸 사용하지 않고 첫번째 값을 사용해도 된다. float('inf')를 사용해도 된다.
house_r, house_c = house_pos
for chicken_r, chicken_c in chicken_combi:
dist = min(dist, abs(chicken_r - house_r)+abs(chicken_c-house_c))
return dist
answer = 9876543221
for combi in combinations(chickens, m)
#선택한 치킨위집 위치 조합으로 모든 집에 대해 치킨 거리를 구하자
sum_chicken_dist = 0
for house_pos in houses:
chicken_dist = calculate_chicken_dist(house_pos, combi)
sum_chicken_dist += chicken_dist
answer = min(answer, sum_chicken_dist)
print(answer)