๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ ํ’€์ด/-

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ํƒ€๊ฒŸ ๋„˜๋ฒ„

by syLim___ 2023. 6. 8.
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