아래 글은 오늘 강의를 들은 자료구조/알고리즘 수업의 내용과 내가 푼 방식, 강사님이 푼 방식이다. 문제의 저작권 때문에 간략하게 정리해서 올리는 점 참고해 주시기 바란다.

[트리, 이분검색(결정알고리즘)]

친구인가? (Disjoint-Set : Union&Find)

친구관계가 순서쌍으로 주어지면 특정 두 명이 친구인지 판별하여라.

📌 내가 푼 방법

function solution(n, nums, s1, s2) {
    let unf = [];
    for(let i = 0; i < n+1; i++) {
        unf[i] = i;
    }

    for(let i = 0; i<nums.length; i++) {
        Union(nums[i][0], nums[i][1]);
    }

    function Union(a, b) {
        unf[a] = b;
    }

    function Find(v) { // unf에 있는 인덱스와 값이 같은 경우에만 return! (매개변수의 집합 번호를 찾아줌)
        if(v===unf[v]) return v;
        else {
            unf[v] = Find(unf[v]); // unf 배열에 1번인덱스에 2, 2번인덱스에 3이 있으므로 알아서 재귀가 돌아감
            return unf[v]; // 이렇게 저장시켜서 하면 더 빠르게 리턴 받을 수 있음
        } 
    }
    console.log(unf);

    if(Find(s1) === Find(s2)) return "YES";
    else return "No";
}

console.log(solution(9, [[1, 2], [2, 3], [3, 4], [1, 5], [6, 7], [7, 8], [8, 9]], 3, 8));

강사님 설명 들으면서 푼거 --> Union함수를 저렇게 쓰면 안되고 Find함수로 확인 후 다른 경우에 바꾸어 주어야 함!!

📌 강사님 방법

function solution(n, nums, s1, s2) {
    let answer = "YES";
    let unf = Array.from({length: n+1}, (v, i) => (i))

    function Find(v) { // unf에 있는 인덱스와 값이 같은 경우에만 return! (매개변수의 집합 번호를 찾아줌)
        if(v===unf[v]) return v;
        else return unf[v] = Find(unf[v]); // unf 배열에 1번인덱스에 2, 2번인덱스에 3이 있으므로 알아서 재귀가 돌아감, 이렇게 저장시켜서 하면 Find함수 호출 시 더 빠르게 리턴 받을 수 있음
    }

    function Union(a, b) {
        let fa = Find(a);
        let fb = Find(b);
        if(fa!==fb) unf[fa] = fb;
    }
    for(let [a, b] of nums) {
        Union(a, b);
    }
    if(Find(s1) !== Find(s2)) return "NO";

    return answer;

}

console.log(solution(9, [[1, 2], [2, 3], [3, 4], [1, 5], [6, 7], [7, 8], [8, 9]], 3, 8));

서로 자료구조를 통해 만들어 두어서 같은 집합인지 확인하면 됨 --> Union & Find
unf배열을 만들고, 인덱스 번호는 학생번호, 안에 들어가 있는 값은 집합번호로 설정
fa, fb로 find(1), find(2)의 값을 설정하고 둘의 집합 번호가 다른 경우 unf[fa] = fb로 설정을 해줌!
이러한 문제는 유니온, 파인드 함수로 풀 수 있는데 Union의 순서쌍의 배열을 받아서 순서쌍 안에 있으면 뒤에 있는 원소를 값으로 unf의 값을 변경시켜주는 것이고 Find함수의 경우 앞의 Union으로 변경된 unf배열을 가지고 같은 집합인지 파악하는 함수이다.


원더랜드(최소스패닝트리 : 크루스칼, Union&Find 활용)

매개변수에 도시의 개수와 edges의 정보(a도시, b도시, 유지비용)이 주어지면 모든 도시를 연결하면서 드는 최소비용을 반환하여라

📌 내가 푼 방법

function solution(n, edges) {
    let answer = 0;
    let unf = Array.from({length: n+1}, (v, i) => (i));

    edges.sort((a, b) => a[2] - b[2]);

    function Find(v) {
        if(v === unf[v]) return v;
        else return unf[v] = Find(unf[v]);
    }

    function Union(a, b) {
        let fa = Find(a);
        let fb = Find(b);
        if(fa !== fb) {
            unf[fa] = fb;
            return true;
        }
        else return false;
    }

    // 간선 개수 만큼 for문 돌면 됨!
    for(let [a, b, c] of edges) {
        if(Union(a, b)) answer += c;
        else continue;
    }
    
    return answer;
}

console.log(solution(9, [[1, 2, 12], [1, 9, 25], [2, 3, 10], [2, 8, 17], [2, 9, 8], [3, 4, 18], [3, 7, 55], [4, 5, 44], [5, 6, 60], [5, 7, 38], [7, 8, 35], [8, 9, 15]]));

📌 강사님 방법

function solution(n, edges) {
    let answer = 0;
    let unf = Array.from({length: n+1}, (v, i) => (i));

    edges.sort((a, b) => a[2] - b[2]);

    function Find(v) {
        if(v === unf[v]) return v;
        else return unf[v] = Find(unf[v]);
    }

    function Union(a, b) { // 여기에선 Union함수 사용안함
        let fa = Find(a);
        let fb = Find(b);
        if(fa !== fb) unf[fa] = fb;
    }

    // 간선 개수 만큼 for문 돌면 됨!
    for(let [a, b, c] of edges) {
        let fa = Find(a);
        let fb = Find(b);
        if(fa!==fb) { // 이 부분이 다른점인데 다른 경우에만 answer에 포함시키고 
         	 // 굳이 Union 함수를 호출할 필요 없이 unf[fa] = fb를 여기서 넣어준다.
            answer+=c;
            unf[fa] = fb;
        }
    }
    
    return answer;
}

console.log(solution(9, [[1, 2, 12], [1, 9, 25], [2, 3, 10], [2, 8, 17], [2, 9, 8], [3, 4, 18], [3, 7, 55], [4, 5, 44], [5, 6, 60], [5, 7, 38], [7, 8, 35], [8, 9, 15]]));

크루스칼 --> 그리디 기법
간선을 오름차순으로 정렬한 뒤 젤 작은것 부터 선택해서 가져가면 됨!
선택이 된것이면 Union으로 한 집합! 선택이 안된것이면 아직 각자 번호를 가진 집합
그리디 기법으로 선택을 해가다가 간선 선택 시 회로(트리가 사이클이 있는 상태)가 되면 안됨! --> find로 두 집합이 같으면 선택하면 안됨!


이분검색

임의의 개수 N개의 숫자가 배열형태로 주어지면 오름차순으로 정렬 한 뒤 그 중 한개의 수인 M이 몇 번째 인덱스에 있는 지 구하시오.

📌 내가 푼 방법

📌 강사님 방법

function solution(nums, m) {
    let answer = 0;
    nums.sort((a, b) => a - b);
    let lt = 0;
    let rt = nums.length -1;

    while(lt <= rt) {
        let mid = parseInt((lt+rt)/2);
        if(nums[mid] === m) {
            answer = mid+1;
            break;
        }
        else if(nums[mid] > m) rt = mid-1;
        else lt = mid+1;
    } 
    
    return answer;
}

console.log(solution([23, 87, 65, 12, 57, 32, 99, 81], 32));

이분검색을 사용하려면 정렬이 되어 있어야함!
절반으로 나누어서 찾는거
lt와 rt를 사용해서 서로 비교해가면서 찾기


2차원 배열 이분검색

각 행과 각 열이 오름차순으로 되어 있는 2차원 배열이 있으면 특정 숫자를 찾는 가장 효율적인 방법을 구하여라

📌 내가 푼 방법

function solution(nums, m) {
    let answer = [];
    let row = 0;
    let col = nums[0].length -1;

    while(true) {
        if(nums[row][col] === m) {
            answer.push([row, col]);
            break;
        } else if(nums[row][col] > m) {
            col--;
        } else {
            row++;
        }
    }
    
    return answer;
}

console.log(solution([
    [1, 6, 9, 12],
    [3, 7, 10, 14],
    [5, 8, 13, 17],
    [15, 18, 20, 23]
], 8));

📌 강사님 방법

function solution(matrix, target) {
    let answer = [];
    let row = 0;
    let col = matrix[0].length - 1;

    while(row < matrix.length && col >= 0) {
        if(matrix[row][col] === target) return [row,col];
        else if (target < matrix[row][col]) col--;
        else row++;
    }
    
    return;
}

console.log(solution([
    [1, 6, 9, 12],
    [3, 7, 10, 14],
    [5, 8, 13, 17],
    [15, 18, 20, 23]
], 8));

마찬가지로 2차원 배열에서도 이분검색이 가능한데 row는 0부터, col은 그 배열행의 끝에서 부터 하여 그 지점부터 비교 matrix[row][col] <-- 여기부터
비교하려는 값보다 작으면 col의 번호를 감소시키고 그렇지 않고 비교하려는 값보다 크면 row를 증가시킨다.


랜선자르기(결정알고리즘) // 결정알고리즘의 가장 대표적인 문제

nums에 랜선의 길이가 주어지면 k개의 랜선을 만든다고 하였을 시 랜선의 최대길이를 구하여라

📌 내가 푼 방법

📌 강사님 방법

function solution(nums, n) {
    let answer;
    let lt = 1;
    let rt = Math.max(...nums); // 작은것으로 rt를 설정하면 반례가 생갈 수 있기 때문에 가장 큰값으로!

    function count(len) {
        let cnt = 0;
        for (let i = 0; i < nums.length; i++) {
            cnt += Math.floor(nums[i] / len);
        }
        return cnt;
    }

    while (lt <= rt) {
        let mid = parseInt((lt + rt) / 2);
        if (count(mid) >= n) { // if else만 사용하여 끝까지 가서 answer를 업데이트 시킨 값이 답
            answer = mid;
            lt = mid + 1;
        } else {
            rt = mid - 1;
        }
    }
    return answer;

}

console.log(solution([802, 743, 457, 539], 11));

결정알고리즘 : 답이 lt와 rt사이에 존재한다(확신!)
이분검색을 이용하여 답으로써 이 숫자가 가능한지, 가능하지 못한지 파악하는 함수를 만들어야함. mid가 값이 가능 한지 answer에 넣어두고 lt가 mid+1로 바꾸어 다시 비교해서 answer가 될 수 있는 가장 좋은값을 찾아야함(가장 마지막 값)
랜선의 최대 길이이므로 while문 중간의 if(count(mid) <= n) 이런식으로 작성하여 lt를 젤 마지막으로 증가시킨 값이 답!


뮤직비디오(결정알고리즘)

매개변수 nums에 노래 길이가 분 단위로 주어지고, 매개변수 m에 DVD의 개수가 지어 질 때, DVD의 최소용량크기를 반환하여라

📌 내가 푼 방법

function solution(nums, m) {
    let answer = 0;
    let lt = 9; // 9로 잡아도 되는데 그 이유가 노래를 쪼갤 수 없으므로
    let rt = nums.reduce((a, b) => a+b, 0);

    function count(size) {
        let cnt = 0;
        let sum = 0;
        for(let x of nums) {
            if(sum+x > size) {
                sum = 0;
                cnt++;
            }
            sum+=x;
        }
        return cnt + 1;
    }
    while(lt <= rt) {
        let mid = parseInt((lt+rt)/2);
        if(count(mid) <= m) {
            answer = mid;
            rt = mid - 1;
        } else {
            lt = mid + 1;
        }
    }

    return answer;
}

console.log(solution([6, 5, 8, 5, 6, 8, 7, 6, 6, 7], 3));

📌 강사님 방법

function count(songs, capacity) {
    let cnt =1 , sum = 0;
    for(let x of songs) {
        if(sum + x > capacity) {
            cnt++;
            sum = x;
        }
        else sum+=x;
    }
    return cnt;
}

function solution(songs, m) {
    let answer;
    let lt = Math.max(...songs); 
    let rt = songs.reduce((a, b) => a+b, 0);
   
    while(lt <= rt) {
        let mid = parseInt((lt+rt)/2);
        if(count(songs, mid) <= m) {
            answer = mid;
            rt = mid - 1;
        } else {
            lt = mid + 1;
        }
    }

    return answer;
}

console.log(solution([6, 5, 8, 5, 6, 8, 7, 6, 6, 7], 3));

결정알고리즘의 대부분 문제가 이 문제로 귀결됨
lt를 배열 원소중 가장 큰 값으로 잡고, rt를 모두 다 더한값으로 잡아서 비교하면서 용량을 정하고 다 담아서 나온 cnt값이 m보다 작거나 같으면 크게 잡았다는 의미이므로 rt값을 조정한다. 반대로 m보다 크면 용량을 너무 작게 잡았으므로 lt값을 조정한다.
최소 용량을 구하는 것이므로 count(song, mid) <= m과 같이 작성하여 rt의 값을 줄여주어 최소용량을 구함


마구간 정하기(결정알고리즘)

N개의 마구간이 배열형태로 주어지면 c마리의 말을 마구간에 넣을 시 가장 가까운 두 말의 최대거리를 구하여라.

📌 내가 푼 방법

📌 강사님 방법

function count(nums, size) {
    let cnt = 1;
    let point = nums[0];
    for(let i = 1; i<nums.length; i++) {
        if(nums[i] - point >= size) {
            cnt++;
            point = nums[i];
        } 
    }
    return cnt;
}

function solution(nums, c) {
    let answer = 0;
    nums.sort((a, b) => a-b);
    // lt와 rt를 설정할 때, 둘 사이의 거리를 고려!
    let lt = 1; // 마구간 사이의 거리이기 때문에 좌표의 제일 작은 값이 아닌 1로 설정
    let rt = nums[nums.length-1]; // 배열에서 가장 큰값

    while(lt <= rt) {
        let mid = parseInt((lt+rt) / 2);
        if(count(nums, mid) >= c) {
            answer = mid;
            lt = mid+1;
        } else {
            rt = mid-1;
        }
    }

    return answer;
}

console.log(solution([1, 3, 6, 11, 18, 27, 38, 41, 56, 73, 92, 113], 8));

좌표값을 우선 정렬해야함 (문제 잘보기)
lt의 값을 정할 때 첫 번째 마구간의 좌표가 아닌 1로 정하는게 좋음 --> 왜냐하면 반례가 생길 수 도 있고, 구하는 문제가 두 말의 거리이기 때문!


제품 이동

매개변수 N이 주어지고 매개변수 edges배열에 각 다리의 정보가 (A, B, C가 주어지는데 A와 B는 섬번호, C는 이동할 수 있는 최대 무게) 주어진다. 마지막 매개변수 s와 e에 두 공장이 있는 섬의 번호가 주어질 때, 한 번의 이동으로 옮길 수 있는 최대 무게를 구하여라.

📌 내가 푼 방법

📌 강사님 방법

function solution(n, edges, s, e) {
    let answer = 0;
    edges.sort((a, b) => a[2] - b[2]);
    let lt = 1; // 1로 설정
    let rt = 0;
    let graph = Array.from(Array(n + 1), () => Array());

    for (let [a, b, c] of edges) {
        graph[a].push([b, c]);
        graph[b].push([a, c]); // 양방향
        rt = Math.max(rt, c);
    }

    function BFS(weight) {
        let ch = Array.from({
            length: n + 1
        }, () => 0);
        let queue = [];
        queue.push(s);
        ch[s] = 1;
        while (queue.length) {
            let v = queue.shift();
            for (let [b, c] of graph[v]) {
                if (weight <= c && ch[b] === 0) {
                    ch[b] = 1;
                    queue.push(b);
                }
            }
        }
        // if(ch[e] === 1) {
        //     return true;
        // } else {
        //     return false;
        // }
        return ch[e]; // 이렇게 쓰면 간단함. (안간곳이면 0을반환(false)하고 간곳이면 1(true)이기때문에)
    }

    // mid값이 트럭에 싣는 무게, 이 무게로 s정점에서 e정점까지 갈 수 있으면 답!
    while (lt <= rt) {
        let mid = parseInt((lt + rt) / 2);
        if (BFS(mid)) {
            answer = mid;
            lt = mid + 1;
        } else {
            rt = mid - 1;
        }
    }
    return answer;
}

console.log(solution(5, [
    [1, 2, 5],
    [1, 3, 3],
    [1, 4, 2],
    [2, 4, 2],
    [3, 4, 4],
    [4, 5, 3]
], 1, 5));

DFS로 풀면 안됨!!
간선의 가중치보다 무게가 더 높을 수 없음
BFS + 이분검색으로 푼다

profile
It is possible for ordinary people to choose to be extraordinary.

0개의 댓글