반응형 알고리즘207 백준 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. 백준 1058번 친구 - C++ 풀이 1. 어떤 사람 p의 2-친구수는 p가 아닌 나머지 모든 사람에 대해 2-친구 여부를 판별해서 구할 수 있다. 2. 모든 사람의 2-친구수를 각각 구한 뒤 그 중 최대값을 찾는다. 1. 어떤 사람 p의 2-친구수는 p가 아닌 나머지 모든 사람에 대해 2-친구 여부를 판별해서 구할 수 있다. 어떤 사람 p의 2-친구수는 k(k != p)인 모든 사람에 대해 친구 여부를 판별해서 구할 수 있다. 두 사람 A, B가 2-친구 사이인지 구하려면 두 사람 모두와 친구인 사람 C가 있는지 찾아야 하므로 O(N)의 시간복잡도가 든다. 따라서 어떤 사람 p의 2-친구수를 구하는데는 O(N^2)의 시간복잡도가 들게 된다. 2. 모든 사람의 2-친구수를 각각 구한 뒤 그 중 최대값을 찾는다. 모든 사람에 대해 2-친구수를.. 2022. 6. 1. 이전 1 ··· 13 14 15 16 17 18 19 ··· 42 다음 반응형
