yulee

🤔문제 이해 비교된 학생들은 그 순서대로 줄을 비교되지 않은 학생들은 그냥 랜덤으로 줄을 세우면 되는 문제이다. 💡첫번째 아이디어 비교되지 않은 학생들을 먼저 맨 앞에 세워주고 비교된 학생들은 "순서"가 정해지므로 그 학생들을 순서에 맞게 줄을 세우는 방식을 떠올렸다. 그냥 위상정렬 문제. 🔥풀이🔥 in_degree의 값이 0인 경우 먼저 queue에 넣어준다. queue가 빌때까지 pop한 학생의 번호를 출력하고 그 학생 다음으로 줄을 설 수 있는 학생의 in_degree를 -1해줬을 때 in_degree값이 0이라면 queue에 push해준다. 비교된 학생이 중복될 수 있으므로 visited를 이용해 이미 줄을 세운 학생은 무시해준다. #include #include #include using nam..

🤔문제 이해 선행관계가 있는 작업은 선행 작업을 모두 마쳤을 때 수행될 수 있으므로 순서대로 작업하다가 특정 건물의 건설이 완료할 때까지 걸리는 최소 시간을 구하면 된다. 💡첫번째 아이디어 동시에 작업될 수 있는 작업들 중 시간이 적게 걸리는 작업이 먼저 다 수행되어야 하므로 priority queue를 사용하면 된다. 🔥풀이🔥 pq에서 가장 시간이 적게 걸리는 작업을 먼저 수행하고 그 작업 다음에 수행될 수 있는 작업의 in_degree를 하나 줄여준다. in_degree를 줄였을 때 그 값이 0이라면 다음에 바로 수행할 수 있으므로 pq에 현재와 다음 작업의 수행시간을 더한 값과 다음 정점을 넣어준다. 위 과정을 반복하다가 찾고자 하는 작업이 pop될 때 그 작업의 수행시간을 출력해주면 된다. 아래는..