파이썬 완전탐색 알고리즘
2022, Aug 08
완전탐색 I(Exhaustive Search)
무식하게 풀기(Brute-force)
모든 경우의 수를 탐색하여 문제를 해결하는 방식
- 가장 단순한 풀이 기법, 단순 조건문과 반복문을 이용해서 풀수있다.
- 복잡한 알고리즘 보다는, 아이디어를 어떻게 코드로 구현할 것인지가 중요하다.
def blackjack(n,m,cards):
max_total = 0
# 완전탐색(Brute-force)
for i in range(n-2):
for j in range(i+1, n-1):
for k in range(j+1, n):
total = cards[i] + cards[j] + cards[k]
# 현재 가장 큰 합보다는 크고, m을 넘지않아야 갱신
if max_total < total <= m:
max_total = total
# 합과 m이 같으면 더이상 탐색하는 의미가 없으므로 종료
if total == m:
return total
return max_total
델타 탐색(Delta Search)
이차원 리스트의 모든 원소를 순회하며(완전탐색) 각 지점에서 상하좌우에 위치한 다른 지점을 조회하거나 이동하는 방식
| (0,0) | (0,1) | (0,2) |
|---|---|---|
| (1,0) | (1,1) | (1,2) |
| (2,0) | (2,1) | (2,2) |
이차원 리스트의 인덱스의 조작을 통해 상하좌우 탐색을 한다. 이때 행과 열의 변량인 -1, +1을 델타값이라고 한다.
델타값을 이용해 상하좌우로 이동하기
# 1번째 방법
# 행을 x, 열을 y로 표현
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 행을 r, 열을 c로 표현
dr = [-1, 1, 0, 0]
dc = [0. 0, -1, 1]
for i in range(4): # 상하좌우
nx = x + dx[i]
ny = y = dy[i]
# 범위를 벗어나지 않으면 갱신(범위를 벗어난 값 예외처리)
if 0 <= nx < 3 and 0 <= ny < 3:
x = nx
y = ny
# 2번째 방법
delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for d in delta:
nx = x + dx[0]
ny = y + dy[1]
# 범위를 벗어나지 않으면 갱신(범위를 벗어난 값 예외처리)
if 0 <= nx < 3 and 0 <= ny < 3:
x = nx
y = ny
# 8방위
dx = [-1, 1, 0, 0, -1, 1, -1, 1]
dy = [0, 0, -1, 1, -1, -1, 1, 1]