반응형 전체 글282 백준 1083번 소트 - C++ 풀이 1. 그리디 하게 앞자리부터 큰 수로 만들어야 한다. 2. i번째 자리에서 X칸 떨어져있는 수는 X번의 스왑으로 i번째 자리로 끌어올 수 있다. 3. S번 이내의 스왑으로 끌어올 수 있는 가장 큰 수를 앞으로 끌어오기를 반복한다. 1. 그리디하게 앞자리부터 큰 수로 만들어야 한다. 결과가 사전 순으로 가장 뒷서도록 하려면 최대한 앞을 큰 수로 만들어야 한다. 2. i번째 자리에서 X칸 떨어져 있는 수는 X번의 스왑으로 i번째 자리로 끌어올 수 있다. 그리고 i번째 자리(A[i])에서 X칸 떨어져 있는 수(A[i+X])는 최소 X번의 스왑으로 i번째 자리로 끌어올 수 있다. A[i+X]를 A[i+X-1], A[i+X-2], ... 순으로 스왑하면 총 X번의 스왑으로 A[i+X]를 A[i]자리로 끌어오고, .. 2022. 6. 7. 백준 2294번 동전 2 - C++ 풀이 1. dp(price): 정확히 price원을 만드는데 필요한 동전의 최소 개수 2. dp(price) = min(1 + dp(price - coin[i])) 1. dp(price): 정확히 price원을 만드는데 필요한 동전의 최소 개수 dp(price)를 위와 같이 정의하자. 기저 사례는 price = 0일 때 return 0. 2. dp(price) = min(1 + dp(price - coin[i])) 각 동전의 개수는 무한하므로 price원을 만들기 위해 이번에 사용할 동전만 골라주면 된다. i번째 동전을 사용하기로 했을 때 dp(price) = 1 + dp(price- coin[i]). i = 0~(N-1)까지 각 동전을 고르는 모든 경우를 탐색한 뒤, 그중 최솟값을 찾으면 된다. #inclu.. 2022. 6. 5. 백준 2211번 네트워크 복구 - C++ 풀이 1. 다익스트라 알고리즘을 사용해서 1번 정점에서 각 정점으로의 최단 거리를 구한다. 2. 1번 과정에서 각 정점을 최단거리로 방문하기 위해 직전에 방문한 정점을 기록해둔다. 3. 2번 과정에서의 기록을 가지고 최단거리로 전송하기 위해 필요한 간선들만 골라낸다. 1. 다익스트라 알고리즘을 사용해서 1번 정점에서 각 정점으로의 최단 거리를 구한다. 1번 슈퍼컴퓨터에서 각 컴퓨터로 최소 시간으로 패킷을 전송해야 한다. 따라서 1번 컴퓨터에서 각 컴퓨터까지의 최단 거리를 구해야 한다. 한 정점에서 다른 모든 정점으로의 최단거리는 다익스트라 알고리즘을 사용해서 구할 수 있다. 2. 1번 과정에서 각 정점을 최단거리로 방문하기 위해 직전에 방문한 정점을 기록해둔다. 구해야 하는 것은 최단 시간(거리)이 아니라 최.. 2022. 6. 4. 백준 13459번 구슬 탈출 - C++ 풀이 1. 시뮬레이션으로 10번 이내로 움직이는 모든 경우를 다 시도해본다. 1. 시뮬레이션으로 10번 이내로 움직이는 모든 경우를 다 시도해본다. 시뮬레이션 문제였다. 보드 기울여 구슬 움직이는 것을 잘 구현해준 뒤, DFS를 이용해서 10번 이내로 움직이는 모든 경우를 다 시도해준다. 각 depth에서 상하좌우로 움직이는 경우 전부를 시도해주어야 한다. #include #include using namespace std; const int MAX = 10; const int U = 0, D = 1, L = 2, R = 3; const int RED = 100, BLUE = 200; struct Marble { int r, c; char color; }; int N, M; Marble H; char boar.. 2022. 6. 3. 백준 2573번 빙산 - C++ 풀이 1. 빙산 덩어리의 개수는 그래프의 연결 요소 개수이므로 DFS/BFS 호출 횟수와 같다. 2. 모든 빙산 칸에 대해 주변의 0의 개수만큼 높이를 줄여주고, 빙산덩어리의 개수를 센다. 3. 빙산 덩어리의 개수가 2개 이상이 될 때까지 2번 과정을 반복한다. 1. 빙산덩어리의 개수는 그래프의 연결 요소 개수이므로 DFS/BFS 호출 횟수와 같다. 서로 연결되어 있는 빙산칸은 하나의 덩어리이므로, 빙산 덩어리의 개수는 그래프의 연결 요소 개수와 같다. 따라서 빙산 덩어리 개수는 모든 빙산칸을 방문하기까지 호출한 DFS/BFS의 횟수와 같다. 2. 모든 빙산 칸에 대해 주변의 0의 개수만큼 높이를 줄여주고, 빙산 덩어리의 개수를 센다. 빙산이 녹는 과정을 시뮬레이션 해준 뒤, 빙산 덩어리의 개수를 세준다. 이.. 2022. 6. 2. 이전 1 ··· 23 24 25 26 27 28 29 ··· 57 다음 반응형
