yulee

🤔문제 이해 먼저 푸는 게 좋은 문제는 먼저 풀어주되 번호가 낮은 문제를 더 우선적으로 풀면 된다. 출력으로는 문제 푸는 순서를 출력하면 되는 문제이다. 💡첫번째 아이디어 먼저 푸는 것이 좋은 문제가 있는 문제를 모두 순서대로 출력해주고, 나머지 문제들을 오름차순으로 출력해주면 된다고 생각했다. ❌첫번째 제출 제대로 풀었다고 생각했고, 출력 값도 잘 나왔다.문제를 다시 읽어보고 반례를 생각해보니 문제의 조건에 "가능하면 쉬운 문제부터"라는 조건을 빠뜨렸었다..! 💡두번째 아이디어 먼저 푸는 것이 좋은 문제가 없는 문제의 in_degree도 0으로 초기화해서 가능하면 쉬운 문제들부터 출력되게 해주었다 . 🔥풀이🔥 위상정렬 알고리즘을 이용하였다. 우선순위큐를 사용하여 in_degree가 0인 문제 먼저 출력..

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

🤔문제 이해 어떤 작업을 수행하는 데 있어 순서가 있고 동시에 수행이 가능할 때, 순서대로 모든 작업을 수행하는 데 걸리는 시간을 구하는 문제이다. 💡첫번째 아이디어 위상정렬 문제로 동시에 수행되는 작업이 있고 선행에 있는 작업을 모두 수행했을 때 다음 작업 수행이 가능하므로 priority queue를 사용해야겠다고 생각했다. 🔥풀이🔥 1. pq에 in_degree가 0인 정점을 다 넣어준다. 2. 현재 pq의 top의 시간을 time값에 더해주고 pop을 해준다. 3. pq에 남아 있는 작업들에서 top의 시간을 빼주고 그 값들을 tmp라는 임시 queue에 넣어준다. 4. tmp에 들어있는 값들을 하나씩 빼서 pq에 넣어준다. 5. top의 다음에 수행될 수 있는 작업들의 in_degree를 -1 ..

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