본문 바로가기
반응형

전체 글282

백준 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.
SCPC 2022 1차 예선 후기 1번 문제 제출 횟수가 2번인 건 비밀입니다:) 2번은 (내가 이상하게 푼 건지 모르겠지만) 예외 케이스 처리를 따로 해주어야 하는 경우가 있었는데 놓쳐서 3번 만에 AC를 받았다. 3번은 2번이랑 같은 배점인데 2번에 비해 너무 쉬워서 2번을 이상하게 꼬아서 푼 것 같다는 생각이 계속 들었다.. 4번은 아이디어 생각해내는데 시간을 너무 많이 썼다. 5번은 대충 감은 잡았는데 구체적인건 좀 더 시간 써서 생각해봐야 할 것 같았다. 근데 너무 졸려서 그냥 잤다. 나한테는 이번이 두 번째 SCPC였다. 그래서 올해 난이도는 잘 가늠이 안되지만 개인적으로는 중간에 다른 일정 없었으면 올솔도 가능했을 것 같아서 조금 아쉽다. 1차 통과해도 2차 예선 날 아침부터 풀로 다른 일정이 있어서 참가 못할 것 같다..ㅠ.. 2022. 7. 18.
백준 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.
반응형

티스토리툴바