2022 02 09

2022-02-09

알고리즘 문제풀이 - DFS, BFS 활용

• DFS... 2^n 에서 줄여보기
  • 재귀 호출될 때 조건에 만족되지 않으면 바로 return을 하도록 하자!
    • 만족하는 값을 이미 구한 경우, flag를 만들어서 true 면 바로 return 시킴
    • 조건을 이미 초과해버렸다면, if 문으로 바로 return 하기

      private void solution(int total, int index) {
          if (flag) {
              return;
          }
          if (total > sum/2) {
              return;
          }
          if (index == num) {
              if (total == sum/2) {
                  flag = true;
                  answer = "YES";
              }
          } else {
              solution(total + array[index], index + 1);
              solution(total, index + 1);
          }
      }
      

• DFS는 모든 경우의 수를 구할때 고려할 것!
  • 배열을 돌면서도 이걸 넣을까 말까?
  • for문 돌면서도 이걸 넣을까 말까?

• 메모이제이션! 메모이제이션!
  • 구해야하는 것이 반복된다면 배열에 때려 넣어두자!