알고리즘/프로그래머스문제풀이

[Python/프로그래머스]타겟넘버_DFS

개발자 덕구🐾 2022. 6. 15. 15:29
728x90

 

 

https://programmers.co.kr/learn/courses/30/lessons/43165

 

코딩테스트 연습 - 타겟 넘버

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수

programmers.co.kr

 

 

 


 

 

 

코드[블로그 참고] : 

def solution(numbers, target):
    answer = 0
    def dfs(idx, val) :
        if idx == len(numbers) :  #  주어진 수를 모두 사용
            if val == target : 
                nonlocal answer # 전역변수도 아닌데 지역변수 아님, 근데 이 수를 변경해야함
                answer +=1 
        else :
            dfs(idx+1, val + numbers[idx])
            dfs(idx+1, val - numbers[idx])
    
    dfs(0,0)
    return answer

 

 

내가 만든 코드 :

 

answer = 0

def solution(numbers, target):
    def dfs(idx,val) :
        global answer
        if idx == len(numbers) :
            if val == target :
                answer +=1
                return 
        else :
            dfs(idx+1, val+numbers[idx])
            dfs(idx+1, val-numbers[idx])
    dfs(0,0)
    return answer

 

 

블로그의 코드는 solution내에서 answer을 정의하며 nonlocal으로 사용하였다.

내가 만든 코드는 전역변수로 만들어서 global으로 answer를 사용하였다. 

 

 

 

 

전형적인 DFS 

easy 하다.

 

 

 

 

 

 

참고 블로그 : 

 

<nonlocal>

https://juhi.tistory.com/6

 

[Python] nonlocal, global로 변수의 scope 변경하기 (파이썬에서 전역변수 사용하기)

👀 다른 scope에 있는 변수를 사용할 때 문제 case 1. 더 넓은 범위에 있는 변수 '읽기'는 가능 아래와 같이 전역변수로 n을 선언하고 이를 함수 내에서 읽기만 하는 경우 에러가 나지 않는다. n = 0 de

juhi.tistory.com

 

<코드 참고>

https://velog.io/@ju_h2/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level2-%ED%83%80%EA%B2%9F%EB%84%98%EB%B2%84-BFSDFS

 

[Python] 프로그래머스 level2 타겟넘버 (BFS/DFS)

타겟넘버 문제를 bfs와 dfs를 이용해서 풀어봤다. 아래 나오는 코드들은 다 모든 테스트케이스를 통과한 코드이다!

velog.io

 

복습 : 

 

20220623

✅ 20220624

✅ 20220625

✅ 20220626

✅ 20220628

🐾 20220921

🐾 20220924

반응형