TIL-220325

윤·2022년 3월 25일

데브코스-TIL

목록 보기

2/8

😊배운내용

우선순위큐는 개념이고
자료구조가 아니다.
하지만 힙이 효율이좋아서 쓴다.

힙의 특징
우선순위가 높은 요소가 먼저 나간다 - root
루트가 가장 큰값- 최대힙, 루트가 가장작은값- 최소힙

정렬

비교식 정렬

요소를 비교해서 정렬을 하는 방식

분산식 정렬

분산정렬

오늘의 과업

최소힙

🎆Todo...

오늘 실습

가장먼 노드 https://programmers.co.kr/learn/courses/30/lessons/49189
그래프를 리스트말고 행렬로 해보고 싶어서 했다가..
태케에서 계속 실패했다, 엣지케이스 고려하는게 잘 안되는것같은데
역시 코드 줄이 길어지면 길어질수록 알아보기가 힘들어진다.

// n 개노드 1-n 까지 가장먼 노드 최단경로일때 간선이 제일큰것
// 1번노드에서 각 노드까지 간선이 몇개인지 체크
// 각 노드에서 dfs?

function solution(n, edge) {
  var answer = 0;
   let adjM= Array.from(Array(n+1), () => Array(n+1).fill(0))
   edge.map((e,i)=>{
      let [l,r]=[e[0],e[1]]
      adjM[l][r]=1
      adjM[r][l]=1
   })
   let visit=[1];
   let will=[];
   let num=new Map();
   let leng=0
   adjM[1].map((e,i)=>{
       if(e===1){
         will.push(i)
         visit.push(i)
 
       }
       num.set(i,leng+1);
       
   })
   let max=1
   while(will.length>0){
       let now=will.shift()
       adjM[now].map((e,i)=>{
       if(e===1 && !visit.includes(i)){
         will.push(i)
         visit.push(i)
         leng= num.get(i) || 0
         num.set(i,leng+1);
         max=Math.max(leng+1,max)
       }
       
       })
   }
   num.delete(0);
   num.delete(1);
     
  [...num.entries()].map((e,i)=>{
       if(e[1]===max) answer+=1
   })
 
   console.log(answer)
   return answer;
     
 }

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

다시 풀어봐야지..

입국심사

https://programmers.co.kr/learn/courses/30/lessons/43238

// 시간 최소
// 입국심사 시간으로 이분탐색을 한다.. 와 발상이
function solution(n, times) {
    var answer = 0;
    let [left,right]=[0,times[times.length-1]*n]
    
    while (left <= right) { 
        let sum= 0
        let mid = parseInt((left + right) / 2) 
        times.map((e)=>{
            sum+=parseInt(mid/e)
        })
        
        if(sum<n){
            left=mid+1
        }else{
            right=mid-1;
            answer=mid;         
        }
    }

    return answer

}

계속 시간값을 미리 구하고 탐색을 하려니깐, log n 안에 안돌아갈것 같았다.
근데 그냥 시간 범위를 정해놓고 심사관 시간으로 나누면 되는거였다..