아래 글은 오늘 강의를 들은 자료구조/알고리즘 수업의 내용과 내가 푼 방식, 강사님이 푼 방식이다. 문제의 저작권 때문에 간략하게 정리해서 올리는 점 참고해 주시기 바란다.
친구관계가 순서쌍으로 주어지면 특정 두 명이 친구인지 판별하여라.
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배열을 가지고 같은 집합인지 파악하는 함수이다.
매개변수에 도시의 개수와 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차원 배열이 있으면 특정 숫자를 찾는 가장 효율적인 방법을 구하여라
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 + 이분검색으로 푼다