아래 글은 오늘 강의를 들은 자료구조/알고리즘 수업의 내용과 내가 푼 방식, 강사님이 푼 방식이다. 문제의 저작권 때문에 간략하게 정리해서 올리는 점 참고해 주시기 바란다.
[최단거리, Trie]
최소편집
문자열 A와 B가 주어져있을 때, 문자열 A를 문자열 B로 바꾸려고한다. 이때 편집하는 최소횟수는?
📌 내가 푼 방법
📌 강사님 방법
function solution(s1, s2) {
let answer;
let len1 = s1.length+1; //
let len2 = s2.length+1; // 6
let dy = Array.from(Array(len1), () => Array(len2).fill(0));
for(let i = 0; i<len2; i++) {
dy[0][i] = i;
}
for(let i = 0; i<len1; i++) {
dy[i][0] = i;
}
for(let i = 1; i<len1; i++) {
for(let j = 1; j<len2; j++) {
if(s1[i-1] === s2[j-1]) {
dy[i][j] = dy[i-1][j-1];
} else {
dy[i][j] = Math.min(dy[i-1][j], dy[i][j-1], dy[i-1][j-1]) + 1;
}
}
}
answer = dy[len1-1][len2-1];
return answer;
}
console.log(solution("BAOBAB", "BACBA"));dy[i,j]의 정의: s1[0~i]문자열을 s2[0~j]문자열로 바꾸는데 사용된 최소 편집 횟수
다를 때는 왼쪽, 위쪽, 대각선 값을 보고 젤 작은값 + 1을 해주면 됨
같으면 대각선 값 가져오면 됨
동전 바꿔주기(냅색 알고리즘)
동전의 금액과 개수가 배열형태로 주어지고 지폐의 금액정보가 주어지면 교환하는 방법의 가지수를 구하여라
📌 내가 푼 방법
📌 강사님 방법
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;
}
console.log(solution(20, [[5, 3], [10, 2], [1, 5]]));동전의 개수가 유한개이기 때문에 뒤에서부터 dp배열을 작성해야함!
방법의 가지수 이기 때문에 배열을 0번째 인덱스를 1로 초기화(자신의 스킬)
여기서 dy배열은 i원을 교환하는 방법의 수
플로이드 와샬 알고리즘
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;
}
console.log(solution(5, [
[1, 2, 6],
[1, 3, 3],
[3, 2, 2],
[2, 4, 1],
[2, 5, 13],
[3, 4, 5],
[4, 2, 3],
[4, 5, 7]
]));dist[i][j]의 의미는 i번 정점에서 j번 정점으로 가는 최소 비용
자신에서 자신으로 가는 dist값은 0으로 초기화!
i, j, k로 삼중 포문을 돌면서 i에서 j로 가는 방법과 i에서 k를 거쳐서 j까지 가는 방법 중 최소 값을 dp배열로 만들어 풀면 된다.
백준의 키순서 --> 플로이드 와샬 알고리즘 문제
플로이드 와샬은 knapsack 알고리즘이다!
회장뽑기(플로이드-와샬 응용)
점수가 가장 낮은 사람이 회장이 되는데 회장 후보의 점수와 회장후보 수를 구하여라
📌 내가 푼 방법
📌 강사님 방법
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 = 100;
for(let i = 1; i<=n; i++) {
for(let j = 1 ; j<=n; j++) {
if(i===j) continue;
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;
}
console.log(solution(5, [[1, 2], [2, 3], [3, 4], [4, 5], [2, 4], [5, 3]]));플로이드 와샬을 돌려서 dist배열의 값을 채워두고, score배열을 dist배열을 이용해서 채워 가장 낮은값과 그 낮은값을 가진 인덱스들의 수를 세어 반환한다.
Trie 자료구조
📌 내가 푼 방법
📌 강사님 방법
class Node {
constructor() {
this.end = false;
this.child = {}
}
}
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.end = true;
}
search(word) {
let cur = this.root;
for (let x of word) {
if (cur.child[x] === undefined) return false;
cur = cur.child[x];
}
return cur.end;
}
prefixS(str) {
let cur = this.root;
for (let x of str) {
if (cur.child[x] === undefined) return false;
cur = cur.child[x];
}
return true;
}
}단어의 끝에만
this.end = true를 해줌
자동완성
go라는 단어가 한번 입력되면 gone를 찾기 위해선 gon까지만 입력하면 된다. 단어를 찾을 때 입력해야할 총 문자수를 구하여라
📌 내가 푼 방법
📌 강사님 방법
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;
}
search(word) {
let cur = this.root;
for(let x of word) {
if(cur.child[x] === undefined) return false;
cur = cur.child[x];
}
return cur.end;
}
prefixS(str) {
let cur = this.root;
for(let x of str) {
if(cur.child[x] === undefined) return false;
cur = cur.child[x];
}
return true;
}
}
function solution(nums) {
let tree = new Trie();
let answer = 0;
for(let x of nums) {
tree.insert(x);
}
for(let word of nums) {
answer += tree.getCount(word);
}
return answer;
}
console.log(solution(["go","gone","guild"]))
Node에 cnt변수와insert함수에 cnt를 세는 로직을 구현하여 다른 단어들과 겹치는 부분을 체킹하고getCount함수를 만들어 cnt가 1을 만나면 그 전까지 카운트 해준것을 반환하여 answer에다가 다 더하여 반환시킨다.
