알고리즘 (미작성) - 브루트 포스(Brute Force) - 순열(permutation)

* 브루트 포스 (Brute Force)

 

• 무차별 대입하여 억지로 문제를 해결한다는 뜻이다. 즉, 모든 경우의 수를 다 탐색하여 문제를 해결하는 알고리즘이다.
• ex ) 네자리 비밀번호의 자물쇠는 0000~9999를 전부 대입해보면 풀린다. (경우의 수는 10,000)

 

 

 

*브루트 포스 알고리즘 설계

1. 문제의 가능한 경우를 계산해본다.  (직접 손으로 계산, 일반적으로 100만이 넘어가는 경우의 수라면, 브루트포스로 문제를 해결할 수 없다.)
2. 가능한 모든 방법을 만들어 코딩한다.  (for문, 순열사용, 재귀호출, 비트마스크 등이 있다.)
3. 각각의 방법을 통해 답을 구한다.
4. 시간 복잡도는 대부분 O(경우의 수 * 방법 1가지의 소요시간)

 

 

*브루트 포스 구현

 

*N중 for문

 

• N개 중에 M개를 선택해야 하는 경우에 자주 사용된다.
• 재귀 함수, 비트마스크 등이 더 짧고 보기 쉬운 코드이기 때문에 자주 사용되지는 않는다.

 

 

 

* 순열 (Permutation)

• 1~ N 까지의 수로 이루어진 수열
• 전체 길이는 항상 N이 된다. 그리고 중복(겹치는 수)이 없다.
• 순서

크기가 N인 순열은 총 N! (factorial)개 존재한다.

 

* Python - itertools.permutations( n )

python에서 a = [a,b,c]의 순열을 구할때

from itertools import permutations
A = ['a','b','c']
A_p =list( permutations(A) )
print(A_p)

>>>>>>>>> [('a', 'b', 'c'), ('a', 'c', 'b'),
        ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

 

 

* 다음 순열 (next permutation)

순열을 사전순으로 sort했을때, 사전순으로 정렬하는 규칙을 이용하여, 다음 순열과 이전 순열을 찾을 수 있다.

1. A[k-1] < A[k] 를 만족하는 가장 큰 k를 찾는다. 
2. j >= k 와 A[j] > A[k-1]를 만족하는 가장 큰 J를 찾는다.
3. A[k-1] 과 A[j]를 바꾼다.
4. A[k]부터 순열을 뒤집는다.

 

1~5까지의 순열을 예로들어 보자면 A = [ 1 2 3 4 5 ] 를 사전순으로 나열했을때

첫번째 순열 : [ 1 2 3 4 5 ] 로 시작하여, 

............

.............

.............       몇번의 과정을 거친 뒤, 앞의 세자리가 3 1 4 일때,

[ 3 1 4 2 5 ]  다음으로 큰수는 2와 5중에서 골라야한다.

[ 3 1 4 5 2 ]  다음은 3 1 뒤의 4가 바뀔차례이다. 이때 3 1 4 를 제외한 수중에 4보다 큰수인 5와 4를 swap하게된다.

[ 3 1 5 2 4 ] 

n = int(input())
arr = list(map(int,input().split()))

def next_permutation(a):

    
    n = len(a) - 1   # n = 2가 된다.
    i = n            # i = 2
    while i > 0 and a[i-1] >= a[i]: 
    # 즉, 사전순으로 마지막 순서일때가 내림차순인데, 그것을 확인
        i -= 1
    if i == 0: # 인덱스 0까지, 내림차순이라면 마지막 순서의 수열 ex) 3 2 1
        return False #False 리턴

    j = n 
    while a[i-1] >= a[j]: # 오른쪽에 있으면서 a[i-1]보다 큰 수
        j -= 1
    a[i-1], a[j] = a[j], a[i-1] # SWAP
    j = n

    while i < j:
        a[i], a[j] = a[j], a[i] # a[i]부터 순열 뒤집기
        i += 1
        j -= 1
    return True

if next_permutation(arr)  : 
    print(*arr)
else : 
    print(-1)

 

 

 

 

 

 

 

---

* 관련 문제

 

https://infinitt.tistory.com/241

일곱 난쟁이 : 난이도 브론즈 2(solve.ac 기준)

백준 (boj) 파이썬 - 2309 : 일곱 난쟁이

 

 

https://infinitt.tistory.com/242

날짜 계산 : 난이도 실버 5 (solve.ac기준)

백준 (boj) 파이썬 - 1476 : 날짜 계산

 

https://infinitt.tistory.com/245

테트로미노 : 난이도 골드5 (solve.ac기준)

백준 (boj) 파이썬 - 14500 : 테트로미노

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

1, 2, 3 더하기 : 난이도 실버3 (solve.ac기준)

9095번: 1, 2, 3 더하기

 

---

 

---

 

---

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

10972번: 다음 순열

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

10973번: 이전 순열

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

10974번: 모든 순열

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

10819번: 차이를 최대로