플루이드-워셜 알고리즘의 원리를 이용하여 정답을 구해내는 문제이다. 입력값으로 N개의 도시와 미리 계산해놓은 최솟값들을 입력받기 때문에 플루이드-워셜 알고리즘을 역으로 돌리며 인접 행렬을 구해내면 문제를 풀어낼 수 있다. 다음은 Java로 작성한 코드이다. import java.util.Scanner; public class RoadSum { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[][] map = new int[n][n]; int[][] adj = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = ..
플루이드 - 워셜 알고리즘(Floyd - Warshall algorithm) 플루이드-워셜 알고리즘은 최단 경로를 구하는 또 하나의 알고리즘이다. 알고리즘을 한 번 실행함으로써 모든 노드 간 최단 경로를 구할 수 있다. 인접 행렬을 이용하여 초기값을 설정한다. 가중치를 포함한 인접 행렬이 다음과 같다고 하자. 이 인접 행렬을 이용해서 다음과 같은 초기값을 만든다. 자신에서부터 자신까지의 거리는 항상 0이며, 직접 연결되어 있지 않은 경우에는 ∞로 초기화 한다. 초기값을 설정한 후에는 n번째 노드부터 중간 노드가 되어, 중간 노드를 거쳐 다른 노드로 갈 수 있는 값들을 업데이트시킨다. n번 반복하면 모든 노드까지의 최단 거리를 알 수 있다. 다음은 Java로 작성한 코드이다. public class Flo..
섬의 크기를 입력받고, map을 입력받은 뒤, 1은 섬, 0 은 바다라 가정한다. 섬에서는 상, 하, 좌, 우, 네방향의 대각선을 포함하여 총 8가지의 이동경로를 가질 수 있다. 하지만, 바다인 경우에는 움직일 수 없다. 즉, 0, 0 위치부터 섬을 찾은 후, 움직일 수 있는 위치까지 모두 방문한 뒤 방문 여부를 기록하면 섬을 중복하여 셀 경우를 피할 수 있고, 방문하지 않은 섬을 새로 발견할 경우 같은 방식으로 진행하면 지도의 모든 섬의 수를 셀 수 있다. 섬을 발견한 경우 깊이 우선 탐색을 이용하여, 갈 수 있는 모든 섬을 방문한 뒤 기록하는 방식으로 문제를 푸는 것이다. 다음은 Java로 작성한 코드이다. import java.util.ArrayList; import java.util.Scanner..
다익스트라 알고리즘(Dijkstra's algorithm) 다익스트라 알고리즘(Dijkstra's algorithm)은 벨만-포드 알고리즘처럼 특정한 노드에서 시작하여 그래프의 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라는 벨만-포드 알고리즘에 비해 좀 더 효율적이기 때문에 그래프가 큰 경우에도 사용할 수 있다는 장점이 있다. 하지만, 이 알고리즘은 음수인 가중치를 가진 간선이 있는 경우에는 사용할 수 없다는 단점이 있다. 다익스트라 알고리즘도 벨만-포드 알고리즘처럼 각 노드까지의 거리를 저장하고 탐색 과정에서 값을 줄여나간다. 각 단계에서는 아직 처리하지 않는 노드 중 거리가 가장 작은 노드를 찾고, 그 노드에서 시작하는 모든 간선을 쭉 살펴보며 노드까지의 거리를 줄일 수 있다면 줄인..
🔥4차 산업 스마트 융합 SW 개발자 양성과정🔥 해당 과정은 C, C#, Python, Javascript 를 진행 중이며 총 91일간 진행됩니다. 또한 무료교육으로 진행되며 매달 훈련장려금 월 최대 335,000원을 비롯하여 지방 거주자 정착금 추가 200,000원 지급됩니다. 취업연계과정이며 실무 프로젝트 위주의 과정으로 포트폴리오 제작도 진행됩니다. 신청문의는 031-606-9319 / 신청방법 : http://edu2.kosta.or.kr/ 공지사항 35번을 참조하시면 됩니다!!
벨만-포드 알고리즘(Bellman-Ford algorithm) 벨만-포드 알고리즘은 시작 노드에서부터 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 이 알고리즘으로 길이가 음수인 사이클을 포함하지 않는 모든 종류의 그래프를 처리할 수 있다. 그래프에 음수 사이클이 있는 경우에는 이를 찾아낼 수도 있다. 이 알고리즘에서는 시작 노드에서 다른 모든 노드까지의 길이를 모두 추적한다. 거리의 초기값은 시작 노드의 경우 0이고 다른 모든 노드의 경우 무한대의 값으로 설정된다. 그리고 이 값을 계속해서 줄여나가는 과정을 더는 줄일 수 있는 값이 없을 때까지 반복한다. 초기 시작 거리가 1인 노드 탐색 거리가 2인 노드 탐색 거리가 3인 노드 탐색 위와 같은 식으로 거리를 줄여나간다. 이후에 거리를 더 줄..
두 수열이 주어졌을 때, 가장 긴 공통 수열을 찾아내는 문제이다. 앞서 풀었던 가장 긴 증가하는 부분 수열과 비슷하다고 생각할 수 있지만 조금 다른 문제이다. for문을 여러 번 돌려 메모제이션을 이용하여 문제를 풀려했었다. 하지만, 문자열을 계속해서 반복하고 어디까지 일치하는지를 기록해야 하고, 건너뛰는 요소가 있을 수 있기 때문에 쉽지 않았다. 해답은 2차원 배열을 이용한 메모제이션이였다. 입력받은 두 문자열 길이보다 1씩 큰 2차원 배열을 생성한 뒤, 0번째 column과 0번째 row을 0으로 초기화 한 뒤, 문제를 풀어나가면 된다. 0으로 채우는 이유는 기저 조건을 설정하는 것이다. 2중 for문을 이용하여 row와 column의 각 요소들을 비교하며 진행한다. 그러다 일치하는 요소가 발견되면,..
