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

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

프로그래머스

 

방법1) deque를 이용한 BFS

"""
입출력 예시)
numbers = [1, 1, 1, 1, 1], target = 3 -> 5
numbers = [4, 1, 2, 1], target = 4 -> 2
"""

# 방법1) deque를 이용한 BFS

from collections import deque

def solution(numbers, target):
    answer = 0
    de_que = deque()
    n = len(numbers)
  
    de_que.append([numbers[0],0]) # deque.append(x) -> x를 덱의 오른쪽에 삽입
    de_que.append([-1*numbers[0],0])

    while de_que:
        temp, idx = de_que.popleft() # deque.popleft() -> 덱의 가장 왼쪽(인덱스: 0)에 있는 원소를 덱에서 제거하고 그 값을 리턴
        idx += 1

        if idx < n:
            de_que.append([temp+numbers[idx], idx])
            de_que.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1

    return answer

 

• deque.append(x) -> x를 덱의 오른쪽에 삽입
• deque.popleft() -> 덱의 가장 왼쪽(인덱스: 0)에 있는 원소를 덱에서 제거하고 그 값을 리턴
  • https://ooeunz.tistory.com/31

[Python] Dequeue 사용하기

 

 

# temp, idx = de_que.popleft()

 while de_que:
 	temp, idx = de_que.popleft() 
    # deque.popleft() -> 덱의 가장 왼쪽(인덱스: 0)에 있는 원소를 덱에서 제거하고 그 값을 리턴
 
"""
deque([[4, 0], [-4, 0]])인 경우
-> temp: 4
-> idx: 0
"""

 

 

 

---

방법2) stack을 이용한 DFS

# 방법2) stack을 이용한 DFS
  
def solution(numbers, target):
    answer = 0
    queue = [[numbers[0],0], [-1*numbers[0],0]]
    n = len(numbers)

    while queue:
        temp, idx = queue.pop() # queue.pop() -> 리스트의 마지막 항목을 삭제하고 리턴
        idx += 1

        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1

    return answer

 

• list.pop([i]): 리스트에서 주어진 위치에 있는 항목을 삭제하고, 그 항목을 리턴
• list.pop(): 리스트의 마지막 항목을 삭제하고 리턴
  • https://docs.python.org/ko/3/tutorial/datastructures.html

5. 자료 구조 — Python 3.10.6 문서

 

 

# temp, idx = queue.pop()

while queue:
	temp, idx = queue.pop() 
    # queue.pop() -> 리스트의 마지막 항목을 삭제하고 리턴
 
"""
queue = [[4, 0], [-4, 0]]인 경우
-> temp: -4
-> idx: 0
"""

 

 

 

---

방법3) 재귀함수를 이용한 DFS

# 방법3) 재귀함수를 이용한 DFS
  
def solution(numbers, target):
    n = len(numbers)
    answer = 0
    
    def dfs(idx, result):
        if idx == n:
            if result == target:
                nonlocal answer
                answer += 1
            return
        else:
            dfs(idx+1, result+numbers[idx])
            dfs(idx+1, result-numbers[idx])
            
    dfs(0,0)
    
    return answer

 

 

 

코드 풀이 설명 참고)

 

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)

 

 

 

---

DFS와 BFS 

 

• DFS: 깊이 우선 탐색 
  • 모든 노드를 방문하고자 하는 경우에 이 방법 선택
  • BFS보다 좀 더 간단
  • 검색 속도는 BFS에 비해 느림
  • Stack 또는 재귀함수(Recursion)로 구현

DFS (출처: https://developer-mac.tistory.com/64)

 

• BFS: 너비 우선 탐색
  • 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법 선택
  • Queue로 구현

BFS (출처: https://developer-mac.tistory.com/64)

 

https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90

DFS, BFS의 설명, 차이점