[TIL] TRIE/ 최단거리

jjyung·2021년 8월 9일
0

TIL

목록 보기
2/6

1. 동전 바꿔주기 (냅색 알고리즘)

  • t원의 지폐를 동전으로 바꿔주기
  • 동전 개수는 각각 다르다
  • 지폐를 동전으로 교환하는 방법의 가지수를 계산하기
function solution(t, coins) {
    let answer = 0;
    let dy = Array.from({length:t+1},()=>0);

    dy[0]=1;
    for(let [p,n] of coins){
        for(let j=t; j>=1; j--){
            for(let k=1; k<=n; k++){
                if(j-(p*k)<0) break;
                dy[j]+=dy[j-(p*k)];
            }
        }
    }
    answer= dy[t];
    return answer;
}

2. 플로이드 와샬 알고리즘

  • n개의 도시가 주어질 때 모든 도시에서 도시로 이동하는데 쓰이는 최소비용 구하기
function solution(n,edges) {
    let answer = 0;
    let dist = Array.from(Array(n+1), ()=>Array(n+1).fill(1000));
    //자기 자신에서 자기 자신까지 가는거리
    for(let i=1; i<=n; i++) dist[i][i]=0;
    //가중치연결
    for(let [a,b,c] of edges){
        dist[a][b]= c;
    }
    //
    for(let k=1; k<=n; k++){
        for(let i=1; i<=n; i++){
            for(let j=1; j<=n; j++){
                dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    
    console.log(dist);
    return answer;
}

3. 회장뽑기

  • 가장 작은 수를 가지고 있는 사람이 회장
  • 회장 후보 점수와 회장 후보수를 출력하기
function solution(n, edges) {
    let answer = [];
    let dist = Array.from(Array(n+1), ()=>Array(n+1).fill(1000));
    let score = Array.from({length:n+1}, ()=>0);

    for(let i=1; i<=n; i++) dist[i][i]=0;
    for(let [a,b] of edges) {
        dist[a][b] = 1;
        dist[b][a] = 1;
    }

    for(let k=1; k<=n; k++){
        for(let i=1; i<=n; i++){
            for(let j=1; j<=n; j++){
                dist[i][j] = Math.min(dist[i][j], dist[i][k]+dist[k][j]);
            }
        }
    }

    let ps = 1000;
    for(let i=1; i<=n; i++){
        for(let j=1; j<=n; j++){
            score[i] = Math.max(score[i], dist[i][j]);
        }
        ps = Math.min(ps, score[i]);
    }
    answer.push(ps);
    let cnt = 0;
    for(let i=1; i<=n; i++){
        if(score[i]===ps) cnt++;
    }
    answer.push( cnt);
    
    return answer;
}

4. Trie 자료구조

class Node{
    constructor(){
        this.end = false;//항상 false로
        this.child = {}//항상 자식이 있으니까 객체만들어두기
    }
}

class Trie{
    constructor(){//새로운 객체생성
        this.root = new Node();
    }
    insert(word){//객체생성후 단어를 넘김 (새롭게 생성되면 항상 새로 시작됨)
        let cur = this.root;//출발점을 가리킴(root)
        for(let x of word) {//키 값이 있나 확인중 , 없으면 자식으로 이동하면서 새로운 루트 만듦 (book에서 b는 부모, ook는 자식으로감)
            if(cur.child[x] === undefined){ // cur이 처음에 루트 -> 나중에 자식 가리킴
                cur.child[x] = new Node(); // 초기화는 false
            }
            cur = cur.child[x];
        }
        cur.end = true; // 단어의 끝 노드는 true로 반환해두기
    }

    search(word){//Root의 child로 값이 없으면 없는 것임
        let cur = this.root;
        for(let x of word){
            if(cur.child[x] === undefined) return false;
            cur=cur.child[x];
        }
        return cur.end;//어떤 단어의 중간까지 밖에 없으면 그냥 false가 return 됨
    }
    prefixS(str){//접두어가있으면 true, 없으면 false
        let cur = this.root;
        for(let x of str){
            if(cur.child[x]===undefined) return false;
            cur=cur.child[x];
        }
        return true;
    }
}

5. 자동완성

class Node{
    constructor(){
        this.end = false;
        this.child = {};
        this.cnt = 0; // 카운팅할 애
    }
}

class Trie {
    constructor(){
        this.root = new Node();
    }

    insert(word) { 
        let cur = this.root;
        for(let x of word){
            if(cur.child[x] === undefined) {
                cur.child[x] = new Node();
            }
            cur = cur.child[x];
            cur.cnt++;
        }
        cur.end = true;
    }

    getCount(word){
        let cur = this.root;
        let Count=0;
        for(let x of word){
            Count++;
            cur = cur.child[x];
            if(cur.cnt === 1) return Count;
        }
        return Count;
    }

}

function solution(words) {
    let answer = 0;
    let mT = new Trie();
    for(let word of words) {
        mT.insert(word);
    }
    for(let word of words){
        answer+=mT.getCount(word);
    }
    return answer;
}
profile
🏃‍♀️movin' forward, developer

0개의 댓글