아래 글은 오늘 강의를 들은 자료구조/알고리즘 수업의 내용과 내가 푼 방식, 강사님이 푼 방식이다. 문제의 저작권 때문에 간략하게 정리해서 올리는 점 참고해 주시기 바란다.
[트리, 이분검색(결정알고리즘)]
친구인가? (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 + 이분검색으로 푼다
