[programmers] 프로그래머스 Level2 타겟 넘버 (파이썬 Python)

(주)그렙

 

[programmers] 프로그래머스 Level2 타겟 넘버

(파이썬 Python)

 

* 문제출처 : 프로그래머스 코딩 테스트 연습, 알고리즘 문제

 

 

 

1) 문제

---

프로그래머스 Level2 타겟 넘버 파이썬

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

 

 

 

 

 

2) 코드

---

def dfs(cur_idx, max_idx, arr, cur_sum, target):
    if(cur_idx == max_idx):
        if(cur_sum == target):
            return 1
        return 0
    
    plus_result = dfs(cur_idx+1, max_idx, arr, 
                     cur_sum + arr[cur_idx], target)
    
    minus_result = dfs(cur_idx+1, max_idx, arr,
                      cur_sum - arr[cur_idx], target)
    
    return plus_result + minus_result
 
def solution(numbers, target):
    answer = dfs(0, len(numbers), numbers, 0, target)
    
    return answer

 

 

 

 

 

 

 

3) 풀이 과정

---

1. def solution 부분 dfs로 돌리기

배열(numbers가)이기 때문에 시작점을 0으로 스타트

 

2. def dfs() 작성 시작

ㄴ> 만약 시작 인덱스가 최대 인덱스(즉, 마지막 인덱스)로 돌게 되었고, 그 때 합계와 타겟하는 넘버가 같다면

return 값을 1로 설정

Why? 방법의 수 이니까

 

그렇지 않으면 0을 반환시키고

 

그 외에 현재 인덱스와 최대 인덱스가 같지 않을 때 플러스와 마이너스를 구분하여 dfs 실시

 

 

 

 

 

 

 

< < 사고 과정 > >

---

1. n의 값의 범위 파악(2<=n<=20)

ㄴ> 최대 발생할 수 있는 시간 복잡도 2^20

Why? +, - 기점으로 나누어지니까

 

 

2. 1.을 파악 후 완전탐색으로 풀어야 겠다는 생각

Why? 연산 기준을 1000만 = 1초 로 기준을 잡았기에 2^20은 1000만 이내의 숫자이기 때문에

 

 

 

 

문제가 dfs/bfs여서 dfs/bfs를 쓰는것이 아니라, 왜 dfs/bfs를 쓸 수 밖에 없는지 파악

 

 

 

 

3. 그리디로 풀이가 가능한가?

ㄴ> No

ㄴ> 완전탐색으로 풀면서 dfs로 시작.

 

 

Why? 리스트 안의 값들을 어차피 다 돌려야 하기 때문에 bfs로 했을 경우 이점이 없으니까 dfs로 실시

 

 

 

 

 

 

4) 정리 노트

---

1. 문제에서 dfs/bfs 로 나뉘어 있기 때문에 dfs/bfs가 아니라, 왜 dfs/bfs 밖에 쓸 수 없는지를 우선적으로 파악해야 한다.

 

2. 연산수 1000만 = 1초 기점으로 기준을 잡고 시작

 

 

 

 

 

만약 위의 문제가 어렵다면?...)

numbers = [1,1,1]

target = 1

일 때 다음을 만들 수 있는 방법의 수는?

 

 

Answer)

def dfs(cur_idx, end_idx, arr, cur_sum, target):
  if(cur_idx == end_idx):
    if(cur_sum == target):
      return 1
    return 0
    
  plus = dfs(cur_idx+1, end_idx, arr, cur_sum + arr[cur_idx], target)
  minus = dfs(cur_idx+1, end_idx, arr, cur_sum - arr[cur_idx], target)
  
  return plus + minus
  
def solution(numbers, target):
  answer = dfs(0, len(numbers), numbers, 0, target)
  return answer
print(solution([1,1,1], 1))#3