[백준 10974번] 완전 탐색 기법

 

 

 

📍완전 탐색 기법이란?

: (컴퓨터의 계산을 이용하여) 가능한 모든 경우의 수를 확인해서 정답을 찾는 방법이다.

 

📍언제 사용하는가?

: 시간이 많이 들기 때문에 탐색 범위가 적을 때 사용한다.

 

 

📍완전 탐색을 이용하기 위해서 사용되는 5가지 알고리즘

◾ Brute-Force

◾ 비트마스크

◾ 재귀 함수

◾ 순열

◾ BFS/ DFS

 

 

📍각 알고리즘에 대해 살펴보자.

1⃣ Brute-Force

: 단순하게 for, if 문으로 모든 경우의 수를 찾는다.

 

2⃣ 비트마스크

: 2진수 표현 기법을 사용한다. (AND, OR, XOR, SHIFT, NOT)

 

3⃣ 재귀 함수

: 함수 내에서 자기 자신을 다시 호출한다.

 

4⃣ 순열

: 서로 다른 n개의 원소에서 r개의 중복을 허용하지 않고 순서대로 나열한다.

ex) [1,2,3] → [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

 

5⃣ BFS/ DFS

 

 

 

 

 

 

쉬운 완전 탐색 문제부터 풀어보자.

 

[백준 10974번 - 모든 순열]

 

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

10974번: 모든 순열

 

 

(정답 - 다른 정답 참고)

import itertools
n=int(input())
arr=[i for i in range(1,n+1)]

for nums in list(itertools.permutations(arr)):
    for n in nums:
        print(n,end=' ')
    print()

 

 

 

 

<공부>

 

◾ itertools 라이브러리: 효율적인 반복을 위한 함수

🔸 itertools.permutations(p,r): 모든 수의 조합 = 순열

🔸 itertools.combinations(p,r): 순서를 고려하지 않는 조합

 

 

(순열)

◾ permutations(p) : p에 존재하는 모든 수의 조합 (=순열)

◾ permutations(p,r) : (p에 존재하는) r개로 이루어진 모든 수의 조합 (=순열)

import itertools
arr=[1,2,3]

print(list(itertools.permutations(arr))) 
#[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

print(list(itertools.permutations(arr,2))) 
#[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

 

(조합)

◾ combinations(p,r) : (p에 존재하는) r개로 이루어진 순서를 고려하지 않는 조합

*r 값을 반드시 정해줘야 한다.

* 조합에서는 (1,2,3), (2,1,3), (3,1,2) 모두 동일하다.

import itertools
arr=[1,2,3]
print(list(itertools.combinations(arr,3))) # [(1, 2, 3)]
print(list(itertools.combinations(arr,2))) # [(1, 2), (1, 3), (2, 3)]

 

 

더 알아보고 싶으면 아래 페이지를 참조하자.

https://docs.python.org/ko/3/library/itertools.html

itertools — 효율적인 루핑을 위한 이터레이터를 만드는 함수 — Python 3.9.5 문서

 

 

◾ 리스트 생성할 때, 아래와 같이 간단하게 표현할 수 있다. 긴 for문 생성하는 버릇 고치기!

arr=[i for i in range(1,n+1)]