243. 타겟 넘버
1) 어떤 전략(알고리즘)으로 해결?
DFS/BFS
2) 코딩 설명
https://school.programmers.co.kr/learn/courses/30/lessons/43165
<내 풀이>
- 주석 참고
def solution(numbers, target):
global answer
answer = 0
def dfs1(idx, now) :
# 프로그래머스에서 재귀 구현할 때 sol 함수 안에 선언
global answer
# 누적 계산 될 것
if now == target and idx == len(numbers) :
#걍 target 이랑 똑같으면 멈추면 안되고
#numbers 끝까지 쓰여야 성립되는 것이고
#그제야 멈추기 가능해
answer+=1
if idx == len(numbers) :
return # 그리고 다 쓰면 멈춤 조건 걸어주기
plus_now = now + numbers[idx]
dfs1(idx+1, plus_now) # 플러스 해주는 가지
minus_now = now - numbers[idx]
dfs1(idx+1, minus_now ) # 마이너스 해주는 가지
dfs1(0, 0 )
return answer
< 내 틀렸던 풀이, 문제점>
- 두번째 재귀문까지 도달하지 않는 경우 발생함
from collections import deque
def solution(numbers, target):
global answer
answer = 0
zero = 0
numbers = deque(numbers)
print(target, "target ")
# dfs(numbers, 0, target, 0)
def dfs(numlist, now, target) :
global answer
if now == target :
print("hihi")
answer+=1
return
elif not numlist :
return
else :
curr = numlist.popleft()
dfs(numlist, now + curr, target ) //1)
dfs(numlist, now - curr, target ) // 2)
dfs(numbers, 0, target )
return answer
- dfs는 한 곳을 깊게 탐색, //1 에 해당하는 애에서 return 당하면 끝
- //2 까지 도달하지 않겠지
단단히 착각한 부분
- numbers 에 담긴 모든 요소들이 사용돼서 target 이 만들어졌어야 하는 것이지
- 그 조건 추가함
if now == target and idx == len(numbers) :
# print(lis)
answer+=1<반성 점>
<배운 점>
- 프로그래머스에서 dfs, bfs 같이 재귀함수 구현해야하는 것 어떻게 작성해야하는지 체험했음
- def 를 def 바깥에 두는 것이 아니라 def 안에 둬야하는 것, 그렇게 global도 선언하고
(+) 이전에 내가 푸렀던 문제들 중 비슷한 문제
