반응형 알고리즘207 백준 2086번 피보나치 수의 합 - C++ 풀이 1. 1번째 항부터 n번째 항까지의 합을 g(n)이라 하면, g(n) = g(n-1) + g(n-2) + 1 2. 점화식을 행렬 곱으로 나타낸다. 3. 분할 정복을 이용하여 행렬의 거듭제곱을 계산한다. 1. 1번째 항부터 n번째 항까지의 합을 g(n)이라 하면, g(n) = g(n-1) + g(n-2) + 1 피보나치수열을 점화식으로 나타내면 f(n) = f(n-1) + f(n-2), f(1) ~ f(n)의 합을 g(n)이라고 하면, g(n) = g(n-1) + g(n-2) + 1이다. 2. 점화식을 행렬 곱으로 나타낸다. g에 대한 점화식을 다음과 같은 행렬 곱으로 나타낼 수 있다. 3. 분할 정복을 이용하여 행렬의 거듭제곱을 계산한다. 분할 정복을 이용하여 거듭제곱을 계산하여 시간 초과를 피한다. #.. 2022. 7. 19. 백준 4355번 서로소 - C++ 풀이 1. N을 소인수 분해한다. 2. 오일러 피 함수를 사용하여 서로소의 개수를 구한다. 1. N을 소인수 분해한다. 오일러 피 함수를 사용할 것이다. 이를 위해 N의 소인수를 모두 구해둔다. 2. 오일러 피 함수를 사용하여 서로소의 개수를 구한다. N과 서로소인 1부터 N까지의 정수의 개수를 구하는 함수인 오일러 피 함수를 이용하여 서로소의 개수를 구한다. #include #include using namespace std; typedef long long ll; // 소인수분해 vector calcDivisors(int N) { vector divisors; int n = N; for (int i=2; i*i 1) divisors.push_back(n); return divisors; } int coun.. 2022. 7. 18. 백준 2610번 회의준비 - C++ 풀이 1. 각 사람이 리더일 때 의사전달시간의 최댓값은 플로이드 와샬 알고리즘을 사용하여 구할 수 있다. 2. 위원회는 그래프의 연결 요소와 같다. 3. DFS/BFS를 사용하여 각 위원회의 리더를 정한다. 1. 각 사람이 리더일 때 의사전달시간의 최대값은 플로이드 와샬 알고리즘을 사용하여 구할 수 있다. A가 리더일 때 B의 의사전달시간은 A와 B의 사이의 거리와 같다. 따라서 A가 리더일 때 의사전달시간의 최댓값은 나머지 모든 사람들과의 거리를 알면 구할 수 있다. 플로이드 와샬 알고리즘을 사용하여 모든 사람들에 대해 각 사람이 리더일 때의 의사전달시간의 최댓값을 구할 수 있다. 2. 위원회는 그래프의 연결 요소와 같다. 위원회의 정의는 그래프의 연결요소와 같다. 따라서 K는 연결요소의 수와 같다. 3. .. 2022. 7. 15. 백준 4991번 로봇청소기 - C++ 풀이 1. 총 이동 횟수가 최소가 되는 순서로 더러운 칸들을 방문해야 한다. 2. A칸에서 B칸으로 가기 위한 최소 이동 횟수는 BFS로 구한다. 1. 총 이동 횟수가 최소가 되는 순서로 더러운 칸들을 방문해야 한다. 더러운 칸이 최대 10개이므로, 더러운 칸을 방문하는 순서를 정하는 경우의 수는 10! 이 중 총 이동 횟수가 최소가 되는 경우를 찾으면 된다. N이 작기 때문에 DFS를 이용한 브루트 포스로도 시간 내에 통과가 가능한데, 아래 코드에서는 DP를 사용하였다. 2. A칸에서 B칸으로 가기 위한 최소 이동 횟수는 BFS로 구한다. 중간에 장애물이 있을 수 있으므로 A칸에서 B칸으로 가기 위한 최소 이동 횟수는 BFS를 이용해서 구해야 한다. #include #include #include #incl.. 2022. 7. 14. 백준 1600번 말이 되고픈 원숭이 - C++ 풀이 1. 원숭이의 위치 {r, c}와 말처럼 이동한 횟수 k로 원숭이의 상태를 나타낼 수 있다. 2. 원숭이의 상태를 그래프의 노드로 생각하고, 한 번의 이동으로 도달 가능한 상태를 모두 간선으로 잇는다. 3. 출발 상태 노드에서 도착 상태 노드로 가는 최단 거리를 BFS를 사용하여 구한다. 1. 원숭이의 위치 {r, c}와 말처럼 이동한 횟수 k로 원숭이의 상태를 나타낼 수 있다. 원숭이의 상태를 나타내기 위해서 필요한 값은, 원숭이의 위치와 현재 위치까지 오면서 말(knight)처럼 이동한 횟수 k이다. 2. 원숭이의 상태를 그래프의 노드로 생각하고, 한 번의 이동으로 도달 가능한 상태를 모두 간선으로 잇는다. 원숭이의 {r, c, k} 값을 가지고 원숭이 상태 노드를 나타낸다. 그리고 한 번의 이동으로.. 2022. 7. 13. 이전 1 ··· 7 8 9 10 11 12 13 ··· 42 다음 반응형
