전공
-
백준 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부..
-
백준 1937(욕심쟁이 판다)전공/알고리즘 2020. 7. 17. 14:20
https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 무슨 문젠지 모르겠는 문제 그냥 dp인걸 알아서 풀었다 정도? ㅈ 같은 판다 아무튼 생각을 진짜 많이 했다. 집중해서 계속 하다보니깐 떠오른 사실이 있었다. 가장 큰 값 순서대로 처리하면 꼬일 일이 없다. 여기서 말하는 꼬일 일이란 내가 만약에 큰 값대로 처리를 하는데 어떤 값 처리 후에 그 값의 dp변화가 생기는 것이다. 예제에서 가장 큰 값인 16을 먼저 처리해보자. 16 상 하 좌 ..
-
백준 2213(트리의 독립집합)전공/알고리즘 2020. 7. 16. 16:10
https://www.acmicpc.net/problem/2213무 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 �� www.acmicpc.net 먼저 이 문제를 dp문제라고 생각하자. 요즘 dp스터디라서 dp인걸 알고 풀고 있음. 문제 이해부터 하자면 트리가 있을때, 인접한 정점은 고르지 못한다. 이 조건을 만족하면서 고른 정점들의 가중치 합이 최대가 되는 값과 그 고른 정점들을 구하려는 문제이다. 결론부터 얘기하면 subtree로 나눈다. subtree들이 모여서 그 위의 부모트리의 값을 결정한다...
-
백준 11049(행렬 곱셈 순서)전공/알고리즘 2020. 7. 15. 14:56
https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같� www.acmicpc.net 오랜만의 알고리즘 컨디션이 너무 안좋아져서.. 아무튼 이 문제를 보면 대충 감이 안온다. 어떻게든 풀 수는 있을것 같은데.. 처음에는 행값이 큰 거 순서대로 연산횟수를 줄이면 어떨까 싶었지만, 진행방법이 떠오르지 않아서 스킵하고, 스터디에서 진행하는 dp식으로 문제를 접근하였다. dp를 적용시키려면 문제의 부분 뭉텅이도 전체처럼 풀수 있을때 적용시키는 것 같다. 뭔가 부분문제도 전체..
-
백준 11780(플로이드 2)전공/알고리즘 2020. 7. 10. 15:44
https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n(1≤n≤100)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 www.acmicpc.net https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 � www.acmicpc.net 이 문제에서 훨씬 더 어려운 조건..