역시 level3랑 level2는 조금 차이가 나는 것 같다. 왜냐하면 level2는 그래도 엄청 오래 고민하면 풀 수 있기 때문이지 !!!

1. 문제

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

처음에 문제를 보고 부르트포스로 풀어야 하나...? 싶다가

DFS/BFS인 것을 보고 이전에 공부했던 거를 바탕으로 풀어봐야겠다! 싶었다.

2. 풀이

1. 내 풀이: 성공

def solution(numbers, target):
    n = len(numbers)
    answer = 0
    def dfs(index, result):
        if index == n:
            if result == target:
            	nonlocal answer
                answer += 1
            return answer
        else:
            dfs(index+1, result+numbers[index])
            dfs(index+1, result-numbers[index])
    dfs(0,0)
    return answer

그럼 풀이를 하나하나 살펴보자.

n = len(numbers)
answer = 0

일단 numbers의 len을 n에 할당해주고, answer도 0으로 초기화한다.
다음 dfs!

def dfs(index, result):

일단 파라미터로 index와 result를 선언해준다. 이 때 index는 numbers에 접근하기 위한 것이고, result는 dfs을 이용하여 만들어지는 수(최종적으로는 target이랑 같아져야 함)이다.

dfs(0,0)

마지막에 보면 dfs에 모두 0을 넣는데, 일종의 초기화 시켜주는 작업이라고 보면 된다. dfs 내에서 index = 0, result = 0을 선언하려고 했으나, dfs를 재귀적으로 사용해야한다는 걸 깨닫고 바꿨다.

if index == n:
    if result == target:
         nonlocal answer
       	 answer += 1
    return answer

그 후에 만약 index와 n, 즉 numbers의 개수가 같다면, 한 번의 조건문을 더 판단하도록 한다. result와 target이 같으면 answer을 nonlocal로 바꿔준 후에 answer에 1을 더해준다. 그리고 answer을 return 해주기!

참고로 nonlocal은

나는 지금 지역변수는 아닌 변수를 사용할거다!

라는 뜻이다. 처음에는 global을 쓰려고 했으나, 이상하게 안 먹혀서 nonlocal을 썼다. global이랑 nonlocal 배울 때는 저걸 어따 써먹어... 했는데... 이렇게 써먹을 줄이야.

else:
     dfs(index+1, result+numbers[index])
     dfs(index+1, result-numbers[index])

그런데 만약 여기서 result와 target이 같지 않다면 dfs를 한 번 더 돈다. 자, 여기서 2가지로 나뉘는데, 타겟넘버를 만들기 위해서는 연산이 - 혹은 +만 사용할 수 있으므로 result에서 numbers[index]를 각각 더하고 빼주는 것이다. 트리가 두 가지로 뻗어나와 더 깊어지는 것을 연상하면 쉬울 것이다.

이 과정을 거치면 타겟 넘버를 만들 수 있다! 나름 깔끔한 풀이인 것 같아 뿌듯하다.

2. 다른 풀이

DFS를 사용한 풀이는 대부분 비슷하고... BFS를 사용한 풀이는 BFS에 대한 추가적인 공부가 필요할 것 같아 나중에 올리는 걸로!

오늘도 코테 스터디 리뷰 끝!