yulee

🤔문제 이해 어떤 작업을 수행하는 데 있어 순서가 있고 동시에 수행이 가능할 때, 순서대로 모든 작업을 수행하는 데 걸리는 시간을 구하는 문제이다. 💡첫번째 아이디어 위상정렬 문제로 동시에 수행되는 작업이 있고 선행에 있는 작업을 모두 수행했을 때 다음 작업 수행이 가능하므로 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 ..

🤔문제 이해 모든 도시를 거치고 다시 처음 도시로 돌아오는 모든 경로 중 비용이 가장 적게 드는 경로의 비용을 구하는 문제이다. 💡첫번째 아이디어 그냥 순열을 구해서 풀면 최대 16! =20,922,789,888,000으로 1초 안에 절대 풀 수 없다. 이 문제는 1주차 스터디에서 배운 비트마스킹에 대한 문제였고, 문제 풀이 방식을 거의 다 배웠어서 DP와 비트마스킹으로 바로 풀 수 있었다. 물론 DP 동작 방식을 이해하기 위해 시간이 조금 걸리긴 했다. 🔥풀이🔥 dp[i][j]는 현재 위치 i와 현재까지 방문했던 정점들의 정보를 담은 j 값일 때, 앞으로 필요한 순회 비용의 최솟값을 의미한다. j가 (1 w[i][j]; } } cout