DP10 [백준 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. [백준 Silver 1] 1309 동물원 - Java 문제링크 : https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 접근 과정 : 2차원 배열(zoo[][])을 선언하고, 2칸 모두 사자가 없는 경우 / 왼쪽칸에 사자가 있는 경우 / 오른쪽칸에 사자가 있는 경우로 경우의 수를 더했다 즉, Bottom-Up 방식으로 DP를 구현하였다. 소스 코드 및 결과 : package BOJ; /* 동물원 */ import java.io.*; public class BOJ1309 { public static void main(String[] args) throws NumberFormatException, IOException { BufferedR.. 2021. 12. 23. [백준 Gold 1] 2098 외판원 순회 - Java 문제링크 : https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 접근 과정 : 백준 10971 외판원순회2 문제의 코드를 리팩토링 시키는 방향으로 시도해보았다. 완전탐색으로 모든 경우를 탐색하면 시간초과!! 즉, 메모리제이션을 통해 이전에 체크한 부분을 재활용해야 한다. DP[][]을 만들어서 이를 관리 i 도시에 있고 j 비트에 포함된 도시를 탐색한 상황에서, 남은 도시를 모두 방문하는 최소비용 또한, 결국 .. 2021. 12. 22. 이전 1 2 3 다음
