전공
-
백준 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의 부분수열 갯수를 구하는 문제. 분할정복에서 배..
-
백준 2812(크게 만들기)전공/알고리즘 2020. 8. 5. 13:22
https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 문제 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000) 둘째 줄에 N자리 숫자 www.acmicpc.net 간단하다. N자리의 수가 주어졌을 때에 K개의 숫자를 지워서 가장 큰 수를 만드는 것이다. 그렇다면 큰 수의 조건은 무엇일까? A와 B를 비교하려면 어떻게 비교하는지에 대해서 생각해보자 먼저 최고자릿수를 비교한다. 수의 규모자체가 더 큰 게 더 큰 수가 되고, 같다면 그 최고자릿수의 크기에 따라서, 같다면 그 다음 자릿수에 따라서 수의 크기가 결정된다. 따라서 우리가 큰..
-
백준 11092(Safe Passage)전공/알고리즘 2020. 8. 3. 14:21
https://www.acmicpc.net/problem/11092 11092번: Safe Passage A group of friends snuck away from their school campus, but now they must return from the main campus gate to their dorm while remaining undetected by the many teachers who patrol the campus. Fortunately, they have an invisibility cloak, but it is only lar www.acmicpc.net 투명망토를 쓰고 학교로 돌아가는데 한번에 최대 두명만 쓸 수 있고, 속도는 더 느린쪽에 맞춰서 이동한다. 그리고 모두 ..
-
백준 1817(짐 챙기는 숌)전공/알고리즘 2020. 7. 31. 14:37
https://www.acmicpc.net/problem/1817 1817번: 짐 챙기는 숌 첫째 줄에 책의 개수 N과 박스에 넣을 수 있는 최대 무게 M이 주어진다. N은 0보다 크거나 같고 100,000보다 작거나 같은 정수 이고, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄에 책의 무게가 �� www.acmicpc.net 책이 쌓여있는데, 순서대로 밖에 책을 상자에 넣을 수 없으므로, 입력 순서와 반대로 책을 상자에 집어 넣는다. 만약에 용량을 초과하면 새로운 상자에 넣는다. 근데 여기서 넣을 책이 없는 경우도 있으므로 이 경우를 주의하자. 문제의 조건을 잘 확인하자 #include using namespace std; #define MAX 100001 int N, M, cnt=1, s..
-
백준 9576(책 나눠주기)전공/알고리즘 2020. 7. 31. 14:21
https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 �� www.acmicpc.net 그리디로 푼 문제 책을 최대한 많이 나눠주려고 한다. 책을 최대한 많이 못 나눠주게 되는 이유는 어떤 애한테 어떤 책을 줌으로써 다른 범위가 좁은 애가 못 받는 경우가 생겨서이다. 방법은 절대 누군가는 가질수 없는 곳을 가진 사람을 가장 늦게 뽑게하자이다 그러니깐 a b범위가 있을때, b를 기준으로 오름차순 정렬을 한뒤에 b가 가장 앞선 사람부터 뽑게한다. 1 2 1 1 1 5 2 6 3 5 4..