전공/알고리즘
-
백준 1309(동물원)전공/알고리즘 2020. 10. 4. 22:22
www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 500문제 달성 위해서 랜덤문제를 푸는 첫 문제. 그냥 점화식 찾는 문제이다. 점화식을 잘 찾아보자 근데 생각보다 점화식이 너무 어려웠다. dp[N] = dp[N-1]*2 + dp[N-2] #include using namespace std; #define MAX 100005 int dp[MAX]; int solve(int idx) { if (dp[idx]) return dp[idx]; int ret=0; ret = (solve(idx-1)*2 + solve(idx-2)) % 9901; return dp[idx] = ret; } int main..
-
백준 10653(마라톤 2)전공/알고리즘 2020. 10. 2. 16:25
www.acmicpc.net/problem/10653 10653번: 마라톤 2 젖소 박승원이 2번째 와 4번째 체크포인트를 건너뛸경우 경로는 (0,0) -> (1,1) -> (2,2) 로 4가 된다. 이보다 더 짧게 달릴수는 없다. www.acmicpc.net 문제를 보자마자 재귀의 점화식이 떠오르긴 했다. 근데 이게 dp인지는 알기가 힘들었다. dp가 뭔지 제대로 모르고 있어서 그런가 그래도 점화식을 바탕으로 dp라고 생각하고 풀었다. 처음에는 최대 K개를 계속해서 패스할 수 있다는 건줄 알고 그렇게 풀었으나 틀렸습니다.를 맞은 후에 알았다. 재귀형식으로 돌아가는 구조와, 점화식 이 두개만 알면 구현도 쉬운 dp문제이다. dp[N][K]는 N체크포인트에서 K개의 건너 뜀을 행하였을때의 최소 값을 저장한..
-
백준 1939(중량제한)전공/알고리즘 2020. 9. 30. 13:59
www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net dfs와 bfs의 차이점과 특징을 상기시켜준 문제. 처음에는 그냥 dfs로 풀었다. 그러자 TLE 최악의 경우에 거의 N*M의 시간복잡도를 가지므로, 10^9 시간초과 발생가능성이 존재한다. 따라서 시간을 더 줄일 방법을 찾아야 했다. 단순 탐색으로 풀게된다면 dfs나 bfs나 똑같이 된다. 따라서 다른 방법이 필요했다. 이진탐색을 이용해서 중량을 결정하고 탐색 ..
-
백준 5829(Luxury River Cruise)전공/알고리즘 2020. 9. 24. 00:49
www.acmicpc.net/problem/5829 5829번: Luxury River Cruise Farmer John is taking Bessie and the cows on a cruise! They are sailing on a network of rivers with N ports (1 3 -> 2(시작) -> 3 -> 4 -> 3(시작) -> 4 -> 1 -> 4 -> 1 -> 2 -> 1(시작) 어떤 점에서 시작을 한다고 하고, 그 점에서 이미 시작을 하였다면 주기반복이다. 왜냐면 어떤 점에서 M의 이동을 하여서 목적지로 이동을 한다고 하면 M의 순서는 변하지 않고, 그래프도 그대로 있으니깐 당연하다. 따라서 주기를 찾으려면 일단 모든 시작점에서 M번의 간선을 지났을 때 목적지를 구하고, ..
-
백준 2252(줄 세우기)전공/알고리즘 2020. 9. 2. 00:22
https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이�� www.acmicpc.net 너무 오랜만에 알고리즘 문제를 풀었다. 역시 관성은 대단하다. 이 문제는 위상정렬의 대표적인 문제로, 위상정렬의 개념을 그대로 적용하면 AC가 나온다 근데 왜 골2인지 의문. 그래프 성질이 들어가서 그런가 위상정렬을 하는 이유는 모르겠다. 순서가 있는 순서도에서 순서를 출력하고자 할때에 쓰이는건가 사실 여기서 차수가 필요한데, 그다지 직관적으로 와닿지는 않았다...
-
백준 16207(직사각형)전공/알고리즘 2020. 8. 8. 17:28
https://www.acmicpc.net/problem/16207 16207번: 직사각형 문제 알렉스는 창고에서 어렸을 때 가지고 놀던 막대 N개를 찾았다. 막대의 길이는 A1, A2, ..., AN이며, 모두 2보다 크거나 같은 자연수이다. 오늘은 이 막대를 이용해서 직사각형을 만들려고 한다. www.acmicpc.net 스터디 모의고사를 봤는데 아쉽게 종료시각 직전에 풀어서 오류를 못 고쳐서 못 낸 문제 아무튼 아쉽다 사실 어제 코포에서 직사각형과 정사각형을 만드는 문제가 있어서 조금 더 쉽다고 생각했다. 한 변을 딱 한번만 1을 뺄 수 있을 때에 그 변들로 구성하는 직사각형 넓이의 합이 최대가 되도록 하는 넓이의 합을 구하는 문제. 먼저 넓이의 합이 언제 최대가 되는지 생각을 해봐야한다. 직사각형..
-
백준 18900 (Printer's Head)전공/알고리즘 2020. 8. 8. 17:21
https://www.acmicpc.net/problem/18900 18900번: Printer's Head Johnny bought a 3D printer. He wants to test it on a simple task: print $n$ cuboids with equal square bases and heights $1, 2, \ldots, n$ in the given order. The printer works in left-to-right and right-to-left sweeps, the sweeps can be mixed arbitrarily, www.acmicpc.net 임의의 배열이 주어진다. 숫자 배열에서 가장 큰 수 부터 지울 수 있는데, 여기서 지우는 조건은 1차이나는 숫자를 한..
-
백준 10090(Counting Inversions)전공/알고리즘 2020. 8. 5. 13:31
https://www.acmicpc.net/problem/10090 10090번: Counting Inversions A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example www.acmicpc.net 어떤 수열이 주어졌을때에, 배열이 역순으로 존재하는 크기 2의 부분수열 갯수를 구하는 문제. 분할정복에서 배..