본문 바로가기
반응형

알고리즘207

백준 11780번 플로이드 2 - C++ 풀이 1. 플로이드 와샬 알고리즘을 사용하여 모든 도시 쌍에 대해 최단 거리를 구한다. 2. 플로이드 와샬 알고리즘을 수행할 때 이전 방문 도시 before를 함께 기록한다. 3. before를 이용하여 시작 도시에서 도착 도시까지의 루트를 구한다. 1. 플로이드 와샬 알고리즘을 사용하여 모든 도시 쌍에 대해 최단 거리를 구한다. 플로이드 와샬 알고리즘을 사용하여 O(N^3)에 모든 노드 쌍에 대해 최단 거리를 구할 수 있다. 2. 플로이드 와샬 알고리즘을 수행할 때 이전 방문 도시 before를 함께 기록한다. 플로이드 와샬 알고리즘에서 i -> j로 가는 것보다 i -> k -> j로 k를 거쳐가는 것이 더 빠를 때 거리를 업데이트한다. i에서 j로 가는 길에 k를 방문하므로, i에서 j로 갈 때 이전 방.. 2022. 7. 25.
백준 17135번 캐슬 디펜스 - C++ 풀이 1. 먼저 궁수 3명의 타깃을 계산만 한 뒤, 모아서 한 번에 죽인다. 2. 모든 적을 한 칸 내린다. (대신 궁수를 한 칸 올려도 된다.) 3. 1, 2번 과정을 N-1번 반복한다. 1. 먼저 궁수 3명의 타겟을 계산만 한 뒤, 모아서 한 번에 죽인다. 궁수끼리 적이 중복될 수 있다. 따라서 타겟을 계산하고 바로 죽이면 안 되고, 궁수 3명의 타깃을 일단 계산만 한 뒤에 3개의 타깃을 한 번에 죽여야 한다. 타깃 계산은 거리가 가까운 순으로, 거리가 가깝다면 왼쪽에 있는 순으로 반복문을 이용해서 간단하게 구현하였다. 2. 모든 적을 한 칸 내린다. (대신 궁수를 한 칸 올려도 된다.) 모든 적을 한 칸 내린다. 대신 궁수를 한칸 올려도 똑같은 상황이기 때문에 아래 코드에서는 궁수를 올려주었다. 다만 궁.. 2022. 7. 24.
백준 11778번 피보나치 수와 최대공약수 - C++ 풀이 1. gcd(f(m), f(n)) = f(gcd(m, n))이다. 2. 유클리드 호제법을 이용하여 gcd(m, n)을 구한다. 3. 분할 정복을 이용하여 gcd(m, n)번째 피보나치 수를 구한다. 1. gcd(f(m), f(n)) = f(gcd(m, n))이다. 위와 같은 피보나치의 성질을 이용해서 푸는 문제였다. 증명은 여기를 참고했다. https://math.hmc.edu/funfacts/fibonacci-gcds-please/ 2. 유클리드 호제법을 이용하여 gcd(m, n)을 구한다. 먼저 m과 n의 최대 공약수를 구해야 한다. 유클리드 호제법을 사용하여 O(logN)에 구해준다. 3. 분할 정복을 이용하여 gcd(m, n)번째 피보나치 수를 구한다. 피보나치 수열을 행렬의 거듭제곱으로 나타낸 .. 2022. 7. 22.
백준 1561번 놀이 공원 - C++ 풀이 1. 파라매트릭 서치를 사용하여 모든 사람이 놀이기구에 탑승하기 위해 필요한 최소 시간 totalTime을 구한다. 2. totalTime을 이용해서 마지막 사람이 탑승하는 놀이기구 번호를 구한다. 1. 파라매트릭 서치를 사용하여 모든 사람이 놀이기구에 탑승하기 위해 필요한 최소 시간 totalTime을 구한다. 시간이 주어지면 해당 시간까지 각 놀이기구가 몇 번 운행되는지 구할 수 있다. 따라서 먼저 모든 사람이 놀이기구에 탑승하는 데 걸리는 시간 totalTime을 찾아주자. 파라매트릭 서치를 이용하여 O(log30N)에 totalTime을 구할 수 있다. 2. totalTime을 이용해서 마지막 사람이 탑승하는 놀이기구 번호를 구한다. 현재 시각을 t라고 하면, 마지막 놀이기구는 t = totalT.. 2022. 7. 21.
백준 1113번 수영장 만들기 - C++ 풀이 1. 하늘에서 비를 내린다고 생각하고, 낮은 칸부터 물을 채운다. 2. 바깥에서 시작하는 DFS/BFS로 물이 담기지 않고 밖으로 흐르는 칸을 체크한다. 1. 하늘에서 비를 내린다고 생각하고, 낮은 칸부터 물을 채운다. 하늘에서 비를 내린다고 생각하자. 낮은 칸부터 점차 물이 차오를 것이다. 이것을 시뮬레이션해준다. 2. 바깥에서 시작하는 DFS/BFS로 물이 담기지 않고 밖으로 흐르는 칸을 체크한다. 비가 내려도 담기지 않고 밖으로 흐르는 칸이 있을 수도 있다. 바깥 칸에서 시작해서 현재 높이 이하인 칸만 방문하는 DFS/BFS를 수행했을 때, 방문되는 칸이라면 밖으로 흐르는 칸이다. #include #include using namespace std; int N, M; int board[52][52].. 2022. 7. 20.
반응형

티스토리툴바