문제 링크 : https://www.acmicpc.net/problem/11403 특정 정점에서 각 정점까지 연결이 되어있는지를 물어보는 문제이다.플로이드 워셜 알고리즘을 이용하면 되는데 여기서 이 문제는 최단거리를 물어보는 문제가 아니기 때문에 이 문제와는 다르게 최단거리를 업데이트해주는 부분만 변형해 주면 된다. 플로이드 워셜이 S부터 E까지의 최단 거리는 S와 E 사이에 있는 K 정점을 기준으로 S -> K + K -> E까지의 거리가 기존의 S -> E 까지의 거리보다 가깝다면 업데이트를 해주는 방식이었다. 이 문제에서는 S -> K 까지 연결되어 있고 K -> E까지 연결되어 있다면 S -> E는 연결되어 있다는 로직으로수정해 주면 된다. package boj;import java.util.*;..

문제 링크 : https://www.acmicpc.net/problem/11404 문제의 이름이 플로이드인 만큼 플로이드-워셜 알고리즘을 사용하는 문제이다.플로이드 워셜 알고리즘은 모든 정점사이 간의 최단거리를 알아내는 알고리즘으로정점의 개수가 N 이라고 했을 때 시간복잡도가 O(N^3)인 알고리즘이다.따라서 플로이드 워셜 알고리즘을 사용하는 문제는 정점의 개수인 N이 작다는 특징이 있다. 우선 플로이드 워셜 알고리즘을 구현하기 위해 인접 행렬을 만들어주고값을 채워준다. 여기서 값이 의미하는 것은 arr[S][E] 는 정점 S부터 정점 E 까지 가는데 드는 최소비용이라는 의미이다.여기서 S와 E가 동일하다면 움직이지 않는것을 의미하기 때문에 0으로 초기화해준다. 그리고 3중 for문을 이용해서 위의 점화..

문제 링크 : https://www.acmicpc.net/problem/11657 이 문제는 1번 도시에서 출발해서 각 도시까지의 최단 거리를 출력하는 문제이다. 여기까지만 보면 다익스트라 알고리즘을 이용하면 될 것처럼 보이지만다익스트라 알고리즘을 사용하기 위한 조건중 하나는 무조건 에지가 양수여야 한다는 것이다.하지만 이 문제를 조건을 보면 에지의 값이 음수도 가능하다. 따라서 다익스트라가 아닌벨만 포드 알고리즘을 사용해서 풀어야 한다. 벨만 포드 알고리즘은 시작 정점부터 각각의 정점까지의 최단거리도 구할 수 있지만 음수 사이클이 존재하는지여부도 알 수 있다. 예제 1번을 보면 위와 같이 음수 사이클이 생성되는 것을 알 수 있다. 벨만 포드 알고리즘을 수행하기 위해서 우선 거리배열을 선언하는데 이때 출..

서버와의 통신이 필요 없고단순히 프론트엔드만 있는 프로젝트를 곧바로 url로 보여주고 싶을 때사용할 수 있는 아주 쉽고 빠른 방법이 있어 실습해 봤다. 먼저 github에서 public으로 repo를 하나 생성해 준다. private로 하면 이후 단계에서 사용이 불가하니 꼭 public으로 해야 한다.  생성이 된 후 리포에 들어오면 이런 화면을 볼 수 있다.여기서 . 을 누르면 편집이 가능한 dev 화면으로 넘어갈 수 있다. 해당 화면에서는 vscode처럼 파일을 생성하고 편집할 수 있다. 간단하게 index.html 파일을 만들어준다. 해당 페이지에서 곧바로 commit 메시지를 입력하고 커밋 및 푸시를 할 수 있다. 푸시가 정상적으로 되면 repo에서 index.html파일의 경로 url을 복사한다..