yulee

🤔문제 이해 한 공장에서 다른 공장으로 가는 경로 중에서 그 경로 상에 있는 중량 제한 값 중에서 최솟값을 찾고, 그 최솟값 중 가장 큰 것을 출력해주는 문제이다. 💡첫번째 아이디어 DFS를 통해 모든 경로를 탐색해서 그 경로의 가장 작은 중량제한 값을 저장하고 그 값들끼리 비교해서 젤 큰 값을 찾아주면 된다고 생각했다. ❌첫번째 제출 섬이 1만개, 도로가 10만개로 10억번을 다 돌게 되는 첫번째 아이디어 방법으로는 시간초과가 났다. 💡두번째 아이디어 시간초과를 어떻게 해결해야할지 막막해서 질문을 했다. 문제에서 나와있듯 짐의 무게보다 중량제한이 작은 다리를 지나가려는 경우엔 다리가 무너진다고 했다. 이 점을 활용해서 이분탐색을 이용하여 결과를 도출해주면 1초 안에 해결이 가능했다. 🔥풀이🔥 DFS +..

🤔문제 이해 상, 하, 좌, 우, 대각선 4방향으로 인접한 1을 한 글자로 취급하여 글자가 몇개 있는지 구하는 문제이다. 🔥풀이🔥 정말 간단한 BFS 문제인데 방향이 4개 더 추가된 버전이다. 방향을 표현해주는 dx와 dy를 다음과 같이 선언해서 오른쪽, 왼쪽, 위쪽, 아래쪽, 오른쪽 아래, 왼쪽 아래, 오른쪽 위, 왼쪽 위를 나타내주었다. int dx[8] = { 1, -1, 0 , 0 , 1, -1, 1, -1}; int dy[8] = { 0, 0, 1, -1, 1, -1, -1, 1}; #include #include using namespace std; int m, n; int map[251][251]; bool visited[251][251]; queue q; int dx[8] = { 1, -1..

🤔문제 이해 같은 색이 연속으로 나오지 않게 칠했을 때 비용이 가장 적게 드는 경우의 비용을 구하는 문제이다. 🔥풀이🔥 전에 풀어본게 기억이 나서 바로 DP를 이용해 풀었다. dp[i][j]에서 i는 집의 번호, j는 색을 의미한다. dp[i][0]은 0을 칠했을 때 그 전 집에서 칠할 수 있는 경우는 1과 2이므로 dp[i-1][1]과 dp[i-1][2]를 비교해 더 작은 값과 i번째 집을 0으로 칠했을 때의 비용과 합해 dp[i][0]을 업데이트 해준다. 색깔 1과 2도 동일하게 해주게 되면 마지막 집에서 색을 0을 칠했을 때 vs 1을 칠했을 때 vs 2를 칠했을 때를 비교해 그 최솟값을 출력해준다. #include #include using namespace std; int n; vector dp..

🤔문제 이해 최단거리로 도달할 수 있는 도시들 중 최단거리가 k인 경우만 출력해주는 문제이다. 💡첫번째 아이디어 다익스트라 문제인데 그냥 다익스트라를 수행한 후 최단 거리가 k인 값만 출력해주면 된다고 생각했다. 🔥풀이🔥 다익스트라 수행 후 dist[i]값이 k인 i만 출력 ❌트러블 슈팅 dist를 모두 INF를 바꿔주고 시작점인 x만 0으로 바꿔주는 코드가 없어서 첫 제출에서 틀렸다. dist[x] =0 코드 추가 후 제대로 돌아갔다. #include #include #include using namespace std; #define INF 987654321 int n, m, k, x; vector edge; int dist[300002]; int main() { cin.tie(nullptr); cou..

🤔문제 이해 문제에서 요구하는 1,2,3번을 계산하되 벽에 대한 정보가 1, 2, 4, 8로 주어지는 것으로 보아 비트마스킹을 사용하면 되는 문제이다. 🔥풀이🔥 간단한 BFS를 수행하되 벽의 정보를 비트 연산으로 처리해주었다. ((1 > m; for (int i = 0; i > map[i][j]; } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (!visited[i][j]) { visited[i][j] = true; cnt++; q.push({i, j}); room_size = 0; BFS(); if (max_room < room_size) max_r..

🤔문제 이해 비교된 학생들은 그 순서대로 줄을 비교되지 않은 학생들은 그냥 랜덤으로 줄을 세우면 되는 문제이다. 💡첫번째 아이디어 비교되지 않은 학생들을 먼저 맨 앞에 세워주고 비교된 학생들은 "순서"가 정해지므로 그 학생들을 순서에 맞게 줄을 세우는 방식을 떠올렸다. 그냥 위상정렬 문제. 🔥풀이🔥 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 ..

🤔문제 이해 1번 정점에서 N번 정점까지 가는 모든 경로 중에 최대 k개의 도로 이동 시간이 0이 되었을 때 시간이 가장 적게 드는 경로의 시간을 구하는 문제이다. 💡첫번째 아이디어 다익스트라 문제이지만 도로를 포장해야 한다는 점에서 더 어려웠다. 스터디 멘토님이 가르쳐준 방법은 아래 풀이와 같다. 🔥풀이🔥 최단경로 문제에서 최단거리를 저장하는 1차원 배열을 2차원 배열로 바꾸어 dist[i][j]에서 j는 도로를 포장한 횟수를 의미한다. 따라서 다익스트라로 구현하되 j값이 문제에서 주어지는 포장가능한 도로의 개수 k보다 작을 때 도로를 한 번 포장한 값을 j+1에 넣어주고 포장하지 않았을 때의 값을 j에 업데이트 해준다. 정점 n에 도착하면 break해주고 나서는 도로를 몇번 포장했을 때 가장 최소인지..

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

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