[Python] 완전탐색 Brute Force

초보자를 위해 작성된 글입니다. 코드레벨의 설명을 매우 자세하게 포함하고 있습니다.

완전 탐색

완전 탐색 (Brute Force)란 모든 경우를 탐색하여 문제의 정답을 구하는 방법입니다.

기본적으로 우리가 IF - Else를 통해 모든 분기를 처리한다면 이것도 완전탐색이라고 볼 수 있습니다.

완전 탐색은 특정 알고리즘이라기 보다는

컴퓨터가 매우 빠른 연산력을 가지고 있다는 것을 바탕으로한 문제를 해결하는 하나의 방법론입니다.

 

IF - Else

조건에 대한 모든 경우에 대한 분기가 있다면 완전탐색으로 볼 수 있습니다.

그러나, 의외로 개발을 하다보면 조건을 누락하는 경우가 많습니다.

a = 100
current = 1
visit = [False, True]
if visit[current] and a > 0:
	# logic 1
elif not visit[current] and a < 0:
	# logic 2

visit[current]	a
true	> 0
false	<= 0
true	<= 0
false	> 0

위의 코드의 경우만 해도 아래 표의 2부분에 대한 누락이 있습니다.

완전 탐색을 수행해야 할 때, 조건의 누락이 없도록 주의해야 합니다.

 

Permutation

순서가 있는 나열 방법입니다.

https://namu.wiki/w/%EC%88%9C%EC%97%B4

수학적인 식은 중등/고교과정에서 소개되고 있으며 위와 같습니다.

 

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

순열로 유명한 문항인 N과 M을 한번 풀어봅시다.

N개중 중복없이 M개의 숫자로 수열을 구성하는 문항입니다.

기본적으로 이러한 문항을 푸는 방법은 2가지 입니다.

1. 언어에서 제공하는 함수 활용
2. 직접 구현

언어 제공 함수 활용

import sys
from itertools import permutations

input = sys.stdin.readline
n, m = map(int, input().split())
nums = list(map(str, range(1, n + 1)))
print('\n'.join(list(map(' '.join, permutations(nums, m)))))

쉬운 코드이지만 한줄한줄 해석해 보도록 하겠습니다.

n, m = map(int, input().split())

input으로 들어온 String을 잘게 쪼개어 list로 생성합니다.

list의 각 원소에 int casting을 적용합니다.

nums = list(map(str, range(1, n + 1)))

map(str, range(1, n + 1))

1 ~ n 까지의 숫자를 갖는 이터러블 객체에 str casting을 적용합니다.

list(map(str, range(1, n + 1)))

해당 이터러블 객체를 리스트로 반환합니다.

https://docs.python.org/ko/3.10/tutorial/controlflow.html

4. 기타 제어 흐름 도구 — Python 3.10.1 문서

에서 이터러블을 반환하는 함수와 이터러블을 인자로 받는 함수들을 조금 더 공부해 보시면 좋습니다. (시간이 되신다면, 왼쪽의 매우 유명한 레퍼런스를 통해 제너레이터까지 배워봅시다! https://nvie.com/posts/iterators-vs-generators/)

'\n'.join(list(map(' '.join, permutations(nums, m))))

그 뒤 itertools의 permutation 함수를 사용합니다.

첫 번째 인자로는 선택할 수 있는 전체값을 넘기고, 두 번째 인자로는 원하는 수열의 원소 개수를 넘깁니다.

역시 permutations 함수는 iterable 객체를 반환합니다.

>>> permutations(nums, m)
<itertools.permutations object at 0x104c4e700>
>>> list(permutations(nums, m))
[('1', '2'), ('1', '3'), ('1', '4'), ('2', '1'), ('2', '3'), ('2', '4'), ('3', '1'), ('3', '2'), ('3', '4'), ('4', '1'), ('4', '2'), ('4', '3')]

출력해보면 위와 같이 나옵니다.

Iterable객체를 list로 반환하면 출력값과 같이 들어 있는 것을 볼 수 있습니다.

우리가 원하는 결과는 

Answer

위와 같은 결과이므로

리스트의 각 원소를 우선적으로

['1 2', '1 3', '1 4', '2 1', '2 3', '2 4', '3 1', '3 2', '3 4', '4 1', '4 2', '4 3']

와 같이 만들어야 합니다.

정리하자면, ('1', '2') 를 '1 2' 로 만들기 위해서 join 함수를 적용합니다. (join 함수를 모든 원소에 적용)

map(' '.join, permutations(nums, m))

 

map함수는 iterable객체를 반환할 뿐 아직은 list와 같은 형태가 아닙니다.

list(map(' '.join, permutations(nums, m)))

리스트로 변환합니다.

여기까지 진행하면

['1 2', '1 3', '1 4', '2 1', '2 3', '2 4', '3 1', '3 2', '3 4', '4 1', '4 2', '4 3']

를 보실 수 있습니다.

이제, 이 출력본을 다시 개행문자로 연결하여 최종적으로 원하는 출력형태를 얻어봅니다.

'\n'.join(list(map(' '.join, permutations(nums, m))))

각 원소를 개행문자로 연결하면,

드디어 원하던 최종 결과인

>>> '\n'.join(list(map(' '.join, permutations(nums, m))))
'1 2\n1 3\n1 4\n2 1\n2 3\n2 4\n3 1\n3 2\n3 4\n4 1\n4 2\n4 3'

를 얻습니다.

 

직접 구현

import sys

input = sys.stdin.readline

stack = []


def permu():
    if len(stack) == m:
        print(*stack)

    for i in range(1, n + 1):
        if vis[i]:
            continue
        vis[i] = True
        stack.append(i)
        permu()
        stack.pop()
        vis[i] = False


n, m = map(int, input().split())
vis = [False] * (n + 1)
permu()

워낙 기초가 되는 문항인 만큼 직접 구현도 한 번은 반드시 해 볼 필요가 있습니다.

이것도 코드레벨의 자세한 설명을 첨부할 예정입니다. 추가 설명은 작성중입니다~