About Dev

https://www.acmicpc.net/problem/13325 13325번: 이진 트리 각 에지에 양수인 가중치가 부여된 높이가 k인 포화이진트리가 주어져 있다. 높이 k인 포화이진트리는 2k개의 리프를 포함하여 (2k+1 − 1)개의 노드를 가진다. 루트에서 어떤 리프까지의 거리는 www.acmicpc.net 알고리즘 : 트리에서 DP 풀이 날짜 : 2023.07.27. K 의 최댓값은 20 으로, 전체 노드 개수의 최댓값은 2 ^ (20 + 1) - 1 ≒ (10 ³) ² 으로 백 만개이다. 따라서 시간 복잡도 O(N) 안에 해결해야 한다. 처음에 같은 부모의 두 자식 edge 는 같은 weight 를 가져야 한다고 생각했다. 위로 같은 route 를 가기 때문이라고 생각했지만..

https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 알고리즘 : 트리에서 DP (DFS + DP) 풀이 날짜 : 2023.07.26. 다음 문제와 조건만 다를 뿐 풀이 로직과 방식은 동일하다. [백준/DP] - 백준 2533: 사회망 서비스(SNS) [골드 Ⅲ / Java] 2533 번 문제와 다른 점은, 노드 개수만이 아니라 마을 주민 수를 비교해 주어야 하고, 그 중 최솟값이 아니고 최댓값을 구하는 문제이다. 『 Ro..

https://www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net 알고리즘 : DP 풀이 날짜 : 2023.08.08. 기본 풀이 원리는 다음 문제와 동일하다. [백준/DP] - 백준 12865: 평범한 배낭 [골드 Ⅴ / Java] 다만 12865번 문제에서는 시간 복잡도가 N (물건 수) * M (가능 배낭 무게) = 100 * 100,000 = 약 1,000만 이지만, 같은 코드에 대하여 해당 문제..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 알고리즘 : DP 풀이 날짜 : 2023.07.19. 어떤 물건을 사용하는 경우와 사용하지 않는 경우를 비교한다. 이때 DP 배열 정의를 다음과 같이 한다. DP[i][bag] = 0 ~ i 인덱스의 물건들의 조합으로 bag을 만들 수 있는 경우 중 최대 가치 그럼 무게가 w인 i 번째 인덱스의 물건을 탐색 중일 ..

https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 알고리즘 : 수학 or Dynamic Programming 풀이 날짜 : 과거, 2023.06.27. 리뷰 "베스킨 라빈스 31" 게임같은 문제이다. 중학교 때 수학 학원 선생님이 해당 게임을 두 명이서 할 때 이기기 위해서는 26을 선점해야 한다고 말해주셨던 기억이 난다. 그럼 22를, 18, 14, 10, 6, 2 를 먼저 사수하면 유리하다. 각설하고, 이 문제는 위의 게임과 다르게 1개나 3개만 가져갈 수 있고, 마지막 돌을 가져가는 사람이 이긴다. 여기서 가져갈 수 있는 돌 개수가 홀수임을 알..

https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 알고리즘 : 트리에서 DP (DP + DFS) or DFS or BFS 풀이 날짜 : 2023.06.23. , 2023.07.28. 리뷰 문제에서 N 이 최대 백 만(10 ^ 6) 까지 나오므로, 시간 복잡도는 O(NlogN = N * log(2 ^ 10 * 2 ^ 10)) 도 아니고 O(N) 이 되도록 구현해야 한다. 문제에서 고려해야 할 상황들과 풀이 로직의 전제를 잘 ..

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 알고리즘 : DFS + DP 풀이 날짜 : 과거, 2023.06.11. 리뷰 더보기 판다 일러스트 출처 : https://kor.pngtree.com/freepng/hand-drawn-cute-panda-eating-bamboo-leaves-illustration_4563517.html 대나무 일러스트 출처 : https://www.logoyogo.com/downloa..

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 알고리즘 : DP 풀이 날짜 : 과거, 2023.04.17, 2023.07.07. 리뷰 무릇 DP 문제는, 어떤 상황이 정해져 있지 않을 때 주로 사용한다. 여러 상황 중에 가정하며 값을 할당하는 것이다. 이 문제에서 정해져 있지 않은 상황은 i 번째 날 근무 여부 이다. 그에 따라 다른 업무를 할 수 있는지에 영향을 주기 때문이다. i 번째 날 근..