TIL 220824

알고리즘

백준

1. 1932 정수 삼각형

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const input = fs.readFileSync(filePath).toString().trim().split('\n');

const n = Number(input[0]);
const graph = input.slice(1).map(element => element.split(' ').map(element => Number(element)));

graph.forEach((element) => {
    if (element.length < n) {
        currentElementLength = element.length
        
        for(let i = 0; i < n - currentElementLength; i++) {
            element.push(0);
        }
    }
})

function solution(n, graph) {
    const dp = new Array();
    for (let i = 0; i < n; i++) {
        dp.push(new Array(n).fill(0));
    }
    
    dp[0][0] = graph[0][0];
    
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (j === 0) {
                dp[i][j] = dp[i - 1][j] + graph[i][j];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + graph[i][j];
            }
        }
    }
    
    return Math.max(...dp[dp.length - 1]);
}

const result = solution(n, graph);
console.log(result);

역시 DP는 어렵다! 이 정도도 잘 못 풀다니... 감을 잘 못잡은 것 같다. 처음에 DFS로 풀어서 제출했는데 메모리 초과가 떴다. 도저히 모르겠어서 질문들을 보니 DP로 풀어야 한다는 것을 알게 됐다. 문제 유형도 아는 것이 중요하다는 걸 알게 됐고, DP는 확실히 많이 풀어봐야겠다.

현재 값의 입장에서는 대각선 윗 왼쪽과 대각선 윗 오른쪽으로 내려오던 것들 중 큰 것을 고르면 된다. 이건 꼭 다음에 다시 풀어봐야겠다.

프로그래머스

1. 소수 찾기 (Level 2)

function isPrime(currentString) {
    const currentNumber = Number(currentString);
    
    if (currentNumber <= 1) {
        return false;
    }
    
    for (let i = 2; i <= parseInt(Math.sqrt(currentNumber)); i++) {
        if (currentNumber % i === 0) {
            return false;
        }
    }
    
    return true;
}

function DFS(currentValue, numbersArray, visited, result) {
    for (let i = 0; i < numbersArray.length; i++) {
        if (visited[i] === 0) {
            if (isPrime(currentValue + numbersArray[i]) === true) {
                result.add(Number(currentValue + numbersArray[i]));
            }
            visited[i] = 1;
            DFS(currentValue + numbersArray[i], numbersArray, visited, result);
            visited[i] = 0;
        }
    }
}

function solution(numbers) {
    const numbersArray = Array.from(numbers);
    const visited = new Array(numbersArray.length).fill(0);
    const result = new Set();
    
    DFS('', numbersArray, visited, result);   
    console.log(result);
    
    return Array.from(result).length;
}

풀긴 풀었는데 어떻게 풀었지? 싶은 느낌이다. 순열과 조합에 대해 확실히 알아놓을 필요가 있을 것 같다.

리트코드

1. 70 Climbing Stairs

var climbStairs = function(n) {
    if (n === 1) {
        return 1;
    }
    
    const dp = new Array(n + 1).fill(0);
    dp[1] = 1;
    dp[2] = 2;
    
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
};