본문 바로가기
반응형

알고리즘207

백준 3745번 오름세 - C++ 풀이 1. 가장 긴 증가하는 부분 수열의 길이를 O(nlogn)에 구한다. 1. 가장 긴 증가하는 부분 수열의 길이를 O(nlogn)에 구한다. 가장 긴 증가하는 부분 수열을 구하는 문제이다. n = 10^5이므로 O(n^2)이 아닌 O(nlogn)의 알고리즘을 사용해서 구해야 한다. #include #include #include using namespace std; int LIS(const vector& arr) { vector lis; lis.push_back(0); for (auto x: arr) { if (x > lis.back()) { lis.push_back(x); } else { int lb = lower_bound(lis.begin(), lis.end(), x) - lis.begin(); li.. 2022. 7. 30.
백준 16118번 달빛 여우 - C++ 풀이 1. 다익스트라를 이용하여 1번 정점에서 각 정점까지의 거리를 구한다. 2. 늑대의 경우 다익스트라 과정에서 홀수번째로 방문과 짝수번째 방문을 구분해서 기록한다. 1. 다익스트라를 이용하여 1번 정점에서 각 정점까지의 거리를 구한다. 한 정점에서 다른 모든 정점까지의 거리는 다익스트라 알고리즘을 사용하여 구할 수 있다. 2. 늑대의 경우 다익스트라 과정에서 홀수번째로 방문과 짝수번째 방문을 구분해서 기록한다. 늑대의 경우 한 간선을 홀수번째로 이용할 때와 짝수번째로 이용할 때 적용되는 가중치가 다르다. 따라서 한 정점을 홀수번째로 방문할 때와 짝수번째로 방문할 때 거리가 다르므로, dist 배열을 홀수, 짝수 각각 따로 기록해준다. i번 정점까지의 최종거리는 min(i번 정점을 홀수번째로 방문할 때의 거.. 2022. 7. 29.
백준 23290번 마법사 상어와 복제 - C++ 풀이 1. 각 단계를 시뮬레이션한다. 2. fish[x][y][d] = (x, y) 위치에서 d 방향을 향하는 물고기의 수의 형태로 물고기 정보를 관리한다. 1. 각 단계를 시뮬레이션한다. 단순 시뮬레이션 구현 문제라 특별한 알고리즘이나 자료구조가 필요하지는 않다. 다만 물고기의 수가 매우 많아질 수 있기 때문에 물고기를 1차원 배열로 관리하면 시간 초과를 맞을 수 있다. 2. fish[x][y][d] = (x, y) 위치에서 d 방향을 향하는 물고기의 수의 형태로 물고기 정보를 관리한다. 물고기의 상태는 위치와 방향으로 결정된다. 4x4칸, 8가지 방향이 있으므로 각 칸에서 각 방향을 향하고 있는 물고기의 수의 형태로 관리하면 시간을 줄일 수 있다. #include #include #include #incl.. 2022. 7. 28.
백준 18809번 Gaaaaaaaaaarden - C++ 풀이 1. 배양액을 뿌리는 모든 경우를 고려하여 피울 수 있는 꽃의 최대 개수를 찾는다. 2. BFS를 사용하여 배양액의 전이를 시뮬레이션한다. 1. 배양액을 뿌리는 모든 경우를 고려하여 피울 수 있는 꽃의 최대 개수를 찾는다. 배양액을 뿌릴 수 있는 땅의 개수가 최대 10개이고, 뿌려야 하는 배양액의 개수도 최대 10개이므로, 최대 배양액을 뿌리는 경우의 수는 최대 10C5 = 252가지 밖에 없다. 또한 각 경우를 O(N^2)에 시뮬레이션할 수 있으므로 브루트 포스를 사용해도 충분하다. 배양액을 뿌릴 곳을 선택할 때는 비트 마스킹을 사용하였다. 초록과 빨강 배양액을 뿌릴 곳을 각각 G, R개를 선택하고, 두 색깔이 겹치는 곳이 있는지 확인해주었다. 2. BFS를 사용하여 배양액의 전이를 시뮬레이션한다. 배.. 2022. 7. 27.
백준 1958번 LCS 3 - C++ 풀이 1. dp(a, b, c): A[a...], B[b...], C[c...]의 LCS 길이 2. 만약 A[a] = B[b] = C[c]이면, dp(a, b, c) = 1 + dp(a+1, b+1, c+1) 3. 아니라면, dp(a, b, c) = max(dp(a+1, b, c), dp(a, b+1, c), dp(a, b, c+1)) 1. dp(a, b, c): A[a...], B[b...], C[c...]의 LCS 길이 세 문자열을 각각 A, B, C라고 하고 dp(a, b, c)를 위와 같이 정의하자. 2. 만약 A[a] = B[b] = C[c]이면, dp(a, b, c) = 1 + dp(a+1, b+1, c+1) 문자열 2개일 때 LCS와 똑같은 방식으로 점화식을 세우면 된다. 세 문자열의 첫 글자가 .. 2022. 7. 26.
반응형

티스토리툴바