์๊ณ ๋ฆฌ์ฆ ์คํฐ๋ํ๋ฉด์ ์ฌ๊ท์ ๋ํด ์ ์ดํดํ๊ณ ์ฐ์ง ๋ชปํ๋ ๊ฒฝํ์ด ์๋ค.
ํผ๋ณด๋์น๋ ํฉํ ๋ฆฌ์ผ ๋ฌธ์ ์ ๋๋ ๊ด์ฐฎ์๋ฐ, ์ดํด๋๊ฐ ์กฐ๊ธ ๋ถ์กฑํ์ด์ ๊ทธ ์ด์์ ์ฒดํ๋์ง ์์, ์ฝ๊ฒ ์ฌ๊ท๋ฅผ ๋ ์ฌ๋ ค ์ฌ์ฉํ์ง ๋ชปํ์๋ค.
์ด๋ฒ์ ์ฝํ ๋ฅผ ์ค๋นํ๋ฉด์, ์ฌ๋ฌ ๋ฌธ์ ๋ฅผ ํ๊ธฐ๋ณด๋จ ๋ถ์กฑํ๋ ๊ธฐ๋ณธ ๊ฐ๋ ์ ๋ํด ๋ค์ ์ดํดํ๊ณ ๋์ด๊ฐ๋ณด์!๋ผ๋ ๋ง์์ผ๋ก ์์ด๊ณผ ์กฐํฉ์ ๋ค์ฌ๋ค๋ณด์๊ณ , ์์ด๊ณผ ์กฐํฉ์ ์์๊ฐ๋ฉด์ ์ฌ๊ท์ ๋ํด์๋ ์์ฐ์ค๋ ์ฒดํํ ์ ์์๋ค-!!!
์์ด (permutation)
์์ด์ด๋ ์๋ก ๋ค๋ฅธ n๊ฐ์ ์์์์ r๊ฐ๋ฅผ ์ค๋ณต ์์ด ์์๋ฅผ ๊ณ ๋ คํ์ฌ ์ ํํ๊ฑฐ๋ ๋์ดํ๋ ๊ฒ์ ์๋ฏธํฉ๋๋ค.(๋จ, 0<r≤n์ผ ๋)
๊ณ ๋ฑํ๊ต ์ํ์๊ฐ์ ๋ฐฐ์ ๋ ์์ด์ ์ํ์ ์ผ๋ก ๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
(์ฌ๊ธฐ์ n!์ n์ ๊ณ์น(factorial)์ ์๋ฏธํ๋ฉฐ, 1๋ถํฐ n๊น์ง์ ์์ฐ์๋ฅผ ๋ชจ๋ ๊ณฑํ ๊ฐ์ ๋๋ค.)
- nPr : ์๋ก ๋ค๋ฅธ n๊ฐ์ ์์์์ r๊ฐ๋ฅผ ์ ํํ๋ ์์ด์ ์
- nPr = n! / (n-r)!
์๋ฅผ ๋ค์ด, 5๊ฐ์ ์ซ์ 1, 2, 3, 4, 5์์ 3๊ฐ์ ์ซ์๋ฅผ ์ ํํ์ฌ ์์๋๋ก ๋์ดํ๋ ๊ฒฝ์ฐ์ ์๋ 5P3 = 5! / (5-3)! = 120์ ๋๋ค.
์กฐํฉ (combination)
์กฐํฉ์ด๋ ์๋ก ๋ค๋ฅธ n๊ฐ์ ์์์์ r๊ฐ๋ฅผ ์ ํํ ๋, ์์๋ฅผ ๊ณ ๋ คํ์ง ์๋ ๊ฒ์ ์๋ฏธํฉ๋๋ค.(๋จ, 0<r≤n์ผ ๋)
- nCr : ์๋ก ๋ค๋ฅธ n๊ฐ์ ์์์์ r๊ฐ๋ฅผ ์ ํํ๋ ์กฐํฉ์ ์
- nCr = n! / (r! * (n-r)!)
์๋ฅผ ๋ค์ด 5๊ฐ์ ์ซ์ 1, 2, 3, 4, 5์์ 3๊ฐ์ ์ซ์๋ฅผ ์ ํํ๋ ๊ฒฝ์ฐ์ ์๋ 5C3 = 5! / (3! * 2!) = 10์ ๋๋ค.
์์ด๊ณผ ์กฐํฉ์ ์ฐจ์ด
๊ฐ์ฅ ํฐ ์ฐจ์ด๋ ์์๋ผ๊ณ ๊ธฐ์ตํ๋ฉด ๋ ๊ฒ ๊ฐ์ต๋๋ค ๐จ
์์ด์ ๋ผ๋
์์ฐ์ N๊ณผ M์ด ์ฃผ์ด์ก์ ๋, 1๋ถํฐ N๊น์ง ์์ฐ์ ์ค์์ ์ค๋ณต ์์ด M๊ฐ๋ฅผ ๊ณ ๋ฅธ ์์ด > ์์ด - ๋ฐฑ์ค N๊ณผ M(1)
func ์์ด(_ depth: Int) {
if ๋์ค๊ฐ ์ํ๋ ๊ธธ์ด์ธ M๊น์ง ๋๋ฌํ๋ค๋ฉด
์ถ๋ ฅ
else { ์์ง ๋ง์ง๋ง๊น์ง ๋๋ฌํ์ง ์์๋ค๋ฉด
for ์ธ๋ฑ์ค 0๋ถํฐ N-1๊น์ง ๋๋ค {
if ๋ง์ฝ ๋ฐฉ๋ฌธํ์ง ์์๋ค๋ฉด {
๋ฐฉ๋ฌธ์ฒ๋ฆฌ
ํ์ฌ์์ด[๋์ค] = ํ์ฌ ์ธ๋ฑ์ค + 1
์์ด(๋์ค + 1)
๋ฐฉ๋ฌธ์ฒ๋ฆฌ ํด์
}
}
}
}
Swift๋ก๋ ๋ค์๊ณผ ๊ฐ๋ค.
var res = Array(repeating: 0, count: M)
func solution(_ lev: Int) {
if lev == M {
print(res.map {String($0)}.joined(separator: " "))
} else {
for i in 0..<N {
if visited[i] == false {
visited[i] = true
res[lev] = i+1
solution(lev + 1)
visited[i] = false
}
}
}
}
solution(0)
์กฐํฉ์ ๋ผ๋
- ์์ฐ์ N๊ณผ M์ด ์ฃผ์ด์ก์ ๋, 1๋ถํฐ N๊น์ง ์์ฐ์ ์ค์์ ์ค๋ณต ์์ด M๊ฐ๋ฅผ ๊ณ ๋ฅธ ์์ด - ๋ฐฑ์ค N๊ณผ M(2)
- ๊ณ ๋ฅธ ์์ด์ ์ค๋ฆ์ฐจ์์ด์ด์ผ ํ๋ค > ์์์ ๋ฝ์ ์๋ ๋ค์์ ๋ฝ์ง ์๋๋ค > ์กฐํฉ
func ์กฐํฉ(_ depth: Int, _ start: Int) {
if ๋์ค๊ฐ M๊น์ง ๋๋ฌํ๋ค๋ฉด {
๊ฒฐ๊ณผ๋ฐฐ์ด ์ถ๋ ฅ
} else {
์ธ๋ฑ์ค๋ฅผ start ๋ถํฐ N-1๊น์ง ๋ฐ๋ณต {
๊ฒฐ๊ณผ ๋ฐฐ์ด[๋์ค] = ์ธ๋ฑ์ค + 1
์กฐํฉ(๋์ค + 1, ์ธ๋ฑ์ค + 1)
}
}
}
var res = Array(repeating: 0, count: M)
func solution(_ depth: Int, _ begin: Int) {
if depth == M {
print(res.map {String($0)}.joined(separator: " "))
} else {
for i in begin..<N {
res[depth] = i + 1
solution(depth + 1, i + 1)
}
}
}
solution(0, 0)
-
๊ณ ๋ฑํ์๋ ์ด์ฌํ ํ๋ฅ ๊ณผ ํต๊ณ ๊ณต๋ถํ๋ ๊ธฐ์ต์ด ๋์, ๋ ์ฝ๊ฒ ์ดํดํ ์ ์์๋ ๊ฑฐ ๊ฐ๋ค..!
์ด์ ๊น์ง๋ ์์ด ์กฐํฉ Swift ์ฝ๋๋ง ์๊ฐํ๊ณ ๋ง์ฃผํ๊ธฐ ์ฝ๊ฐ ๋ง์ค์ฌ์ก๋๋ฐ, ์ด์ ๋ ์ํ๋ฌธ์ ํธ๋ ๊ฒ์ฒ๋ผ ๋ฟ์๋ ์ฌ๋ฏธ๊ฐ ์๋ค ๐
์ง๋๊ณ ๋ณด๋ฉด ๋ฌด์์ด๋ ๋ค ์ด์ ์๋ ํ์ต์ธ ๊ฒ ๊ฐ๋ค ๐ช๐ผ
'๐ Algorithm > ์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์๊ณ ๋ฆฌ์ฆ] 02. BFS์ DFS ์๊ณ ๋ฆฌ์ฆ์ ๋ผ๋ with Swift (1) | 2023.12.28 |
---|---|
[์๊ณ ๋ฆฌ์ฆ] 01. ๋์ ํฉ with Swift (0) | 2023.12.23 |