프로그래머스 알고리즘 복습하기

최적해를 구해야 되는 문제, 완전 탐색을 해야 되는 문제는 개인적으로 어려워하는 유형이라 이미 풀어봤던 문제일지라도 다시 풀어보면서 복습해야 될 것 같다. 틈틈이 업데이트하자!

 

앞으로는 github에 업데이트하기: https://github.com/jaemin-jeong/algorithm-programmers

jaemin-jeong/algorithm-programmers

 

완전 탐색, DFS, BFS

1. 타겟 넘버 https://programmers.co.kr/learn/courses/30/lessons/43165 (O)
모든 경우를 탐색해 계산 결과가 타겟과 동일한 경우의 수를 찾는 문제이기 때문에 이전과 마찬가지로 DFS로 풀이했다.

// 이전에 작성한 코드
function solution(numbers, target) {
    var answer = 0;
    let index = 0, calc = 0;
    
    const dfsRecursion = (i, sum) => {
        while(i < numbers.length){
            i = i + 1
            dfsRecursion(i, sum+numbers[i - 1]);
            dfsRecursion(i, sum-numbers[i - 1]);
        }
        return sum === target ? answer++ : answer;    
    }
    
    dfsRecursion(index, calc);
    return answer;
}

// 복습 코드
function solution(numbers, target) {
    let answer = 0;
    search(0, 0);
    
    function search(sum, depth){
        if(depth === numbers.length){
            return sum === target ? answer++ : answer;
        }
        search(sum + numbers[depth], depth + 1);
        search(sum - numbers[depth], depth + 1);
    }
    
    return answer;
}

2. 네트워크 https://programmers.co.kr/learn/courses/30/lessons/43162 (O)
모든 경우를 탐색해 연결된 컴퓨터를 네트워크로 묶은 후 총 네트워크 개수를 구하는 문제이기 때문에 DFS로 풀이했다. 예전에는 stack으로 해결하는 게 더 쉽게 느껴졌는데, pseudo-code를 다시 작성하다보니 이번 복습에서는 재귀로 풀게되었다.

// 이전 코드
function solution(n, computers) {
    let answer = 0, stack = [], i = 0, count = 0, passed = [];
    while(count < n){
        for(let j = 0; j < n; j++){
            if(computers[i][j] === 1 && !passed.includes(j)){
                stack.push(j);
                passed.push(j);
            };
        };
        if(stack.length > 0){
            i = stack.pop();
        }
        if(stack.length === 0){
            answer++;
            i = 0;
            while(passed.includes(i)){
                i++;
            }
        }
        count++;
    }
    return answer;
}

// 복습 코드
function solution(n, computers) {
    let answer = 0, check = new Map();
    for(let i = 0; i < n; i++){ 
        check.set(i, true) 
    };

    const search = (com) => {
        check.set(com, false);
        computers[com].forEach((v, i) => {
            if(check.get(i) && v === 1) search(i);
        });
        return;
    }
    
    for(let i = 0; i < n; i++){
        if(check.get(i)){ 
            search(i);
            answer++;
        };
    }
    
    return answer;
}

3. 카펫 https://programmers.co.kr/learn/courses/30/lessons/42842 (O)

완전 탐색 문제로서 모든 경우를 체크하면 된다. 이전과 동일하게 브루트 포스(Brute-force) 알고리즘으로 문제를 해결했다. 달라진 점이라면  ①변수명을 보다 직관적으로 작성한 것 ②제약조건(가로길이 >= 세로 길이, 갈색 테두리 줄은 1)을 통해 최대/최소값을 구하여 조건식에 부합하는지 판단하고 판단 여부에 따라 반복문을 도는 로직으로 구현하여 코드 길이는 줄이고 가독성은 높였다는 것이 있겠다.

// 이전 코드
function solution(brown, yellow) {
    let answer = [];
    let row, col;
    row = Math.ceil(Math.sqrt(brown + yellow));

    if(Math.sqrt(brown + yellow) % 1 === 0){
        answer[0] = row;
        answer[1] = row;        
    }else{
        for(let i = row - 2; i <= yellow; i++){
            col = yellow / i;
            if((i + 2) * (col + 2) === brown + yellow){
                row = i;
                answer[0] = row + 2;
                answer[1] = col + 2;
                break;
            }

        }        
    }

    return answer;
}

// 복습 코드
function solution(brown, yellow) {
    let answer = [];

    let yellowMinX = Math.ceil((brown - 4) / 4);
    let yellowMaxY = Math.floor((brown - 4) / 4);
    
    while (true) {
        if(yellowMaxY * yellowMinX === yellow) {
            answer.push(yellowMinX + 2);
            answer.push(yellowMaxY + 2);
            return answer;
        }
        yellowMinX++;
        yellowMaxY--;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/43163 ()
https://programmers.co.kr/learn/courses/30/lessons/43164 ()

https://programmers.co.kr/learn/courses/30/lessons/42840 ()
https://programmers.co.kr/learn/courses/30/lessons/42839 ()

 

탐욕법

1. 큰 수 만들기 https://programmers.co.kr/learn/courses/30/lessons/42883 ()

탐욕법(greedy algorithm)은 모든 문제의 해결 방안은 아니다. 탐욕법으로 풀었을 때 최적의 해를 구하지 못하는 경우도 있기 때문에, 탐욕법으로 일단 풀어보고 안되면 빨리 다른 방법으로 해결하는게 시간을 아끼는 방법이다. 이 문제를 단순하게 생각하면,  ①작은 수 순서대로 정렬하고 k개를 제거한다 ②큰 수 부터 차례대로 이어 붙이면 큰 수가 된다.

// 이전 코드
function solution(num, k) {
    let answer = [];
    let i = 0;
    let rest = num.length - k;
    let number = [...new Set(num.split('').sort((a, b) => b - a))];
    
    while(rest > 0){
        let delStart = (num.indexOf(number[i])) + 1;
        answer.push(number[i]);
        if(!num.includes(number[i]) || num.slice(delStart).length < rest - 1){
            answer.pop();
            i++;
            continue;
        }
        num = num.slice(delStart);
        rest--;
        i = 0; 
    }
    
    return answer.join('');
}

 

 

 

동적 계획법

https://programmers.co.kr/learn/courses/30/lessons/43105 ()
https://programmers.co.kr/learn/courses/30/lessons/42895 ()

 

스택/큐

1. 다리위를 지나는 트럭 programmers.co.kr/learn/courses/30/lessons/42583(O)

큐를 이용하면 되는 문제이고, 이번 풀이에서는 불필요한 변수 선언이나 과정을 최대한 피해 코드를 작성하려 노력했다.

// 이전 코드
function solution(bridge_length, weight, truck_weights) {
    let answer = 0;
    let done = [];
    let onBridge = [];
    let restTime = [];
    let count = truck_weights.length;
    while(done.length < count){
        let tmp = 0;
        if(truck_weights.length > 0){
            tmp = truck_weights.shift();
            onBridge.push(tmp);
            restTime.push(bridge_length); 
        }

        let sum = onBridge.reduce((a, b) => { a += b; return a; })
        if(weight >= sum){
            restTime = restTime.map(t => {
                t--;
                return t;
            });
            answer++;
            if(restTime[0] <= 0){
                restTime.shift();
                let d = onBridge.shift();
                done.push(d);
            }
        }else{
            if(tmp !== 0){
                truck_weights.unshift(tmp);   
                onBridge.pop();
                restTime.pop();
                tmp = 0;
            }
            while(restTime[0] > 0){
                restTime = restTime.map(t => {
                    t--;
                    return t;
                });
                answer++;
            }
            restTime.shift();
            let d = onBridge.shift();
            done.push(d);
        }
    }
    return answer + 1;
}

// 복습 코드
function solution(bridge_length, weight, truck_weights) {
    let answer = 0;
    let queue = [];
    let lenList = [];
    let curWeight = 0;

    while (truck_weights.length > 0 || queue.length > 0) {
        if (truck_weights[0] && weight >= curWeight + truck_weights[0]) {
            let truck = truck_weights.shift();
            // queue에 트럭 추가, 현재 무게에 트럭 무게 추가
            queue.push(truck);
            curWeight += truck;
            // lenList 다리에 오른 트럭이 다리를 벗어나기까지 남은 거리 추가
            lenList.push(bridge_length);
        }
        lenList = lenList.map(len => len - 1);
        answer++;

        // 남은 거리가 0이면 lenList, queue에서 빼내기
        if (lenList[0] === 0){
            lenList.shift();
            curWeight -= queue[0];
            queue.shift();
        }
    }
    answer++;
    return answer;
};