막내의 막무가내 프로그래밍 & 일상

www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 백준 BFS 유형의 백준 2146 다리만들기 문제입니다. 여러개의 섬이(1) 있는데 바다에(0) 최소의 다리 개수를 설치하여 여러개의 섬들 중 두 개의 섬을 이을 수 있게 하려는 문제 입니다. BFS를 살짝 응용한 문제입니다. 처음에 너무 비효율적으로 자원을 소비하는건가 했는데 통과되었습니다. 풀이를 간략히 설명하면, 1. 섬마다 번호가 똑같으므로 바로 BFS로 다른 섬을 찾아 연결하기가 힘듭니다. 그러므로 섬에 각..

programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 최근 백준만 풀다가 오랜만에 프로그래머스 문제를 풀어본 것 같습니다. 예전에는 프로그래머스에 적응이 되어 백준의 입력값을 직접 받아야한다는점이 거부감이 있었는데 이제 프로그래머스가 뭔가 어색하네요. ㅎㅎ 프로그래머스 고득점 kit 그래프 종류에 있던 Level 3 문제입니다. 최단경로 문제인가 했는데 최단 경로가 아닌 최장 경로의 개수가 몇개인지 묻는 문제이고 간선의 가중치는 1로 모두 동일하다는 특징을 갖고 있습니다. 저는 평소 최단경로 문제푸..

www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 백준 최소신장트리 문제인 행성 터널 문제를 풀어봤습니다. ㅎㅎ 처음에 평소대로 푼 후 제출을 하였는데 메모리 초과가 일어났습니다. //모든 행성 관계 연결(엣지 초기화) for (int i = 0; i < N - 1; i++) { Space space = spaces[i]; for (int j = i + 1; j < N; j++) { Space space2 = spaces[j];..