728x90
https://school.programmers.co.kr/learn/courses/30/lessons/43165
ํ๋ก๊ทธ๋๋จธ์ค
์ฝ๋ ์ค์ฌ์ ๊ฐ๋ฐ์ ์ฑ์ฉ. ์คํ ๊ธฐ๋ฐ์ ํฌ์ง์ ๋งค์นญ. ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฐ๋ฐ์ ๋ง์ถคํ ํ๋กํ์ ๋ฑ๋กํ๊ณ , ๋์ ๊ธฐ์ ๊ถํฉ์ด ์ ๋ง๋ ๊ธฐ์ ๋ค์ ๋งค์นญ ๋ฐ์ผ์ธ์.
programmers.co.kr
์ด ๋ฌธ์ DFS/BFS ์ ํ์ธ ๊ฑธ ์๊ณ ๋ ๋์ ํ ํ์ด๊ฐ ๋ ์ค๋ฅด์ง ์์์ ๋ค๋ฅธ ๋ถ๋ค ํ์ด๋ฅผ ์ฐธ๊ณ ํ๋ค.
ํ์ด๋ฅผ ๋ณด๋ฉด ์ดํด๊ฐ ๋๋๋ฐ ๋ด๊ฐ ๋ ์ฌ๋ฆฌ๋ ๊ฑด ์ ์ด๋ ๊ฒ ํ๋ค์ง
๋ฉฐ์น ๋ค์ ๋ค์ ํ์ด๋ด์ผ๊ฒ ๋ค.
BFS
def solution(numbers, target):
answer = 0
leaves = [0]
for num in numbers:
temp = []
for parent in leaves:
temp.append(parent + num)
temp.append(parent - num)
leaves = temp
for leaf in leaves:
if leaf == target:
answer += 1
return answer
DFS
def dfs(numbers, target, depth):
answer = 0
if depth == len(numbers):
if sum(numbers) == target:
return 1
else:
return 0
else:
answer += dfs(numbers, target, depth+1)
numbers[depth] *= -1
answer += dfs(numbers, target, depth+1)
return answer
def solution(numbers, target):
return dfs(numbers, target, 0)
728x90
'์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํ์ด > -' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ๋ก๊ทธ๋๋จธ์ค] ์คํ์ฑํ ๋ฐฉ (0) | 2023.06.10 |
---|---|
[ํ๋ก๊ทธ๋๋จธ์ค] k์ง์์์ ์์ ๊ฐ์ ๊ตฌํ๊ธฐ (0) | 2023.06.09 |
[ํ๋ก๊ทธ๋๋จธ์ค] ํํ (0) | 2023.06.03 |
[ํ๋ก๊ทธ๋๋จธ์ค] ์์ (0) | 2023.06.03 |
[ํ๋ก๊ทธ๋๋จธ์ค] ํ๋ ฌ์ ๊ณฑ์ (0) | 2023.06.02 |