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;
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;
}
}
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;
}