jaeserrr.log

https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 연산 - 최소시간을 구하는 문제이기 때문에, dp를 갱신할 때 max로 해주어야 한다. - 모든 작업이 끝났을 때의 최소시간으로 갱신을 해주어야 한다. queue 가 비었을 때 즉, 모든 작업이 끝났을 때의 바로 직전의 for문으로 들어가기 전 시점에서 갱신을 한다. 그렇게 된다면, 다음에 탐색할 node는 없으니까 이 시점이 마지막 작업이 된다. #include #include #inc..

https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 입력 i번째 건물이 지어지기 위해 먼저 지어져야하는 건물을 입력할 때, -1이 들어오면 바로 입력에서 빠져나와야 한다. 연산 - 이 문제에서 위상정렬과 함께 DP를 활용할 때엔, 초기화해주는 단계에서 각 건물의 dp엔 각 건물이 지어지기 위한 시간으로 초기화 해준다. 누적되는 시간을 구하기 위함이다. - 다음 노드를 탐색할 때, max로 갱신을 해준다. * 최소 시간 = 건물을 동시에 ..

크루스칼 * tuple 로 저장한 그래프에 대해, 가중치가 짧은 순서대로 정렬하는 것 잊지말기 #include #include #include #include using namespace std; typedef tuple tp; vector parent; int findParent(int v) { if (parent[v] < 0) // 값이 음수라는 것은, 루트(최상위 부모) 찾음 return v; return parent[v] = findParent(parent[v]); // 그래프 압축, 해당 정점의 부모 찾기 } bool unionNodes(int x, int y) { // 각 노드의 부모를 찾음 int px = findParent(x); int py = findParent(y); // 부모가 같다..

소수점 둘째자리까지 나타내기 위해, 아래와 같이 선언 후 cout 하면 된다. cout next_w) { dist[next] = next_w; pq.push({next_w, next}); } } } return sum; } /* * 모든 별자리가 연결되어 있다고 가정 후, 각 별마다의 가중치를 계산하여 그래프를 완성 * 최소 신장 트리 알고리즘 (프림) 수행 */ int main() { int v; double a, b; // 입력 cin >> v; vector star(v + 1); // first : x, second : y for (int i = 1; i > a >> b; star[i] = { a,b }; } // 가중치 계산 vector graph(v + 1, vector(v + 1)); // f..

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 2차원 배열로, 문자가 같을 경우와 다른 경우에 따라, 부분 수열이 되는 수열 중 가장 긴 것으로 dp를 채워나가면 된다. 그리고 string 그대로 dp에 저장해버리면 시간초과가 나기 때문에,, dp가 채워진 순서를 역추적하여 lcs를 완성해야 한다. #include #include #include using namespace std; const ..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net * 주의! * 우선 4,000,000까지 먼저 걸러준 후에, 2부터 n까지 필요한 소수를 저장해주어야 한다. for (int i = 2; i * i

https://www.acmicpc.net/problem/18115 18115번: 카드 놓기 수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. www.acmicpc.net 앞과 뒤를 다 참조해야할 때 유연하게 사용할 수 있는 STL인 deque를 사용하여 카드를 구현한다. #include #include #include #include using namespace std; deque prac(int n, vector& tech) { deque card; // 처음 카드 상태 for (int i = 1; i > n; vector tech(n + 1); for (int..

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 순서가 상관없기 때문에 unordered_map을 활용하였다. 자꾸 시간 초과가 난다면 꼭 추가하기! cin.tie(NULL); ios_base::sync_with_stdio(false); #include #include #include #include using namespace std; int main() { cin.tie(NULL); ios_base::sync_w..

https://www.acmicpc.net/problem/17478 단순한 재귀문제이다.🙂 문제에서 요구하는 대로 출력하면 된다. 기저조건에선 꼭 return; #include using namespace std; int N; void print(int n) { if (n == 0) { for (int j = n; j < N; j++) cout