[취업준비일지] - 31

1.트라이(Trie)는 트리형 자료구조로 문자열에 특화되어있다.
트라이는 공백 루트에서 시작해 "a"~"z"까지의 분기(물론 존재할 경우에만 추가된다) 후 다시 거기에서 분기가 되는 방식으로 진행된다.
'apple'를 검색한다고 할 경우 루트에서 a를 찾고 p를 찾은 다음
p를 찾고 l을 찾고 e를 찾아 진행하는 형태로 O(M(문자열 길이))의 시간복잡도를 가지고 있다.

시간복잡도면에서는 우수하지만
공간복잡도면에서는 포인터 배열의 크기 때문에 큰 손실이 있다고 한다.

하지만 미리 포인터에 맞는 배열을 크기대로 선언할 필요가 없는 js의 경우가 궁금했는데 생각보다 메모리에 큰 손실은 딱히 체감되지 않는 것 같았다. 

또한 js와 타 언어의 차이도 없어 보였는데 치명적이라는 곳과 다른 곳의 기준도 많이 달랐다.

즉 최종 메모리는 O(포인터 크기 * 포인터 배열 개수 * 트라이에 존재하는 총 노드의 개수)가 된다.
https://www.crocus.co.kr/1053

O(N*M)
https://dev-dream-world.tistory.com/78

 

(W*n)(모든 문자열의 글자가 모두 겹치지 않는 최악의 경우), where W is average number of characters per word and n is total number of words in the Trie.
https://stackfull.dev/trie-in-javascript-the-data-structure-behind-autocomplete

 

문자열이 글자당 O(M)의 시간복잡도를 가지고 있고
이게 N개만큼 있다면 O(N*M) 영어판과 비교하면 (W*n)의 공간복잡도를 가지는 것 같은데 이게 왜 치명적이라는지 이해하기 힘들다.

심지어 본인이 제출한 map을 이용한 방식과 trie를 사용한 방식의
시간 차이는 현저(5배가량)하지만 메모리 차이는 큰 차이가 안나는 것(10%미만)을 볼 수 있었다.

아래(map), 위(trie)라고 한다.  https://www.crocus.co.kr/1053

문제가 생기면 주저없이 trie를 사용해봐야겠다.
(메모리 초과가 생기면 그때 추가적으로 알아보자)





(1).백준 3059 등장하지 않는 문자의 합은 정답처리가 되지 않는다.
런타임 에러 EACCES라고 하는데 검색해보니 기존에 사용하는 방법으로는
input을 받아올 수 없는 문제가 있었다.
readline방식을 통해 문제를 해결할 수 있었다..

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let input = [];

rl.on('line', function (line) {
  input.push(line)
})
  .on('close', function () {
    let result = []
    for(let i = 1 ; i < input.length ; i++){
        let arr = new Array(26).fill(1)
        let sum = 0 
        for(let j = 0 ; j < input[i].length ; j++){
            if(arr[input[i][j].charCodeAt()-65]){
                arr[input[i][j].charCodeAt()-65] = 0
            }
        }
        for(let i = 0 ; i < arr.length ; i++){
            if(arr[i]){
                sum += i+65
            }
        }
        
        result.push(sum)
    }
    
    console.log(result.join('\n'))
  process.exit();
});

(2).프로그래머스 기사단원의 무기는 조건이 복잡해보이는 문제였는데
기사단원의 숫자 n이 주어질 경우 1~n까지의 n명이 생기는 것이고
(10이면 1,2,3,4,5,6,7,8,9,10)
각각의 기사단원은 본인의 약수의 개수만큼의 공격력을 가진 무기 착용이 가능하다.(그만큼의 공격력이라고 봐도 됨)
하지만 국제 협약으로 일정 파워(조건) 이상은 일정 이하로 제한되고(조건)
10만 이하의 숫자를 줄 때 총 필요한 철의 무게(파워 합과 같다)를 구하는 문제였다.

일단 1~10만까지 각자 약수의 갯수를 모두 구하고
약수의 갯수가 제한을 초과한 경우 정해진 규정값을 더하며
제한초과가 아닌 경우는 그냥 더해 총 합을 출력하면 되는 문제다.

이를 위해 10만의 제곱근인 3161을 기준으로 소수들을 정렬한 다음
while문을 통해 2부터 나눠 소인수분해를 하고
각 소수의 갯수마다 +1을 한 다음 곱하는 방식으로
약수의 갯수를 구할 수 있었고
조건에 맞춰 더해 문제를 해결할 수 있었다.

function solution(number, limit, power) {
    let answer = 0;
    let arr = new Array(3162).fill(0)
    for(let i = 2 ; i < 3162 ; i++){
        arr[i] = i
    }
    for(let i = 2 ; i < 3162 ; i++){
        let n = 2
        while(i*n < 3162){
            arr[i*n] = 0
            n++
        }
    }
    arr = arr.filter(el => el !== 0)
    
    for(let i = 1 ; i <= number ; i++){
        let obj = {}
        let n = i
        let powerNow = 1
        while(n !== 1){
            let isChange = n
            for(let j = 0 ; j < arr.length ; j++){
                if(n%arr[j] === 0){
                    n /= arr[j]
                    if(obj[arr[j]]){
                        obj[arr[j]]++
                    }
                    else{
                        obj[arr[j]] = 1
                    }
                    break
                }
            }
            if(isChange === n){
                obj[n] = 1
                n /= n
            }
        }
        for(let key in obj){
            powerNow *= (obj[key]+1)
        }
        if(powerNow <= limit){
            answer += powerNow
        }
        else{
            answer += power
        }
    }
    
    return answer;
}

(3).백준 1991 트리 순회는 전위, 중위, 후위순회결과를 구하는 문제였다.
직접 트리를 구성해보지는 않았기 때문에 class로 구현해야 하나 고민했지만
다행히 객체로도 편하게 해결할 수 있었다.

let input = `7
A B C
B D .
C E F
E . .
F . G
D . .
G . .`.split('\n')

let obj = {}
let start = ''
let middle = ''
let end = ''
for(let i = 1 ; i < input.length ; i++){
    let [a,b,c] = input[i].split(' ')
    obj[a] =[b,c]
}

function recurtion(n) {
    if(n === '.') return
    start += n
    recurtion(obj[n][0])
    middle += n
    recurtion(obj[n][1])
    end += n
}

recurtion("A")

console.log(start)
console.log(middle)
console.log(end)

(4).백준 11725 트리의 부모 찾기는 트리 내부의 정점의 연결(순서섞임)을 받아 트리형태로 만든 다음 각 숫자의 부모노드를 순서대로 출력하는 문제였다.

let input = `12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12`.split('\n')

let obj = {}
let arr = []

for(let i = 1 ; i < input.length ; i++){
    let [a,b] = input[i].split(' ').map(Number)
    if(obj[a]){
        obj[a].push(b)
    }
    else{
        obj[a] = [b]
    }
    if(obj[b]){
        obj[b].push(a)
    }
    else{
        obj[b] = [a]
    }
}

function recurtion(n) {
    if(obj[n].length === 1 && n !== 1){
        return 
    }
    for(let i = 0 ; i < obj[n].length ; i++){
        if(obj[n][i] !== arr[n]){
            arr[obj[n][i]] = n
            recurtion(obj[n][i])
        }
    }
}

recurtion(1)

console.log(arr.slice(2).join('\n'))

(5).백준 1520 내리막 길은 현재 칸보다 작은 칸으로만 상하좌우로 이동 가능한 상태에서 목적지까지 갈 수 있는 경우의 수를 구하는 문제였다.

처음에는 bottom up 방식으로 진행했는데 
일반적 문제와는 다르게 역주행이 가능한 경로가 있었기 때문에
역주행 경로는 처리되지 않는 심각한 문제가 있었다.

let input = `4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10`.split('\n')

let arr = []
let [x, y] = input[0].split(' ').map(Number)
let matrix = input.slice(1)

for(let i = 0 ; i < x ; i++){
    arr.push(new Array(y).fill(0))
    matrix[i] = matrix[i].split(' ').map(Number)
}
arr[0][0] = 1

for(let i = 0 ; i < x ; i++){
    for(let j = 0 ; j < y ; j++){
        if(matrix[i+1] && matrix[i][j] > matrix[i+1][j]){
            arr[i+1][j] += arr[i][j]
        }
        if(matrix[i][j] > matrix[i][j+1]){
            arr[i][j+1] += arr[i][j]
        }
        if(matrix[i-1] && matrix[i][j] > matrix[i-1][j]){
            arr[i-1][j] += arr[i][j]
        }
        if(matrix[i][j] > matrix[i][j-1]){
            arr[i][j-1] += arr[i][j]
        }
    }
}

console.log(arr)

 

 

그래서 이번에는 모든 경로는 지나가는 방식으로 문제를 해결했으나
모든 경로를 개별적으로 탐색했기 때문에 잘 진행되다가
큰 테스트케이스를 만났는지 중간에 시간초과로 터져버렸다.

let input = `4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10`.split('\n')
let arr = []
let [x, y] = input[0].split(' ').map(Number)
let matrix = input.slice(1)
let sum = 0
for(let i = 0 ; i < x ; i++){
    arr.push(new Array(y).fill(0))
    matrix[i] = matrix[i].split(' ').map(Number)
}
arr[0][0] = 1

recurtion(0,0)

function recurtion(a,b) {
    if(a === x-1 && b === y-1){
        sum++
        return
    }
        if(matrix[a+1] && matrix[a][b] > matrix[a+1][b]){
            recurtion(a+1,b)
        }
        if(matrix[a][b] > matrix[a][b+1]){
            recurtion(a,b+1)
        }
        if(matrix[a-1] && matrix[a][b] > matrix[a-1][b]){
            recurtion(a-1,b)
        }
        if(matrix[a][b] > matrix[a][b-1]){
            recurtion(a,b-1)
        }
}

console.log(sum)

 

 

결국 공통되는 부분을 찾아 top-down 방식으로 내려가야만 했다.
전반적인 구조는 큰 차이가 없지만 앞에서 뒤로 가는게 아닌
뒤에서 앞으로 떙겨오는 구조라는 차이가 있으며
뒤에서 땡기기 위해서는 데이터가 있어야 하니 땡겨올 부분에서 
다시 재귀처리를 진행해 목적지에서부터 내려가는 방식으로 구현됐다.

let input = `4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10`.split('\n')

let arr = [] //dp인데 처음 구현은 경로라 arr로 진행했다.
let [x, y] = input[0].split(' ').map(Number) //x,y축(반대)
let matrix = input.slice(1) //map이라고도 부를 수 있겠다
let sum = 0 //경로 합 위에서 쓴 내용이고 여기서는 필요없다...
for(let i = 0 ; i < x ; i++){ //arr(dp)세팅 및 matrix 문자열 -> 숫자
    arr.push(new Array(y).fill(-1))
    matrix[i] = matrix[i].split(' ').map(Number)
}
arr[x-1][y-1] = 1 //출발지가 아닌 목적지부터 값을 땡겨오니 1로 초기화

function recurtion(a,b) {
    if(arr[a][b] !== -1){ //이미 지정된 경로일 경우 계산 안하고 값만 받아오기
        return arr[a][b]
    }
    let sum = 0 //각 방위별로 진행해 값을 받아오기
    //지나온 경로 역행은 걱정할 필요가 없는게 내리막으로 진행이기 때문에
    //a -> b -> a과 같은 경우는 일어날 수 없다.
    if(matrix[a+1] && matrix[a+1][b] >= 0 && matrix[a][b] > matrix[a+1][b]){
        sum += recurtion(a+1,b)
    }
    if(matrix[a][b+1] >= 0 && matrix[a][b] > matrix[a][b+1]){
        sum += recurtion(a,b+1)
    }
    if(matrix[a-1] && matrix[a-1][b] >= 0 && matrix[a][b] > matrix[a-1][b]){
        sum += recurtion(a-1,b)
    }
    if(matrix[a] && matrix[a][b-1] >= 0 && matrix[a][b] > matrix[a][b-1]){
        sum += recurtion(a,b-1)
    }
    arr[a][b] = sum //경로의 합 할당(이제 이 위치가 필요하면 맨 위에서 return된다)
    return sum
}

console.log(recurtion(0,0)) //재귀 호출