문제 링크 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 풀이 - 앞서 MST 문제 풀이하다가 '트리의 지름'에 대한 이론을 알게 되었고, 관련 문제 풀이함 '트리의 지름'에 대한 강의 영상을 찾아보니 초보 알고리즘이란다 (하하하.. 심플하긴하다) https://dev-ljw1126.tistory.com/369 [BOJ20010] 악덕 영주 혜유 (크루스칼, 프림, MST, 최소신장트리, 트리의 지름) 문제 링크 http..

문제 링크 https://www.acmicpc.net/problem/20010 20010번: 악덕 영주 혜유 FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net 문제 풀이 최소 가중치를 가지는 MST는 구했는데, 두번째 값을 구하지 못해 3시간을 소비했다. 찾아본 결과 트리의 지름을 구하는 방법을 몰랐고, 문제 지문을 제대로 읽지 못해 MST 트리 정보를 활용하는 것을 파악하지 못했다..(반성) 문제 지문을 다시 보면 아래와 같다 마음이 괘씸한 혜유는 돈을 최대한 적게 쓰면서 퀘스트를 달성하려고 한다. 혜유를 도와서 (1)모든 마을과 마을을 ..

문제 링크 https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 문제 풀이 문제를 접근할 때 우물을 무조건 하나 파야 한다고 생각해서 제일 적은 비용이 드는 우물을 기준으로 구했으나 '틀렸습니다' 만 나왔다 기술 블로그를 찾아본 결과, 우물을 하나 파는 행위를 간선(Edge) 정보로 추가해서 풀이해야 했다. - 임의 노드 0번에 {i번 논, 논을 파는 비용} 으로 정의해서 컬렉션에 담는다 - 그리고 0번 노드부터 시작하..

문제 링크 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 풀이 - 별자리(노드)를 모두 연결하는 최소 비용을 구하는 문제 - 프림 알고리즘으로 풀이 (최소신장트리, MST) - 시간 복잡도 : O(ElogV) 1) 2차원 좌표로 입력 주어지는데 각각 노드 1, 2, .. 로 보고 노드별 거리 값을 계산하여 컬렉션에 담는다 (양방향 그래프) 2) 시작 노드는 1로 고정해서 프림 알고리즘 수행 - 방문한적 있으면 continue; - 방문한적..

문제 링크 https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 문제 풀이 - 프림 알고리즘(최소 신장트리) 사용하여 풀이 - 시간 복잡도 : O(ElogV) 절차 1) 모든 컴퓨터(노드)를 연결하는 최소 랜선 길이(비용)을 구한다. 2) 다솜이가 가진 총 랜선 길이에서 최소 랜선 길이 뺀 나머지를 기부 한다 알파벳이 소문자인지, 대문자인지 구분하는 방법이 조금 애매했는데 이번 문제를 통해 Character 클래스에 유용한 메서드를 알게 되었다..

문제 링크 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 문제 풀이 그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다. 위의 지문이 조금 이해가 안되었는데, 사이클이 발생하는 경우에 대해 설명하는 것으로 이해했다. - 크루스칼/프림 알고리즘 (최소 신장트리,MST) 사용하여 최소 비용을 구한 후 전체 비용과의 차..

문제 링크 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 문제 풀이 크루스칼 알고리즘을 사용하기 위해 노드와 노드 사이의 비용 정보가 필요한데, 2차원 좌표(X, Y)가 주어질 때 노드로 생각하지 못했고, 거리 계산 또한 생각을 하지 못했다. 해당 문제를 통해 시야가 또 좁아진 점을 반성한다.. 입력 예시 4 1 // 노드 수, 연결된 노드 수 1 1 // 노드 1 3 1 // 노드 2 2 3 // 노드 3 4 3 ..

문제 링크 https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 문제 풀이 문제 지문에 " 무게가 중간이 절대로 될 수 없는 구슬의 수 " 키워드 였다. 풀어서 적어보자면 자기보다 크거나 작은 구슬의 개수가 중간 개수가 넘어가면 절대 중간이 될 수 없는 구슬이다. - 플로이드 워셜 풀이 - 시간 복잡도 : O(N^3) + O(N^2) // 플로이드 워셜 알고리즘 + 각 구슬별로 크거나 작은 구슬 카운팅 - 구슬 절반 개수 : ( N..

문제 링크 https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 풀이 - 시간 복잡도 : O(N^3) - 플로이드 워셜 공식 활용하여 각 노드별 최단 경로는 구한다 floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j] i -> j로 바로가는 비용과 k 를 거쳐 가는 i -> k -> j 비용 중 작은 값을 구한다 경로 추적 - (1,1) ~ (N, N) 까지 경로 추적하는 부분에서 시작과 끝 ..

문제 링크 https://www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 문제 풀이 - 플로이드 워셜 기본 문제 - 시간 복잡도 = 플로이드 워셜 수행 + 친구 별 방에 대한 최단 거리 합산 + 최소 비용 가지는 방 번호 구하기 = O(N^3) + (N^2) + (N) (최대 친구 수는 N 이하, N번 방) 절차 1) 각 노드별 다른 노드에 대한 최단 경로를 플로이드 워셜 알고리즘으로 구한다, 시간 복잡도 O(N^3) 2) 친구별 방에 대한 최단 거리 비용을..

문제 링크 https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 문제 풀이 플로이드 워셜로 각 노드별 다른 노드에 대한 최단 경로를 구할 수 있었다. 그런데 출발 행성 K 위치가 주어졌을 때 다른 행성을 탐색하는데 걸리는 시간을 어떻게 구할 지에서 삽질을 여러번 하였다. 결국 재귀 함수 사용한 완전 탐색으로 구하면 방문 여부 체크하며 구하면 되는 문제였다. "이미 방문한 행성도 중복해서 갈 수 있다"는 문제 지문이 함정이 아니었나 싶다 스스로 ..

문제 링크 https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 문제 풀이 - 단방향 그래프 - 주어진 입력에 따라 인접 행렬을 초기화 및 입력 가중치(1) 설정 - 플로이드 워셜 알고리즘을 실행해서, 각 노드별로 다른 노드 갈 수 있는지 구한다. - 시간 복잡도 : O(N) 각 케이스에 대해 1) 0 인 경우는 (i, j), (j, i) 둘다 INF로 확인 불가를 뜻함 // 입력 2) 1 인 경우 j와 i 두 값중 i 사건이 더 먼저 발생한..

문제 링크 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 문제 풀이 - 직접 풀이하지 못하여 아래 기술 블로그 참고 후 풀이 - 최소라는 단어에 매몰되어 이진 탐색 후 완전탐색을 해야 하나하고 삽질함 (당연히 시간초과) https://steady-coding.tistory.com/105 [BOJ] 백준 1507번 : 궁금한 민호 (JAVA) 문제 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, ..

문제 링크 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 문제 풀이 1) 각 노드별로 다른 노드에 대한 최단 거리를 구한다 (양방향 관계, 플로이드 워셜 알고리즘 사용) - 이때 시간복잡도 O(N^3) 2) 각 노드별 최단 거리를 구한 후 그 중 최대값이, 해당 노드의 회장 점수가 된다 3) 회장 점수가 최소가 되는 번호를 구해서 출력한다 문제에서 아래 부분이 조금 이해가 안 되었는데 결론은 각 노드별 최단 거리를 구해라는 의미였다 각 회원의..

문제 링크 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제 풀이 - 플로이드 워셜 카테고리 문제 (카테고리 몰랐으면 과연 풀었을까 싶다) - 노드별 사이클 발생할 경우 최단 거리 구함(시작 노드를 포함하는) - 시간 복잡도 : O(N^3) 플로이드 워셜의 경우 각 노드별로 다른 노드로 가는 최단 거리를 구하게 된다 이때 사이클이 발생한다는 것은 각 시작 노드의 최단 거리 값이 INF가 아니게 된다는 의미로..

문제 링크 https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 문제 풀이 - 다익스트라 알고리즘 문제 - 1 -> N 노드 까지 최단 거리 구하면 된다 - C_i마리 소 = 간선의 가중치 - 시간 복잡도 : O(ElogV) - 노드와 간선이 최대 50,000개 있으므로 O(50,000log50,000) = O(50,000 * 약 15.6) , 고로 1초만에 가능 제출 코드 import java.util.*; import java.io.*; public cl..

문제 링크 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 풀이 - 다익스트라 카테고리 분류되어 있어 다익스트라 알고리즘 방식으로 풀었다 - (1,1) -> (N, M) 까지 벽을 최소로 부숴야 하므로 우선 순위 큐를 사용 (부숴버린 벽돌 수에 대해 오름차순 정렬) 제출 코드 import java.util.*; import java.io.*; public class Main { static int n, m; stati..

문제 링크 https://www.acmicpc.net/problem/20166 20166번: 문자열 지옥에 빠진 호석 K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다. www.acmicpc.net 문제 풀이 중복 방문을 허용하고, 상하좌우 대각선(8개 방향) 방향으로 이동하여 문자열을 만듦 참고. 시간 복잡도 행 * 열 * (8방향으로 이동^최대 단어 길이 5) = 100 * (8^5) = 3,276,800 (1초안에 수행 가능) 참고. 방향 이동 관련하여 ( 3 x 3 ) (0, 0) 좌표에서 아래 대각선 방향으로 이동할 경우 맵의 범위를 벗나게 될 것이다 (-1, -1) (-1, 0) (-1, 1) (0, -1) 시작 (0, 1) (1, -1) (1, 0) (..