Algorithm/BOJ172 [BOJ]1976번: 여행 가자 문제: https://www.acmicpc.net/problem/1976 N제한이 작으므로 완전 탐색으로 해결할 수 있습니다. 여행 계획 E-C-B-C-D를 예시로 설명해보면, 여행 계획을 출발지-도착지 관계로 E-C, C-B, B-C, C-D로 나눈 후 각 각을 방문할 수 있는지 DFS로 조사합니다. 시간복잡도는 O(N^2*M)으로 최악의 경우에도 O(40,000,000)이므로 시간 제한에 걸리지 않습니다 :) 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1976.java 2022. 3. 2. [BOJ]16562번: 친구비 문제: https://www.acmicpc.net/problem/16562 그래프 문제입니다. 1. 주어진 간선(친구 관계)을 활용하여 전체 N개의 노드를 몇 개의 컴포넌트로 나눕니다. - 예제의 경우 2개의 컴포넌트로 나뉩니다. (1-3, 2-4-5) 2. 각 컴포넌트를 탐색하기 위한 최소 비용을 구합니다. 3. 각 컴포넌트를 탐색하기 위한 최소 비용들의 합이 K 이하라면 모든 사람과 친구가 될 수 있고, K 초과면 불가능합니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ16562.java 2022. 3. 2. [BOJ]1162번: 도로포장(JAVA) 문제: https://www.acmicpc.net/problem/1162 JusticeHui님이 푸신 솔루션을 참고하여 해결하였습니다. (출처: https://justicehui.github.io/usaco/2019/07/12/BOJ1162/) 도로 포장에 대한 정보를 어떻게 나타내느냐가 중요한 문제입니다. 이 문제의 경우 다익스트라의 결과값인 dist[N]을 다음과 같이 응용해서 정의할 수 있습니다. dist[N][K]: 출발점 1번 도시에서 N번 도시까지 갈 때, K개의 도로를 포장해서 가는 최단거리. 이 때 저희가 원하는 정답 값은 아래와 같습니다. answer = min(dist[N][0],dist[N][1],dist[N][2],dist[N][3],dist[N][4],...,dist[N][K]) .. 2021. 6. 28. [BOJ]1590번: 캠프가는 영식 https://www.acmicpc.net/problem/1590 버스의 갯수 와 각 버스의 대수가 각 각 10만이므로 N^2 탐색을 하면 시간초과가 납니다. 그러므로 한 종류의 버스에 대해 영식이가 최소 몇 분을 더 기다려야하는지 계산할 때 logN만에 탐색해야 합니다. 그래야 NlogN으로 시간제한을 통과할 수 있습니다. 제가 logN으로 시간복잡도를 줄인 방법은 이분탐색입니다. 이분 탐색을 사용하여 버스 도착 시간의 상한과 하한을 계산해서 영식이가 탈 수 있는 최초 버스 시간을 구했습니다. 코드: https://github.com/cotchan/algorithm/blob/main/java/BOJ/BOJ1590.java 2021. 6. 23. 이전 1 ··· 8 9 10 11 12 13 14 ··· 43 다음
