99클럽 코테 스터디 11일차 TIL + DFS/프로그래머스 [타겟 넘버] JAVA풀이

 

 

 

 

 

 

1. 오늘의 학습 키워드

---

 

DFS 재귀함수

JAVA

트리

 

 

 

2. 오늘의 학습 문제 

---

문제

---

 

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=java

프로그래머스

 

 

코드

---

import java.util.*;

class Solution {
    
    static int answer = 0;
    public int solution(int[] numbers, int target) {
        
        dfs(numbers, target, 0,0);
        return answer; 
        
    }
    
    static public void dfs(int[] numbers, int target, int depth, int sum){
        
        if(depth==numbers.length){ //DFS +-모두 탐색한 경우
            if(sum==target)
                answer++;
        }
        else{
            dfs(numbers, target, depth+1, sum + numbers[depth]);
            dfs(numbers, target, depth+1, sum - numbers[depth]);
        }
        
    }
           
}

 

 

재귀함수를 이용한 DFS 풀이이다. (내부적으로는 스택을 사용한다.)

 

* .length는 배열의 길이 

.length()는 문자열의 길이

size()는 ArrayList의 길이

*()가 붙은 것들은 메서드이기 때문이며, .length는 배열의 속성이기 때문에 ()가 없다. 따라서 .length는 오버라이드도 불가함! 그 자체로 배열의 크기를 나타내는 불변의 속성이기 때문이다. 

 

3. 오늘의 회고

---

 

 

• DFS는 그래프, depth, 재귀, 스택을 생각하자
• +-+-...의 조합을 구해야한다는 생각은 좋았으나, 일일이 조합을 저장하려는 시도는 복잡했다. 
• 구조에 대해 트리 그림을 그려보자 - > 할만하다 싶으면 DFS
• 문제의 요구사항을 파악하는 것이 중요하다
• 중요한 건 많이 푸는 것
• 문제를 실패하면, 비기너 문제도 풀어봐서 기초를 잡자
• 예전에 풀었던 문제였다... 파이썬 풀이 링크 첨부
• https://pudingcoding.tistory.com/37

[프로그래머스] 타겟넘버 파이썬 풀이 lv2