Algorithm54 [백준 Gold 1] 2213 트리의 독립집합 - Java 문제링크 : https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 접근 과정 : 이전에 풀었던, '트리에서의 다이나믹 프로그래밍' 접근을 통해서 문제를 해결하려고 했다. 추가적으로 고민했던 부분은 독립 집합의 원소들을 추적하는 부분이었다. 결국 현재 정점의 독립 집합 포함 여부에 따라서 연결된 다음 정점의 포함여부가 결정되기에, 이 부분을 고려해서 작성했다. DP[][] : i번 정점의 독립집합 포함 여부 , [n+1.. 2022. 1. 6. [백준 Gold 1] 1949 우수 마을 - Java 문제링크 : https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 접근 과정 : 특정 마을이 우수 마을인지 아닌지를 기준으로하는 DP를 사용했다. DP[][] : i 마을이 우수 마을인 경우(1) / 우수 마을이 아닌 경우(0) 의 우수 마을들의 인구 총합 마을간의 연결 관계는, town 클래스를 생성해서 사용했다. '트리에서의 다이나믹 프로그래밍' 을 풀어보았다면 어렵지 않게 해결할 수 있다. 소스 코드 및 결과 : package BOJ;.. 2022. 1. 5. [백준 Gold 3] 2553 사회망 서비스(SNS) - Java 문제링크 : https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 접근 과정 : 각 친구는 얼리어답터이거나 일반인이다. 즉 노드의 상태가 0,1인 경우에 따라서, 최소 얼리어답터의 수를 저장하는 DP를 사용했다. DP[][] : i가 얼리어답터(1) 이거나 일반일(0)일 때, 최소 얼리어답터의 수를 의미한다. 그리고 친구 관계를 저장하는 데 있어서, List를 활용 / node 클래스 작성 두가지 방법으로 시도해보았다. 소스 코드 및 결과 : .. 2022. 1. 5. [백준 Platinum 5] 2618 경찰차 - Java 문제링크 : https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net 접근 과정 : DP를 활용하려고 했다. DP를 활용해서 최소 거리를 갱신하는데, 상황별 경찰차의 위치를 어떻게 처리할지가 관건이라고 생각했다. 경찰차의 위치는 사건이 발생한 위치와 같아지므로.. 최근에 각 경찰차가 처리한 사건의 인덱스를 기준으로 DP했다. 그리고 한번 더 탐색하면서, 경로를 저장했다. 소스 코드 및 결과 : package BOJ; /* 경찰차 .. 2022. 1. 4. 이전 1 2 3 4 5 6 7 ··· 14 다음
