문제 난이도GOLD I (링크)   문제 풀이각각의 독립된 섬들을 최단 거리로 연결하고 싶을 때, 놓을 수 있는 다리의 총 길이의 최소값을 구하는 문제.역시나 최소 신장 트리를 응용한 문제가 되겠다. 이번에는 각 간선을 구하는 것과 더불어, 이 섬이 어느 정점인지를 구하는 것도 필요하다. 결국엔 두 정점 사이의 간선을 구해서 문제를 풀어야하기 때문이다.  위의 그림처럼 문제에서 요한 3가지 올바르지 않은 방법과 함께, 추가로 두 가지만 주의한다면 쉽게 풀 수 있다. 처음 다른 섬을 만났을 때 만족하지 않는 조건이라면 바로 빠져나올 것.부끄럽게도 처음 코드를 완성시켰을 때,  다른 섬을 만났을 때, 종료 조건을 부족하게 작성하여 아래 그림처럼 더이상 탐색하지 못함에도 불구하고 탐색을 시켰다.   Union..

문제 난이도GOLD III   1774번 풀이간선의 가중치가 주어지지 않아 간선의 가중치를 구하는 로직만 추가해준다면 쉽게 문제를 해결할 수 있다. 이 문제에서 간선의 가중치는 2차원에 있는 신들의 위치 사이의 거리를 구하는 것으로, 아래 공식처럼 유클리드 거리 계산 방법을 이용하면 쉽게 가중치를 구할 수 있다.   위 공식을 코드로 나타낸다면 아래와 같다. private static double calCost(int x1, int x2, int y1, int y2) {    return Math.sqrt(Math.pow(x1 - y1, 2) + Math.pow(x2 - y2, 2));}       크루스칼(Kruskal) 알고리즘 (with. 백준 1197번 최소 스패닝 트리)크루스칼 알고리즘 (Kru..

문제 난이도PLATINUM V (문제 링크)  풀이LIS 알고리즘을 이진 탐색을 통해 구현하면 되는 문제로 해당 문제를 어떻게 코드로 풀어낼 것인지에 대한 아이디어도 아래 포스팅에서 자세히 다루기 때문에 구체적인 설명은 필요하지 않을 것 같다. [알고리즘] LIS (Longest Increasing Subsequence)LIS(최장 증가 부분 수열)N크기의 배열이 주어졌을때, 배열에서 일부 원소를 조합하여 만든 부분 수열 중, 오름차순의 조건을 만족하면서 길이가 최대인 부분 수열을 말한다. 아래처럼, {3, 6, 2, 1,mag1c.tistory.com  간단하게 복기하자면, 해당 문제는 전깃줄의 개수가 최대 100,000개이기 때문에, DP로 LIS를 구현해서는 풀 수가 없다.  전깃줄의 시작지점을 오..

문제 난이도GOLD II (문제 링크)  풀이사칙연산에서의 연산 우선순위의 특징과 스택을 활용해서 풀 수 있다. 다들 알겠지만 리마인드하고 넘어가자면,1. 곱셈과 나눗셈은, 덧셈과 뺄셈보다 우선으로 연산된다.2. 괄호가 존재할 경우, 가장 먼저 처리된다.3. 우선순위가 같을 경우, 좌결합성의 특성에 따라 왼쪽의 수식을 우선처리한다.   또한 문제의 예제와, 그림표기된 것을 보고도 방법을 캐치할 수 있는데,   사칙 연산의 우선순위 특징을 리마인드했고, 어떻게 문제를 풀어나가야할지 통해 정리해볼 수 있다. 연산은 선출력하는 것이 아니라, 이전 연산자가 존재할 경우, 이전 연산과의 우선순위를 판별해서 출력 여부를 결정해야한다.괄호는 우선 연산이 되기때문에, 괄호 시작 부분을 만났을 경우에, 괄호가 끝나는 시..

문제 난이도GOLD III (문제 링크)  풀이 [알고리즘] 벨만-포드(Bellman-Ford) 알고리즘벨만-포드 알고리즘은 그래프의 최단 경로를 구하는 알고리즘의 하나로, 다익스트라로 해결하지 못하는 음의 간선이 포함된 문제를 효과적으로 해결할 수 있는 알고리즘이다.  [알고리즘] 다mag1c.tistory.com 포스팅에서 학습했기 때문에 자세한 설명은 생략하고, 풀었던 방법만 나열해보고자 한다. 벨만-포드 알고리즘은 특정 출발점에서 모든 노드로의 최단 경로를 탐색하는 알고리즘이다. 또한 음수 사이클을 검출할 수 있다. 도달할 수 없는 노드를 표시하기 위해 INF에 가까운 값들로 초기화해서 사용할 수 있다.  첫번째 방법문제에서, 특정 노드를 언급하지 않았다. 한 노드에서 출발하여~~~이기 때문에, ..

문제 난이도GOLD II (문제 링크)   풀이두 노드 간의 최장 경로인 트리의 지름을 구하는 문제이다. 모든 경우의 수를 구해서, 가장 큰 값을 찾아야하기 때문에 DFS에 적합하다. DFS 구현은 단순하니 이를 통해 문제를 쉽게 해결할 수 있다.//dfs 호출부int max = 0;for (int i = 1; i     메모리 초과는 단순 이차원 배열을 통해 각 노드의 경우의 수를 계산했기 때문에 발생했다.이는 리스트로 구현하여 해결하였다.  하지만, 모든 경우의 수를 구하면 시간 초과가 발생하는데, 모든 경우의 수를 구하게 되면 O(V^2)이 되며, 문제 조건에서 V가 100,000까지이기 때문에 최적화할 수 있는 방법이 필요하다. 임의의 노드 x에서 최장 경로 노드를 DFS를 통해 구했고, 이를 y..

문제 난이도GOLD III  문제 링크https://www.acmicpc.net/problem/1238   풀이 [알고리즘] 다익스트라(Dijkstra) 알고리즘다익스트라(Dijkstra) 알고리즘그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다. 탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로,mag1c.tistory.com 위의 다익스트라 알고리즘을 사용해서 구현한 문제이다.    문제 예시를 그림으로 표현해보았다.목적지로의 최단거리만 구하면 됐던 기본적인 다익스트라 알고리즘 구현 문제에서, 반대로 2에서 각 노드의 최단 경로를 한번 더 구해주기만 하면 된다. (A -> X, X -> A) private static int[] dijkstra..

문제 링크 Gold 4 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net https://mag1c.tistory.com/452 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘 그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다. 탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로, mag1c.tistory.com 풀이 방향..