내일배움캠프 48일차 TIL _ 10주 5일차

 

• 오늘 있었던 일
  
  • 팀과제
  • 알고리즘

SPRIONG

• 스프링 정리

 

 

알고리즘 문제 풀기

 

     ● 피로도

● 피로도 //링크

class Solution {
    static int max = 0; 
    public int solution(int k, int[][] dungeons) {
        max = 0; 
        btk(dungeons, 0, k);
        return max;
    }

    private static void btk(int[][] dungeons, int idx, int k) {
        for (int i = idx; i < dungeons.length; i++) {
            swap(dungeons, idx, i); 

            if (k >= dungeons[idx][0]) { 
                max = Math.max(max, idx + 1); 
                k -= dungeons[idx][1]; 

                btk(dungeons, idx + 1, k); 
                k += dungeons[idx][1]; 
            }

            swap(dungeons, idx, i); 
        }
    }

    private static void swap(int[][] dungeons, int i, int j) {
        int[] temp = dungeons[i];
        dungeons[i] = dungeons[j];
        dungeons[j] = temp;
    }
}

• gpt 최고야아앗!
  
  • 문제 지문에
    •  매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.
  • 한바퀴를 도는것을 생각해야한다 
    • 정렬을 이용해 구하려 했지만 어째서서인지 통과하지 못했다가 지문을 다시보고 생각해보니, 최대 던전의 수라는건 여러 경우를 구하는 것을 이야기 한다는 것을 깨달았다.
    • 백트래킹이라는 방식을 알게 되었다, 이런 방법이 있네
• 밑은 다른 사람의 풀이

• class Solution {
      public static boolean check[];
      public static int ans = 0;
  
      public int solution(int k, int[][] dungeons) {
          check = new boolean[dungeons.length];
  
          dfs(k, dungeons, 0);
  
          return ans;
      }
      public static void dfs(int tired, int[][] dungeons, int cnt){
          for(int i=0; i<dungeons.length; i++){
              if(!check[i] && dungeons[i][0]<=tired){
                  check[i] = true;
                  dfs(tired-dungeons[i][1], dungeons, cnt+1);
                  check[i] = false;
              }
          }
          ans = Math.max(ans, cnt);
      }
  }

• 백트래킹 말고 dfs도 있구나

 

---

당일 회고

• 끼얏호우 팀과제 끝났다!