전공/알고리즘
-
백준 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..
-
백준 19539(사과나무)전공/알고리즘 2020. 7. 30. 20:08
ㅜhttps://www.acmicpc.net/problem/19539 19539번: 사과나무 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다. www.acmicpc.net 2020ucpc H번 문제 쉬는데 갑자기 계속 생각이 나길래 좀 더 생각을 해보니깐 알것 같다. 일단 문제는 단순하다. 2만큼 자라게 하는 물과 1만큼 자라게 하는 물을 무조건 하루에 다 써야 한다. 주어진 나무의 길이를 모두 어떤 하루가 지났을 때에 도달할 수 있느냐 물을 한 나무에 모두 부어도 괜찮다. 그러면 하루에 3만큼 자라게 해주어야하고 특정일이 도달했을때에는 3*n만큼의 길이가 된다. 따라서 만약에 목표 나무길이들의 합이 3의 ..
-
백준 1700(멀티탭 스케줄링)전공/알고리즘 2020. 7. 29. 15:31
https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 그리디 스터디중에 푸는 문제인데 내가 생각했던 그리디보다는 좀 그리디답지 않은 문제였다. 정해진 갯수의 콘센트에 전자기기를 꽂아서 사용할 수 있는데, 전자기기의 사용순서가 있어서 콘센트에서 코드를 뽑는 횟수가 최소가 되게끔 만드는게 이 문제이다. 엄청 단순하고 명확하다 그냥 제일 늦게 사용하는거를 뽑아서 사용하면 되지 않을까 만약에 이미 꽂혀있는거면 그대로 꽂아서 사용하면 되고. 그래서 단순하게 ..
-
백준 1967(트리의 지름) dp전공/알고리즘 2020. 7. 20. 17:07
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 �� www.acmicpc.net dp로 풀 수 있다길래 dp로 풀어보았다. dp의 핵심은 항상 생각하는 것이다. 전체의 부분이 빠짐없이 되는 부분을 찾으면 된다. 그래서 나는 dp[node]를 dp[node][2]로 쪼개어서, dp[node][0]은 node를 root로 하는 트리의 지름 dp[node][1]은 node를 root로 하는 최대 간선 길이 로 하였다. dp[node][1]의 존재 이유는 더 상위..
-
백준 11054(가장 긴 바이오닉 부분 수열)전공/알고리즘 2020. 7. 17. 15:08
https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 감소하다가 증가하지 않는 수열이 바이토닉 수열이라고 한다. 그러니깐 증가만 해도 되고, 감소만 해도 되고, 증가하다가 감소해도 되고 이 문제는 어떤 수열이 주어졌을 그 수열의 부분수열 중 가장 긴 바이토닉 수열을 구하는 것이다. 보자마자 생각나는 문제가 있다. LIS다 그런데 감소해야하는 경우도 구해야 한다. 바이토닉 수열 dp[i] = max( i까지의 증가수열 + i부터 감소수열) 따라서 i까지의 증가수열과 i부..