알고리즘60 [백준 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. [백준 Gold 2] 17472 다리 만들기 2 - Java 문제링크 : https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 접근 과정 : 크게 4개의 과정으로 문제를 해결하려고 했다. input() : 입력을 받는 단계. N,M을 입력받고 그에 따라 Map[][] 입력받는다. defindLand() : 섬을 정의하고 구분한다. 섬에 번호를 붙여 구분한다. serarchBridge() : 섬들 사이에 연결할 수 있는 모든 다리를 구한다. minBridges() : 앞서서 구한 다리들을 .. 2022. 1. 4. 이전 1 2 3 4 5 6 7 8 ··· 15 다음
