본문 바로가기
반응형

알고리즘207

백준 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.
백준 15685번 드래곤 커브 - C++ 풀이 1. 다음 세대 드래곤 커브를 만들 때는, 최근에 생성된 순서로 점들을 회전시킨다. 2. 주어진 드래곤 커브들을 시뮬레이션한 뒤 네 꼭짓점이 모두 드래곤 커브에 포함된 정사각형의 개수를 센다. 1. 다음 세대 드래곤 커브를 만들 때는, 최근에 생성된 순서로 점들을 회전시킨다. 드래곤 커브는 이루는 점들을 생성된 순서로 배열에 담는 것으로 나타낼 수 있다. 다음 세대 드래곤 커브는 현재 세대의 끝점(가장 최근에 생성된 점)을 기준으로 90도 회전하므로, 배열 역순으로 점들을 회전시켜준다. 2. 주어진 드래곤 커브들을 시뮬레이션한 뒤 네 꼭짓점이 모두 드래곤 커브에 포함된 정사각형의 개수를 센다. 1의 방법으로 주어지는 드래곤 커브들을 모두 시뮬레이션으로 생성한 뒤, 드래곤 커브에 속하는 좌표를 체크해 조건.. 2022. 8. 14.
백준 1939번 중량제한 - C++ 풀이 1. 가중치 내림차순으로 간선을 정렬한다. 2. 두 공장이 이어질 때까지 간선을 하나씩 추가한다. 1. 가중치 내림차순으로 간선을 정렬한다. 시작 공장에서 도착 공장으로 가는 경로에서 가중치가 가장 작은 간선이 한 번에 옮길 수 있는 중량의 최댓값을 결정한다. 2. 두 공장이 이어질 때까지 간선을 하나씩 추가한다. 따라서 시작 공장에서 도착 공장으로 가는 경로가 생성될 때까지 가중치가 큰 간선부터 차례로 추가해보면 된다. 가중치가 큰 순서로 추가했으므로, 최초로 경로가 만들어지는 순간에 추가한 간선이 경로 내에서 최소 가중치를 갖는 간선이 되므로 해당 간선의 가중치가 답이 된다. #include #include using namespace std; typedef pair pii; typedef pair .. 2022. 8. 12.
백준 1699번 제곱수의 합 - C++ 풀이 1. dp(n) : n을 제곱수들의 합으로 표현할 때에 그 항의 최소 개수 2. dp(n) = min(1 + dp(n-i*i)) 1. dp(n) : n을 제곱수들의 합으로 표현할 때에 그 항의 최소 개수 dp(n)을 위와 같이 정의하자. 2. dp(n) = min(1 + dp(n-i*i)) n을 표현하는 제곱수 중 하나로 i*i를 골랐다고 가정하자. 이제 (n - i*i)를 제곱수들의 합으로 표현해야 하므로, dp(n) = 1 + dp(n-i*i)가 된다. 따라서 i*i가 n 이하인 모든 i에 대해 dp(n) = 1 + dp(n-i*i)값을 계산하고, 그중 최솟값을 찾으면 된다. 기저 사례는 n이 1 이하일 때, dp(0) = 0, dp(1) = 1. #include #include using names.. 2022. 8. 12.
반응형

티스토리툴바