카카오 코딩테스트 1,2 차가 끝난 후 오랜만에 풀어보는 leetcode.

뭐 부터 해야할지 막막했는데, 그 전에 연습 해두려고 했던게 생각나서 체계를 잡을 수 있었다.

백트래킹

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 알고리즘을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다.

• DFS

  가능한 모든 경로(후보)를 탐색합니다. 따라서 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지못합니다.
  

• 백트래킹

  해를 찾아가는 도중 지금의 경로가 해가 될지 않을 것 같으면 그 경로를 더이상 가지 않고 되돌아갑니다.

  → 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 , 불필요 경로를 차단하게 되어 효율적. N!의 경우 지수함수의 시간을 필요로 하므로 처리 불가능할 수 있다. 가지치기를 잘해야함.
  

정리하자면, 특정한 조건을 만족하는 경우만 살펴보는 기법을 말한다. 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것을 말함

문제풀이에서는 → DFS 등으로 모든 경우의 수를 탐색하는 과정에서 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고 그러한 상황일 경우 탐색을 중지.

결정 문제 (Decision problem)
결정 문제란 여러 문제들 중 Yes or No로 답이 나오는 문제를 의미합니다.

Sum of All Subset XOR Totals

조합을 구한다음 -> 조합의 XOR을 구해 list에 저장하고, 이를 모두 합산 값을 리턴하면 된다.

첫 풀이

/**
 * @param {number[]} nums
 * @return {number}
 */
var subsetXORSum = function(nums) {
    let array = []
    for(let i=0;i<=nums.length;i++){
          
        const comb = DFS(nums,i,0);
        
        if(comb){
            
            comb.forEach(item=>{
                array.push(item.reduce((a,b)=>a^b))
            })
                       
        }else{
                
            array.push(0);
                
        }
    }
    
    return array.reduce((a,b)=>a+b)
    
    function DFS(nums,i,start){
        
        if(i === 0){
            return null;
        }
        
        const array = []
        
        // start 지점부터 찾는다. (start 지점 이전 것들은 유망하지 않다) 조합으로서 유망할 뒷 자식들을 
        for(let j=start;j<nums.length;j++){
          
          // 자식에서 구한 데이터를 가지고
            const data = DFS(nums,i-1,j+1);
            if(data){
              // 내 데이터에 붙인다.
              // [[0],[1],[2]] 가 오면 -> [[현재,0],[현재,1],[현재,2]] 가 된다.
//                 i !== 1;
               data.forEach(el => array.push([nums[j],...el]));                
            }else{
              
//                 i === 1;                
               array.push([nums[j]]); 
                
            }
        
        }
        
        return array;
        
        
        
        
    }
};

좋은 풀이

레벨은 인덱스를 의미한다. 한 레벨에 두개의 자식이 존재하는 이진트리가 되는데, 왼쪽으로 뻗어나가면 해당 레벨 (인덱스)를 포함하는 것이고, 오른쪽으로 뻗어나가면 포함하지 않는 것.

내일 다시 풀어보도록 하자.

/**
 * @param {number[]} nums
 * @return {number}
 */
var subsetXORSum = function(nums) {
    return DFS(nums,0,0);
    function DFS(nums,index,current){
        
        if(index === nums.length) return current;
        
        const computeCurIndex = DFS(nums,index+1,current ^ nums[index]);
        
        const dontComputeCurIndex = DFS(nums,index+1,current);
        
        return computeCurIndex + dontComputeCurIndex;
        
    };
};

Ref

• [백트래킹]