๋ ๋ฌธ์ ๋ฅผ ๊ตฌ๋ถํ๋ ๊ธฐ์ค์ด ์ฝ๊ฐ ๋ชจํธํ์ง๋ง..
๋ฌธ์ ๋ฅผ ํ๋ฉด์ ๋ง๋ฌ๋ ๋ช๋ช ์ ํ๋ค์ ๊น๋จน์ง์๊ธฐ ์ํด ์ ๋ฆฌํด๋๋ค.
DFS / ๋ฐฑํธ๋ํน
nums = [1,2,3]
result = []
permute = []
def dfs():
if len(permute) == len(nums) :
result.append(permute[:])
return
for i in range(len(nums)) :
if nums[i] not in permute :
permute.append(nums[i])
dfs()
permute.pop()
dfs()
print(result)
DFS
25731๋ฒ : ๋น์ฐ
https://www.acmicpc.net/problem/2573
2573๋ฒ: ๋น์ฐ
์ฒซ ์ค์๋ ์ด์ฐจ์ ๋ฐฐ์ด์ ํ์ ๊ฐ์์ ์ด์ ๊ฐ์๋ฅผ ๋ํ๋ด๋ ๋ ์ ์ N๊ณผ M์ด ํ ๊ฐ์ ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋ค. N๊ณผ M์ 3 ์ด์ 300 ์ดํ์ด๋ค. ๊ทธ ๋ค์ N๊ฐ์ ์ค์๋ ๊ฐ ์ค๋ง๋ค ๋ฐฐ์ด์ ๊ฐ ํ์
www.acmicpc.net
: 2์ฐจ์ ๊ทธ๋ํ ๋ฌธ์
: โ๏ธ์ผ์์ ์์ฐจ์ ์ผ๋ก ๋ น์ด๋ฉด ์์ง ๋ น์ง์์ ์ผ์์๋ ์ํฅ์ด ๊ฐ ์ ์๊ธฐ๋๋ฌธ์ ๋ น๋ ์ผ์๋ค์ ๋ฐ๋ก ์ ์ฅํด ๋์๋ค๊ฐ ํ ํ ์ด ๋๋ ํ ํ๊บผ๋ฒ์ ์ ์ฉํด์ค๋ค.
2617๋ฒ : ๊ตฌ์ฌ ์ฐพ๊ธฐ
https://www.acmicpc.net/problem/2617
2617๋ฒ: ๊ตฌ์ฌ ์ฐพ๊ธฐ
๋ชจ์์ ๊ฐ์ผ๋, ๋ฌด๊ฒ๊ฐ ๋ชจ๋ ๋ค๋ฅธ N๊ฐ์ ๊ตฌ์ฌ์ด ์๋ค. N์ ํ์์ด๋ฉฐ, ๊ตฌ์ฌ์๋ ๋ฒํธ๊ฐ 1,2,...,N์ผ๋ก ๋ถ์ด ์๋ค. ์ด ๊ตฌ์ฌ ์ค์์ ๋ฌด๊ฒ๊ฐ ์ ์ฒด์ ์ค๊ฐ์ธ (๋ฌด๊ฒ ์์๋ก (N+1)/2๋ฒ์งธ) ๊ตฌ์ฌ์ ์ฐพ๊ธฐ ์ํด์
www.acmicpc.net
: ๊ตฌ์ฌ์ ์ด๋ค ์์ผ๋ก ๊ทธ๋ํ๋ก ํํํ ์ง๋ง ๋ ์ค๋ฅด๋ฉด ํฌ๊ฒ ์ด๋ ต์ง์์ ๋ฌธ์ ์ด๋ค. (๊ทธ๊ฒ ์ด๋ ต์ง๋ง..)
: ๊ตฌ์ฌ์ ๋ฌด๊ฒ๋ก ์ค๋ฆ์ฐจ์, ๋ด๋ฆผ์ฐจ์ ๊ทธ๋ํ๋ก ํํํ์ฌ ํน์ ๋ ธ๋์ ์์๋ ธ๋๊ฐ ๊ตฌ์ฌ์ n/2๊ฐ ์ด์์ผ๋ ์ค๊ฐ์ ์ฌ ์ ์๋ ๊ตฌ์ฌ์ด๋ค.
: defauldict()ํจ์๋ฅผ ์ฌ์ฉํ๋ฉด ํธํ๊ฒ ๋์ ๋๋ฆฌ๋ฅผ ์ฌ์ฉํ ์์ด๋ค. - ์ฌ์ฉํ์ง ์์๋ ๋ฌธ์ ์์ด ๊ตฌํ๊ฐ๋ฅ
light = defaultdict(list) #defauldict์ ์ฌ์ฉํด์ ์ ์ธ
heavy = defaultdict(list)
for i,j in biz :
light[i].append(j)
heavy[j].append(i)
# ํค๊ฐ์ด ์์ผ๋ฉด ๋น ๋ฆฌ์คํธ๊ฐ ์ ์ฅ๋๊ธฐ๋๋ฌธ์
# ์๋ ์ธ๋ฑ์ค์ ์ ๊ทผํ์์๋๋ ์๋ฌ๊ฐ ๋์ง์๋๋ค.
14888๋ฒ : ์ฐ์ฐ์ ๋ผ์๋ฃ๊ธฐ
https://www.acmicpc.net/problem/14888
14888๋ฒ: ์ฐ์ฐ์ ๋ผ์๋ฃ๊ธฐ
์ฒซ์งธ ์ค์ ์์ ๊ฐ์ N(2 ≤ N ≤ 11)๊ฐ ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ A1, A2, ..., AN์ด ์ฃผ์ด์ง๋ค. (1 ≤ Ai ≤ 100) ์ ์งธ ์ค์๋ ํฉ์ด N-1์ธ 4๊ฐ์ ์ ์๊ฐ ์ฃผ์ด์ง๋๋ฐ, ์ฐจ๋ก๋๋ก ๋ง์ (+)์ ๊ฐ์, ๋บ์ (-)์ ๊ฐ์,
www.acmicpc.net
: DFS๋ก ์ด๋ป๊ฒ ๊ตฌํํด์ผํ๋์ง ์ ๋ ์ค๋ฅด์ง์๋๋ค.
: ์ด์ ์ ์์ด(ํจ์)๋ก ํด๊ฒฐํ๋ ๊ธฐ์ต์ด ์์ด์ ๊ทธ๋ฐ์ง ์์ด ๋ฐ์ ๋ ์ค๋ฅด์ง์์ ๋ฐฑํธ๋ ํน์ผ๋ก ๋ชจ๋ ์์ด ์กฐํฉ์ ๊ตฌํ๋ค์์ ์ฐ์ฐํ์ฌ ์ต์,์ต๋๊ฐ์ ๊ตฌํ๋ ๋ฐฉ์์ผ๋ก ๊ตฌํํ์๋ค. > ์๋ ํจ์๋ฅผ ๊ตณ์ด ๊ตฌํํ์ฌ ์ ๋ต์ ๋ง์์ง๋ง ์ด๋ค ๋ฉ๋ฆฌํธ๋ ์์๋ค.
: dfs๋ฐฉ์์ผ๋ก ํ์์ ๊ฒฝ์ฐ ์์ ํ์์ด๋ผ๋ ์ ์ ๋๊ฐ์ง๋ง depth๋ฅผ ๊ธฐ๋กํ์ฌ ๋จ์์๋ ๋ชจ๋ ์ฐ์ฐ์์ ๊ฒฝ์ฐ๋ก ๊ฐ์ง ๋ป์ด ๋๊ฐ๋ฏ์ด ํจ์๋ฅผ ์ฌํธ์ถํด์ฃผ๋ฉด์ ์ฐ์ฐ์ ๋ฐ๋ณตํ์ง์์๋์ ํจ์ฌ ํจ์จ์ ์ด๋ค.
BFS
18352๋ฒ : ํน์ ๊ฑฐ๋ฆฌ์ ๋์ ์ฐพ๊ธฐ
https://www.acmicpc.net/problem/18352
18352๋ฒ: ํน์ ๊ฑฐ๋ฆฌ์ ๋์ ์ฐพ๊ธฐ
์ฒซ์งธ ์ค์ ๋์์ ๊ฐ์ N, ๋๋ก์ ๊ฐ์ M, ๊ฑฐ๋ฆฌ ์ ๋ณด K, ์ถ๋ฐ ๋์์ ๋ฒํธ X๊ฐ ์ฃผ์ด์ง๋ค. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) ๋์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์ ๊ฑธ์ณ์ ๋ ๊ฐ
www.acmicpc.net
: ์์ ์ ์ ๋ถํฐ n๋ฒ๊น์ง ๊ฐ์ ์๋ ๋ ธ๋ ๊ตฌํ๊ธฐ
: while ๋ฌธ์ level์ ์ธ์ n๋ฒ์ด ๋๋ฉด ์ข ๋ฃ๋๋๋กํ๋ค. ( bfs๋ ํญ์ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๋ณด์ฅํ๋ค. )
: queue(deque)๋ฅผ ์ฌ์ฉํ์ง์๊ณ ๋ฐฐ์ด๋ก๋ง ๊ตฌํํ์๋ค. ๋์ผํ ๋ ๋ฒจ์ด์๋ ๋ ธ๋๋ฅผ ์ ๋ถ ๋ฆฌ์คํธ์ ๋ด๊ณ popํ๋ ๋์ ๋ฆฌ์คํธ์ ๋ค์ด์๋ ๋ชจ๋ ๋ ธ๋๋ฅผ ๊ฒ์ฌํ๋ ๋ฐฉ์์ผ๋ก ๊ตฌํํ์๋ค. ๋ค๋ฅธ ๋ ์ข์ ๋ฐฉ๋ฒ์ด ์์์ง ๋ชจ๋ฅด๊ฒ ๋ค.
7569๋ฒ : ํ ๋งํ
https://www.acmicpc.net/problem/7569
7569๋ฒ: ํ ๋งํ
์ฒซ ์ค์๋ ์์์ ํฌ๊ธฐ๋ฅผ ๋ํ๋ด๋ ๋ ์ ์ M,N๊ณผ ์์์ฌ๋ ค์ง๋ ์์์ ์๋ฅผ ๋ํ๋ด๋ H๊ฐ ์ฃผ์ด์ง๋ค. M์ ์์์ ๊ฐ๋ก ์นธ์ ์, N์ ์์์ ์ธ๋ก ์นธ์ ์๋ฅผ ๋ํ๋ธ๋ค. ๋จ, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,
www.acmicpc.net
: 3์ฐจ์ ๊ทธ๋ํ - 2์ฐจ์ ๊ทธ๋ํ ํ์ ๋ฐฉ๋ฒ์์ ์์๋๋ง ์ถ๊ฐ๋ก ํ์ธํด์ฃผ๋ฉด ๋๋ค.
: ๋น์ฐ๊ณผ ๋ฌ๋ฆฌ ํ๋ฒ ์ ๊ทผํ ์์ญ์ ์๋ฃ๋์ด ์ฌ์ ๊ทผ ํ์ง์์๋ ๋๊ธฐ ๋๋ฌธ์ ์ ๊ทผ ํ์ธ์ ๋ฐ๋ก ์ ์ฉํ๊ณ visited์ ์ฒดํฌํด์ค๋ค.
:โ๏ธ์์ ๊ฐ์ ํ๋์ฉ ๋ด์ผ๋ฉด dfs๊ฐ ํ๋ฒ ๋ ๋ ์ธ์ ํด์๋ ๊ทธ๋ํ๋ง ์ ์ฉ๋๊ธฐ๋๋ฌธ์ ํ๋ฃจ์ ๋ชจ๋ ๊ทธ๋ํ ์ฌ์ดํด์ ๊ฒ์ฌํ๊ธฐ ์ํด์ ๋ชจ๋ ์ด๊ธฐ๊ฐ์ ํ์ appendํด์ค๋ค.
18405๋ฒ : ๊ฒฝ์์ ์ ์ผ
https://www.acmicpc.net/problem/18405
18405๋ฒ: ๊ฒฝ์์ ์ ์ผ
์ฒซ์งธ ์ค์ ์์ฐ์ N, K๊ฐ ๊ณต๋ฐฑ์ ๊ธฐ์ค์ผ๋ก ๊ตฌ๋ถ๋์ด ์ฃผ์ด์ง๋ค. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ๊ฑธ์ณ์ ์ํ๊ด์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ์ N๊ฐ์ ์์๋ก ๊ตฌ์ฑ๋๋ฉฐ, ํด๋น ์์น
www.acmicpc.net
: ๋จ์ bfs๋ฌธ์ ๋ผ๊ณ ์๊ฐํ๋๋ฐ ๋ช๋ช ํจ์ ์ด ์์๋ค.
: ๐ ์ซ์๊ฐ ์์ ๋ฐ์ด๋ฌ์ค๊ฐ ๋จผ์ ํผ์ง๋ค > ์ฐ์ ์์ ํ ์ฌ์ฉ
: ๐ ๋ฐ์ด๋ฌ์ค ๊ฐ์๋งํผ ๋ฐ๋ณต๋ฌธ์ ๋๋ฆฌ๋๊ฒ 1์ด, 1์ด ํ์ ๋ฐ์ด๋ฌ์ค ๊ฐ์๋ฅผ ๊ฐฑ์ ํด ์ฃผ๋๊ฒ์ด ํต์ฌ์ด๋ค.
2665 ๋ฒ : ๋ฏธ๋ก๋ง๋ค๊ธฐ
https://www.acmicpc.net/problem/2665
2665๋ฒ: ๋ฏธ๋ก๋ง๋ค๊ธฐ
์ฒซ ์ค์๋ ํ ์ค์ ๋ค์ด๊ฐ๋ ๋ฐฉ์ ์ n(1 ≤ n ≤ 50)์ด ์ฃผ์ด์ง๊ณ , ๋ค์ n๊ฐ์ ์ค์ ๊ฐ ์ค๋ง๋ค 0๊ณผ 1์ด ์ด๋ฃจ์ด์ง ๊ธธ์ด๊ฐ n์ธ ์์ด์ด ์ฃผ์ด์ง๋ค. 0์ ๊ฒ์ ๋ฐฉ, 1์ ํฐ ๋ฐฉ์ ๋ํ๋ธ๋ค.
www.acmicpc.net
: ์ฐ์ ์์ ํ๋ฅผ ์ด์ฉํด ํด๊ฒฐ. ์ฌ์ค ์์ง ์์ ํ ์ดํดํ์ง ๋ชปํ๋ค. ๊ฒ์๋ฐฉ์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ํ์ธํ๋๊ฑฐ๊ฐ์๋ฐ..๐ค๐ค๐ค
: ์ฐ์ ์์ ํ๊ฐ ์๋ appendleft๋ฅผ ์ฌ์ฉํ๋ ๊ฐ๋ฅํ๋ค๊ณ ํ๋ค. ํ์ ๋ค์ ํ์ธ์์ .........................
์์ง ๋ฌธ์ ๋ฅผ ๋ณด๊ณ ์ด๋ค ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํ์ด์ผํ๋์ง ์ ๋ ์ค๋ฅด์ง์๋๋ค... ๋ง์ด ํ์ด๋ณด๋ฉด ์์์๊ฒ ์ง
์คํ(dfs)๊ณผ ํ(bfs) ์ฌ์ฉ์ ์ฐจ์ด
์คํ์ ๊ฒฝ์ฐ ๊ฐ๋ฅํ ๊ฒฝ๋ก๋ฅผ ๋ชจ๋ ๊ตฌํ๋๊ฒ ์ธ์ ๋ฑํ ์์ฉํ ์ ์ด ์์ด๋ณด์ธ๋ค. ํ๋ฅผ ์ฌ์ฉํ๋ ๊ฒฝ์ฐ๋, ๊ฐ์ ์์ ์์๋ฅผ ๊ฐ์ง ๋ ธ๋๋ฅผ ์ถ์ถํด๋ผ ์ ์๋ค.
๋ฌธ์ ์ ํ
- ๋ฐฉ๋ฌธ๊ฐ๋ฅํ ๋ ธ๋์ ๊ฐ์ ๊ตฌํ๊ธฐ : ๋ฐฉ๋ฌธํ ๋ ๋ง๊ฐ cnt += 1
- ๋ชฉ์ ์ง๊น์ง ๋๋ฌํ ๋ ์ต๋จ ๊ฑฐ๋ฆฌ : 2์ฐจ์ ํํ : move offset ๋ณ์(dx,dy)
- ์๋ก ์ธ์ ํ์ง์์ ์ง์ญ์ ๊ฐ์ ๊ตฌํ๊ธฐ - 2์ฐจ์ ํํ : ์ด์ค for ๋ฅผ ํตํด ๋ฐฉ๋ฌธ ์ํ๊ณณ์ ์์์ ์ผ๋ก ๋ชจ๋ ๋ฐฉ๋ฌธ
- ์ ์ ๋ ธ๋ ๊ฐ์ผ์ํค๊ธฐ - ๊ฐ์ผ๋ ๋ ธ๋๋ค์ ๋ชจ๋ ํ์ ๋ฃ๊ณ ์์ํ๋ค!!
- ๋์ผ ์์น์ ์ฌ๋ฐฉ๋ฌธ์ด ๊ฐ๋ฅํ ๊ฒฝ์ฐ
์ค๋๋ ์ด์ฝ!!๐๐ญ
'SW์ฌ๊ดํ๊ต ์ ๊ธ > ๊ฐ๋ฐ์ผ์ง - TIL' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Week05] C์ธ์ด - Red Black Tree (0) | 2022.05.05 |
---|---|
[Week04] ์๊ณ ๋ฆฌ์ฆ - ๋นํธ ๋ง์คํน (2) | 2022.04.26 |
[Week03] ์๊ณ ๋ฆฌ์ฆ - ์ ๋์จ ํ์ธ๋ (3) | 2022.04.20 |
[Week02] ์๊ณ ๋ฆฌ์ฆ - ํ (feat. python) (2) | 2022.04.14 |
[Week02] ์๊ณ ๋ฆฌ์ฆ - ์ด๋ถํ์ (5) | 2022.04.09 |
๋๊ธ