본문 바로가기
반응형

Problem Solving242

백준 13904번 과제 - C++ 풀이 1. 시간 역순으로 매일 가장 점수를 많이 받을 수 있는 과제를 고른다. 1. 시간 역순으로 매일 가장 점수를 많이 받을 수 있는 과제를 고른다. 1781번 컵라면 문제와 동일한 문제이다. 1781번 게시글에 그리디 알고리즘에 관해 그림과 함께 설명해두었으니 참고. (점수=컵라면이라고 생각하면 된다.) 백준 1781번 컵라면 - C++(cpp) 풀이 + 그림 설명 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. 1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다. day일에 풀 수 있 please-amend.tistory.com #include #include using namespace std; typedef pair pii;.. 2022. 8. 22.
백준 1963번 소수 경로 - C++ 풀이 1. 에라토스테네스의 체를 이용하여 4자리 소수를 모두 구한다. 2. BFS를 이용하여 두 소수 사이의 변환에 필요한 최소 회수를 구한다. 1. 에라토스테네스의 체를 이용하여 4자리 소수를 모두 구한다. 네 자리 수가 소수인지 아닌지 판별할 일이 잦으므로 미리 4자리 소수를 모두 구해두어 O(1)에 소수 판별을 할 수 있도록 하자. N 미만의 소수는 에라토스테네스의 체를 사용하면 O(NloglogN)에 구할 수 있다. 2. BFS를 이용하여 두 소수 사이의 변환에 필요한 최소 회수를 구한다. 각 소수를 그래프의 노드라고 생각하면, BFS를 통해 두 소수(노드) 사이의 최단 거리를 구할 수 있다. #include #include using namespace std; const int INF = 987654.. 2022. 8. 20.
백준 17142번 연구소 3 - C++ 풀이 1. M개의 자리를 활성시키는 모든 경우를 시뮬레이션하여 최소 시간을 구한다. 2. 각 경우는 BFS를 이용해서 시뮬레이션한다. 1. M개의 자리를 활성시키는 모든 경우를 시뮬레이션하여 최소 시간을 구한다. 바이러스를 놓을 수 있는 위치가 최대 10군데이고, M이 최대 10이므로 최악의 경우에도 10C5가지 경우 밖에 발생하지 않는다. 또한 각 경우를 시뮬레이션하는 데는 O(N^2)의 시간 복잡도가 들기 때문에 브루트 포스를 사용해도 충분하다. 2. 각 경우는 BFS를 이용해서 시뮬레이션한다. 바이러스가 퍼지는 시뮬레이션은 BFS를 사용하면 쉽게 구현할 수 있다. #include #include #include using namespace std; typedef pair pii; const int EMP.. 2022. 8. 19.
백준 25430번 다이제스타 - C++ 풀이 1. 다익스트라를 사용하여 최단거리를 구한다. 2. 다익스트라 과정에서 마지막으로 이용한 간선의 가중치 w를 저장해 두고 더 큰 가중치의 간선만 사용하도록 한다. 3. 같은 노드에 도착하더라도 w에 따라 이용할 수 있는 다음 간선이 달라지므로 dist 배열은 dist[node][w]의 형태로 운영한다. 1. 다익스트라를 사용하여 최단거리를 구한다. 다익스트라 알고리즘을 사용하여 두 노드 사이의 최단거리를 구할 수 있다. 2. 다익스트라 과정에서 마지막으로 이용한 간선의 가중치 w를 저장해두고 더 큰 가중치의 간선만 사용하도록 한다. 단, 문제에서 주어진 조건에 따라 경로 내 간선의 가중치는 오름차순이 되어야 한다. 따라서 다익스트라 과정에서 이 조건을 만족할 수 있도록 마지막으로 이용한 간선의 가중치 w.. 2022. 8. 18.
백준 13913번 숨바꼭질 4 - C++ 풀이 1. BFS를 이용하여 K까지 가기 위한 최단 거리를 찾는다. 2. BFS 과정에서 이전 노드를 기록하여 경로를 구할 수 있도록 한다. 1. BFS를 이용하여 K까지 가기 위한 최단 거리를 찾는다. 수 하나를 노드 하나라고 생각하고, n번 노드와 [n+1, n-1, 2n]번 노드는 간선으로 이어져있다고 생각하면 된다. BFS를 이용하여 N번 노드에서 K번 노드까지의 거리를 구한다. 이때 노드 번호의 범위를 [0, 200000]으로 제한할 수 있다. N, K의 범위가 100,000이므로 거리의 최댓값은 100,000이다. 그런데 200,000보다 큰 노드의 경우 더 작아지는 방법은 -1 밖에 없기 때문에 최소 100,000번의 연산을 해야 K로 갈 수 있다. 따라서 200,000을 넘어가는 수는 고려하지 .. 2022. 8. 17.
반응형

티스토리툴바