백트래킹 조건추가?

다른 코테 문제를 풀다가 알게된 것....

백트래킹에 조건이 들어간다면?

백트래킹을 풀다가 조건이 추가되는 경우를 발견했다.

class Solution {

    static int n;
    static int m;
    static int k;
    static int [] isused = new int [1000000];
    static int [] arr = new int[1000000];
    static int [] value;
    static int count=0;

    private void dfs(int t){
        if(t==k){
            int sum=0;
            for(int i=0; i<k; i++){
                sum += value[arr[i]];
            }
            System.out.println();
            if(sum == m){
                for(int i=0; i<k; i++){
                    System.out.println(arr[i]+ " ");
                }
                System.out.println();
                count++;
            }
            return;
        }

        int st=0;
        if(t !=0) st = arr[t-1];
        for(int i=st; i<=n-1; i++){
            if(isused[i] ==0){
            //값이 홀수인경우 skip하는 형태
                if(value[i] %2 ==1)continue;
                isused[i] =1;
                arr[t] =i;//index의 값
                dfs(t+1);
                isused[i] =0;
            }
            
        }
    }

    public int solution(int N, int M, int K, int[] scores) {
        int answer = 0;
        n = N;
        m = M;
        k = K;
        value = scores;

        dfs(0);

        return count;
    }
}

처음에는 return을 해버려서 백트래킹이 아예 종료가 되어버렸다.
저런식으로 조건을 추가하고 continue를 해주면 된다.

정점에 도달했을 때 arr(정답이 들어가있는 배열 혹은 정답의 인덱스가 들어가 있는 배열)을 체크해도 되지만 그러면 추가적인 조사가 더 많이 들어가게 된다.

REVIEW

백트래킹은 풀어도 풀어도 어렵다ㅠ 하지만 이번엔 조건을 추가해 필터링하는 법을 깨달았다.
조건은 되도록 백트래킹이 실행되는 for문 안에 넣는 것이 좋다. 이유는 모두 다 완료하고 필터링하면 쓸데없는 연산이 늘어나기 때문이다. depth를 줄일 수 있는 경우가 있다면 수행속도 시간때문에 줄이는 것이 좋다.

오늘의 코테 문제

오늘은 DP문제 역시나 내가 싫어하는 문제이다.

문제의 접근 방법

처음에는 모든 경우의 수를 다 구해서 제일 큰 값을 찾아야하나 라고 생각했지만 경우의 수가 너무 많다고 판단해서 그렇게 안했다. 애초에 어디 노드로 가야할지도 정확하게 정해져 있지 않고 갈 수록 노드의 수가 너무나도 많아졌기 때문이다.
문제를 보니 일정한 규칙이 있는 것 같아 이건 DP로 풀어야한다고 생각했다.

로직은 가장 끝노드는 서로 더해주면 되고 가운데 노드는 더해진 값중에서 좀 더 큰 값을 선택해서 구해주면 된다. 위의 로직을 이용해서 가장 큰 값을 찾으면 끝이다.

REVIEW

아직 코테 문제는 이런식으로 풀면 되곘군 하는 로직은 생각이 나는데 그걸 제대로 구현하는 방법을 잘 모르는 느낌이다. 열심히 훈련하면 점점 더 나아지지 않을까 ㅠ

이력서리뷰

이력서 작성을 해보았다.
이력서에서 중요한 것

• 정성적인 부분은 나중에 간략하게 적을것(전 ~~ 잘하는 사람 노력 많이한다. 어쩌구 저쩌구)
• 소개 부분에 나의 핵심 역량을 표현한다.
• 내가 어떤 직무를 하고싶은지 확실하게 적어놓는다.(상단부에 백엔드 개발자 혹은 프론트엔드 개발자)
• 프로젝트 부분에는 개요, 담당업무, 기여한 점이 눈에 띄도록 작성한다.
• 개발과 필요없는 부분은 과감하게 빼버리자!

REVIEW

내가 이력서를 작성했을 떄 놓쳤던 부분이다. 잘 썻다고 생각했는데 점검해보니 생각보다 개판이 부분이 너무 많았음 ㅋ

포트폴리오 리뷰

• 목차, 간단한 설명을 추가하면 면접관이 보기에 좀 더 편리할 것 같다.
• 지원하려는 기업 성질에 맞춰서 프로젝트를 배치한다.
  난 기존에 시간 순서로 프로젝트를 배치했는데 이게 훨씬 더 좋은 방법인것 같다. 글은 읽을 수록 피곤해지는게 사실이니까 가장 처음 들어오는 글이 눈에 잘 띄는 법이다.

REVIEW

생각보다 개판은 아니었지만 면접관의 눈에 잘 띄게 하는 방법을 미처 생각하지 못했던 것 같다.