전체 글
-
2020 ucpc예선 후기대회/UCPC 2020. 7. 27. 15:30
https://www.acmicpc.net/contest/view/522 UCPC 2020 예선 Open 사용 가능한 언어 C++14 Python 3 C11 PyPy3 C++11 C++17 Java (OpenJDK) C++2a Kotlin (JVM) C++11 (Clang) C++14 (Clang) C11 (Clang) C++17 (Clang) C++2a (Clang) www.acmicpc.net 올해 5월부터 알고리즘을 풀기 시작해서 처음으로 대회를 참가해보았다. 난이도 표시도 안되고, 알고리즘 표시도 안되고, A번 패스 B번 그냥 어려워보여서 풀 생각도 안했다. C번도 마찬가지 D번은 중반부터 풀이를 생각해보았는데 트리를 어떻게 조사해야 할지 모르겠어서 .. E번은 허겁지겁 풀었다. 단순하게 생각했을..
-
백준 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]의 존재 이유는 더 상위..
-
7/17일상 2020. 7. 17. 16:17
알고리즘 문제를 풀다보면 생각하는 과정에 대해서 생각하게 된다. 어떤 생각을 위해서 어떤 생각을 끄집어 내고, 하는 것의 반복이다. 그러다가 특정 알고리즘에 대해서 깨달았다고 생각될 때에는 머릿속에서 그림으로 그려진다. 우리가 쓰는 언어나 코드는 시각적인 것보다 정보를 조금 담는다 그렇다면 시각적인 것보다 더 많은 정보를 나타내는 무언가가 있지 않을까 단순 시각적 감각뿐만이 아니라 여러 감각을 사용해서 정보를 전달받고 있다고 생각한다. 만약 친구에게 숫자하나를 생각해보라고 한 뒤에 그것만 생각하고 있을 때 내가 친구의 모습을 보고 그 숫자를 맞춘다고 해보자 아니 딥러닝으로 학습된 기계로 해보자 솔직히 맞추기 힘들것이라고 생각하지만 확신하는 건 아니다. 만약 기계가 맞출 수 있다는 건 사람도 맞출 때가 있..
-
백준 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들이 모여서 그 위의 부모트리의 값을 결정한다...