์๊ณ ๋ฆฌ์ฆ (๋ฏธ์์ฑ) - ๋ธ๋ฃจํธ ํฌ์ค(Brute Force) - ์์ด(permutation)
- -
* ๋ธ๋ฃจํธ ํฌ์ค (Brute Force)
- ๋ฌด์ฐจ๋ณ ๋์ ํ์ฌ ์ต์ง๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ค๋ ๋ป์ด๋ค. ์ฆ, ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๋ค ํ์ํ์ฌ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
- ex ) ๋ค์๋ฆฌ ๋น๋ฐ๋ฒํธ์ ์๋ฌผ์ ๋ 0000~9999๋ฅผ ์ ๋ถ ๋์ ํด๋ณด๋ฉด ํ๋ฆฐ๋ค. (๊ฒฝ์ฐ์ ์๋ 10,000)
*๋ธ๋ฃจํธ ํฌ์ค ์๊ณ ๋ฆฌ์ฆ ์ค๊ณ
- ๋ฌธ์ ์ ๊ฐ๋ฅํ ๊ฒฝ์ฐ๋ฅผ ๊ณ์ฐํด๋ณธ๋ค. (์ง์ ์์ผ๋ก ๊ณ์ฐ, ์ผ๋ฐ์ ์ผ๋ก 100๋ง์ด ๋์ด๊ฐ๋ ๊ฒฝ์ฐ์ ์๋ผ๋ฉด, ๋ธ๋ฃจํธํฌ์ค๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์๋ค.)
- ๊ฐ๋ฅํ ๋ชจ๋ ๋ฐฉ๋ฒ์ ๋ง๋ค์ด ์ฝ๋ฉํ๋ค. (for๋ฌธ, ์์ด์ฌ์ฉ, ์ฌ๊ทํธ์ถ, ๋นํธ๋ง์คํฌ ๋ฑ์ด ์๋ค.)
- ๊ฐ๊ฐ์ ๋ฐฉ๋ฒ์ ํตํด ๋ต์ ๊ตฌํ๋ค.
- ์๊ฐ ๋ณต์ก๋๋ ๋๋ถ๋ถ 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ํ์๋, ์ฌ์ ์์ผ๋ก ์ ๋ ฌํ๋ ๊ท์น์ ์ด์ฉํ์ฌ, ๋ค์ ์์ด๊ณผ ์ด์ ์์ด์ ์ฐพ์ ์ ์๋ค.
- A[k-1] < A[k] ๋ฅผ ๋ง์กฑํ๋ ๊ฐ์ฅ ํฐ k๋ฅผ ์ฐพ๋๋ค.
- j >= k ์ A[j] > A[k-1]๋ฅผ ๋ง์กฑํ๋ ๊ฐ์ฅ ํฐ J๋ฅผ ์ฐพ๋๋ค.
- A[k-1] ๊ณผ A[j]๋ฅผ ๋ฐ๊พผ๋ค.
- 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://www.acmicpc.net/problem/2309 2309๋ฒ: ์ผ๊ณฑ ๋์์ด ์ํ ๊ฐ์ ์ค์ ๊ฑธ์ณ ๋์์ด๋ค์ ํค๊ฐ ์ฃผ์ด์ง๋ค. ์ฃผ์ด์ง๋ ํค๋ 100์ ๋์ง ์๋ ์์ฐ์์ด๋ฉฐ, ์ํ ๋์์ด์ ํค๋ ๋ชจ๋ ๋ค๋ฅด๋ฉฐ, ๊ฐ๋ฅํ ์ ..
infinitt.tistory.com
https://infinitt.tistory.com/242
๋ ์ง ๊ณ์ฐ : ๋์ด๋ ์ค๋ฒ 5 (solve.ac๊ธฐ์ค)
๋ฐฑ์ค (boj) ํ์ด์ฌ - 1476 : ๋ ์ง ๊ณ์ฐ
๋ฌธ์ ๋งํฌ : https://www.acmicpc.net/problem/1476 1476๋ฒ: ๋ ์ง ๊ณ์ฐ ์ค๊ท๊ฐ ์ฌ๋ ๋๋ผ๋ ์ฐ๋ฆฌ๊ฐ ์ฌ์ฉํ๋ ์ฐ๋์ ๋ค๋ฅธ ๋ฐฉ์์ ์ด์ฉํ๋ค. ์ค๊ท๊ฐ ์ฌ๋ ๋๋ผ์์๋ ์ 3๊ฐ๋ฅผ ์ด์ฉํด์ ์ฐ๋๋ฅผ ๋ํ๋ธ๋ค. ๊ฐ๊ฐ์ ์..
infinitt.tistory.com
https://infinitt.tistory.com/245
ํ ํธ๋ก๋ฏธ๋ ธ : ๋์ด๋ ๊ณจ๋5 (solve.ac๊ธฐ์ค)
๋ฐฑ์ค (boj) ํ์ด์ฌ - 14500 : ํ ํธ๋ก๋ฏธ๋ ธ
๋ฌธ์ ๋งํฌ : https://www.acmicpc.net/problem/14500 14500๋ฒ: ํ ํธ๋ก๋ฏธ๋ ธ ํด๋ฆฌ์ค๋ฏธ๋ ธ๋ ํฌ๊ธฐ๊ฐ 1×1์ธ ์ ์ฌ๊ฐํ์ ์ฌ๋ฌ ๊ฐ ์ด์ด์ ๋ถ์ธ ๋ํ์ด๋ฉฐ, ๋ค์๊ณผ ๊ฐ์ ์กฐ๊ฑด์ ๋ง์กฑํด์ผ ํ๋ค. ์ ์ฌ๊ฐํ์ ์๋ก ๊ฒน์น..
infinitt.tistory.com
https://www.acmicpc.net/problem/9095
1, 2, 3 ๋ํ๊ธฐ : ๋์ด๋ ์ค๋ฒ3 (solve.ac๊ธฐ์ค)
9095๋ฒ: 1, 2, 3 ๋ํ๊ธฐ
๋ฌธ์ ์ ์ 4๋ฅผ 1, 2, 3์ ํฉ์ผ๋ก ๋ํ๋ด๋ ๋ฐฉ๋ฒ์ ์ด 7๊ฐ์ง๊ฐ ์๋ค. ํฉ์ ๋ํ๋ผ ๋๋ ์๋ฅผ 1๊ฐ ์ด์ ์ฌ์ฉํด์ผ ํ๋ค. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 ์ ์ n์ด ์ฃผ์ด์ก์ ๋, n์ 1, 2, 3์ ํฉ์ผ๋ก ๋ํ๋ด๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ T๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค๋ ํ ์ค๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , ์ ์ n์ด ์ฃผ์ด์ง๋ค. n์ ์์์ด๋ฉฐ 11๋ณด๋ค ์๋ค. ์ถ๋ ฅ ๊ฐ
www.acmicpc.net
https://www.acmicpc.net/problem/10972
10972๋ฒ: ๋ค์ ์์ด
์ฒซ์งธ ์ค์ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง ์์ด์ ๋ค์์ ์ค๋ ์์ด์ ์ถ๋ ฅํ๋ค. ๋ง์ฝ, ์ฌ์ ์์ผ๋ก ๋ง์ง๋ง์ ์ค๋ ์์ด์ธ ๊ฒฝ์ฐ์๋ -1์ ์ถ๋ ฅํ๋ค.
www.acmicpc.net
https://www.acmicpc.net/problem/10973
10973๋ฒ: ์ด์ ์์ด
์ฒซ์งธ ์ค์ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง ์์ด์ ์ด์ ์ ์ค๋ ์์ด์ ์ถ๋ ฅํ๋ค. ๋ง์ฝ, ์ฌ์ ์์ผ๋ก ๊ฐ์ฅ ์ฒ์์ ์ค๋ ์์ด์ธ ๊ฒฝ์ฐ์๋ -1์ ์ถ๋ ฅํ๋ค.
www.acmicpc.net
https://www.acmicpc.net/problem/10974
10974๋ฒ: ๋ชจ๋ ์์ด
N์ด ์ฃผ์ด์ก์ ๋, 1๋ถํฐ N๊น์ง์ ์๋ก ์ด๋ฃจ์ด์ง ์์ด์ ์ฌ์ ์์ผ๋ก ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
www.acmicpc.net
https://www.acmicpc.net/problem/10819
10819๋ฒ: ์ฐจ์ด๋ฅผ ์ต๋๋ก
์ฒซ์งธ ์ค์ N (3 ≤ N ≤ 8)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ ๋ฐฐ์ด A์ ๋ค์ด์๋ ์ ์๊ฐ ์ฃผ์ด์ง๋ค. ๋ฐฐ์ด์ ๋ค์ด์๋ ์ ์๋ -100๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 100๋ณด๋ค ์๊ฑฐ๋ ๊ฐ๋ค.
www.acmicpc.net
'๐งฎ PS' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๋ฐฑ์ค (boj) ํ์ด์ฌ - 1476 : ๋ ์ง ๊ณ์ฐ (0) | 2020.04.19 |
---|---|
๋ฐฑ์ค (boj) ํ์ด์ฌ , C++ - 2309 : ์ผ๊ณฑ ๋์์ด (1) | 2020.04.19 |
๋ฐฑ์ค (boj) ํ์ด์ฌ - 1436 : ์ํ๊ฐ๋ ์ (2) | 2020.04.18 |
๋ฐฑ์ค (boj) ํ์ด์ฌ - 6588๋ฒ : ๊ณจ๋๋ฐํ์ ์ถ์ธก (0) | 2020.04.18 |
๋ฐฑ์ค (boj) ํ์ด์ฌ - 2960๋ฒ : ์๋ผํ ์คํ ๋ค์ค์ ์ฒด (0) | 2020.04.18 |
์์คํ ๊ณต๊ฐ ๊ฐ์ฌํฉ๋๋ค