[Week01] ์๊ณ ๋ฆฌ์ฆ ํค์๋ - ์ ์๋ก , ๋ฐฐ์ด, ๋ฌธ์์ด, ์ฌ๊ทํจ์, ์ ๋ ฌ, ์์ ํ์, ์๊ฐ๋ณต์ก๋
์ฌ๊ทํจ์
- ์์ ๋ฌธ์ ์ ํด๊ฒฐ๋ฒ์ ์ฌ์ฉํด์ ๋ ํฐ ๋ฌธ์ ๋ฅผ ํผ๋ค
- ์ ์ฐจ์ ์งํฅ์ ์ฌ๊ณ ๋ฅผ ๋ฒ๋ฆฌ๊ณ ์ํ์ ๊ท๋ฉ๋ฐฉ์์ผ๋ก ์๊ฐํ๊ธฐ
- ์ ํ์(๋๊ฐ์ ํญ ์ฌ์ด์ ์ฑ๋ฆฝํ๋ ๊ด๊ณ)๊ณผ ์ดํญ ๊ตฌํ๊ธฐ
- loop(๋ฐ๋ณต๋ฌธ)์ recursion(์ฌ๊ท)์ ์๋ก ๋ณํ์ด ๊ฐ๋ฅํ๋ค
์ฌ๊ทํจ์๋ ์๊ธฐ์์ ์ ๋ถ๋ฅด๋ ํจ์์ด๊ธฐ ๋๋ฌธ์ ์ ์ฐจ์ ์ผ๋ก ์ฝ๋๋ฅผ ์ซ์๊ฐ๋ฉด ํท๊ฐ๋ฆด ์ ๋ฐ์ ์๋ค. ๊ท๋ฉ๋ฒ์ ์ผ๋ก ์๊ฐํ ์ ์๋ค๋ฉด ์ด์์ ์ด์ง๋ง, ํ๋ค๋ค๋ฉด ์ฒ์ ๋ถ๋ ๋ ํจ์์ ๊ทธ ์์์ ๋ถ๋ฅธ ํจ์, ๊ทธ ์์์ ๋ถ๋ฅธ ํจ์ ๋ค๋ค๋ฅธ ํ์๋ผ๊ณ ์๊ฐํ๊ณ ํจ์์ธ์์ depth๋ฅผ ์ ์ด๊ฐ๋ฉด์ ์ด๋ป๊ฒ ๋์๊ฐ๋์ง ํ๋ํ๋ ์ซ์๊ฐ๋ ๊ฒ๋ ์ดํดํ๋ ๋ฐฉ๋ฒ ์ค ํ๋์ด๋ค.
๊ตฌํ๋ฐฉ๋ฒ
1. ๋ฌธ์ ์ ์ ์๋ฅผ ์ ํํ๊ฒ ํ๊ธฐํ๋ค. (์ ์ธํ ํ๋ก๊ทธ๋๋ฐ*)2. ์ข ๋ฃ ์กฐ๊ฑด+ ์ปฌ์คํ : ํธ์ถ์ ํ๋ฆ์ ์ ์ฅํด์ ์ด๋ฒ ์ฒ๋ฆฌ๊ฐ ๋๋๋ฉด ๋์๊ฐ ๊ณณ์ ๊ธฐ์ตํ๋ ์ฅ์.
ํธ์ถ์ ํ๋ฆ์ ๋ฐ๋ผ๊ฐ์ค์์์ผํ๋ค. (์ปฌ์คํ์ด ์ด๋ป๊ฒ ์์ด๊ณ ์ค์ด๋๋ ์ง)
โ ์์ด๊ณผ ์กฐํฉ
์์ด - ์๋ก ๋ค๋ฅธ n ๊ฐ ์ค r ๊ฐ๋ฅผ ๊ณจ๋ผ ์์๋ฅผ ์ ํด ๋์ดํ๋ ๊ฐ์ง์
def permutation(arr, n):
result = []
if n == 0:
return [[]]
for i in range(len(arr)):
elem = arr[i]
for rest in permutation(arr[:i] + arr[i+1:], n - 1):
result.append([elem] + rest)
return result
print(permutation([0,1,2,3], 2))
์กฐํฉ - ์๋ก ๋ค๋ฅธ n๊ฐ ์ค r๊ฐ๋ฅผ ์ทจํ์ฌ ์กฐ๋ฅผ ๋ง๋ ๋ค.
def combination(arr, n):
result = []
if n == 0:
return [[]]
for i in range(len(arr)):
elem = arr[i]
for rest in combination(arr[i + 1:], n - 1):
result.append([elem] + rest)
return result
print(combination([0,1,2,3], 2))
โ ๋ฐฑํธ๋ํน : ํ์ฌ ์ํ์์ ๊ฐ๋ฅํ ๋ชจ๋ ํ๋ณด๊ตฐ์ ๋ฐ๋ผ ๋ค์ด๊ฐ๋ฉฐ ํ์ํ๋ ์๊ณ ๋ฆฌ์ฆ
DFS์ ์ผ์ข ์ธ ๋ฐฑํธ๋ํน, ๋ฌธ์ ์ ํ์ด ํฌ์ง์์ ๊ฒฝ์ฐ ์ฌ์ฉ๊ฐ๋ฅํ๋ค.
๋ฐฑํธ๋ํน ์ฐ์ต ๋ฌธ์ - ๋ฐฑ์ค 1569(N๊ณผ M)
import sys
x,y = map(int,sys.stdin.readline().split())
arr = [0] * y #์์ด ์กฐํฉ์ ๋ด๋ ๋ฆฌ์คํธ
isused = [False] * (x+1) #ํด๋น ์๊ฐ ์ฌ์ฉ๋๋์ง ํ์ธ - ์ธ๋ฑ์ค ๊ฐ์ด ํด๋น ์
def back(n) :
if n == y :
print(' '.join(map(str,arr)))
else :
for i in range(1,x+1) :
if isused[i] == False :
arr[n] = i
isused[i] = True
back(n+1)
isused[i] = False
back(0)
์ข ๋ ๊น๋ํ๊ฒ ํํ
์ด ๊ฒฝ์ฐ isused list๊ฐ ๋ฐ๋ก ์์ด ์ค๋ณต ๊ฐ์ ํ์ฉํ๋ ๊ฒฝ์ฐ ์ด์๊ฐ ๋ฐ์ํ ์ ์๋ค.
n,m = map(int,input().split())
arr = []
def back():
if len(arr)==m:
print(' '.join(map(str,arr)))
return
for i in range(1,n+1):
if i not in arr: #์ค๋ณต๊ฐ์ ํ์ฉํ ๊ฒฝ์ฐ ์กฐ๊ฑด๋ฌธ์ ๊ฑธ๋ฆฌ์ง์์
arr.append(i)
back()
arr.pop()
back()
์ฌ๊ทํจ์๋ ๋ค์ ๋์ค๋ ๋ค์ํ ์๊ณ ๋ฆฌ์ฆ ๋ฐฉ์์ ์ฐ์ด๊ธฐ ๋๋ฌธ์ ๊ผญ ์ตํ๋๊ธธ ๋ฐ๋๋ค...!
'SW์ฌ๊ดํ๊ต ์ ๊ธ > ๊ฐ๋ฐ์ผ์ง - TIL' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Week03] ์๊ณ ๋ฆฌ์ฆ - DFS / BFS ๋ฐฑ์ค ๋ฌธ์ (5) | 2022.04.21 |
---|---|
[Week03] ์๊ณ ๋ฆฌ์ฆ - ์ ๋์จ ํ์ธ๋ (3) | 2022.04.20 |
[Week02] ์๊ณ ๋ฆฌ์ฆ - ํ (feat. python) (2) | 2022.04.14 |
[Week02] ์๊ณ ๋ฆฌ์ฆ - ์ด๋ถํ์ (5) | 2022.04.09 |
[Week01] ์๊ณ ๋ฆฌ์ฆ - ์ ๋ ฌ01 (0) | 2022.04.09 |
๋๊ธ