풀이 문제 자체는 If Else 조건문만 잘 활용하면 되는 간단한 알고리즘의 문제였으나문제의 주어진 조건을 한번에 정확히 이해하기에는 조금은 실수의 여지가 있지 않나 싶었던 문제였다. X보다 가깝다 && X보다 숙박비가 더 비싸다 -> 후보의 가능성 만족X보다 멀다 -> 숙박비에 상관없이 후보의 가능성이 있다. X보다 싸다 && X보다 거리가 멀다 -> 후보의 가능성 만족X보다 비싸다 -> 거리에 상관없이 후보의 가능성이 있다. 즉, 후보의 가능성이 없는 숙소들은X보다 가까우면서 숙박비가 싼 경우, X보다 싸면서 거리가 가까운 경우 이 2가지 밖에 없다. 이 부분을 제대로 이해하지 못해 꽤나 시간이 걸렸던 문제였던 것 같다. 숙소를 나타내는 클래스를 하나 생성하고 인스턴스들을 배열화하여 숙소의 리스트들을..

풀이 문제 자체는 다익스트라 알고리즘을 이용해서 한 노드에서 다른 모든 노드들에 이르는최단 경로를 출력하면 되는 간단한 문제였다. 우선순위 큐 (Priority Queue)를 이용해서 다익스트라 알고리즘을 구현했고, 우선순위 큐를 이용하기 위해서 목적지 노드의 인덱스와 시작점으로부터의 거리를 저장하는 Element라는 원소 클래스를 정의하였다. *우선순위큐를 이용한 다익스트라 알고리즘은 시간 복잡도가 O(ElogV)정도이다. 문제는 간단했으나, 문제에 걸린 제약조건이 보기보다 꽤나 까다로웠다. 맨 처음에는 인접행렬과 Scanner를 통해 알고리즘을 수행했으나메모리초과와 시간초과가 동시에 발생하였다. 메모리 초과 이유는 인접행렬을 사용했기 때문인데,예를 들어 2만개의 노드가 존재한다면, Integer형을 ..

풀이 플로이드 와샬 알고리즘을 응용해야 하는 쉽지만은 않은 문제였던것 같다.숫자에 의미를 부여하여 그래프를 구성해야 하고, 이 의미를 부여하여 그래프를 완성하는 과정 자체가생각해내기 쉽지는 않았다. 문제 해결을 위한 생각의 과정은 다음과 같다.예를 들어 1 2 0 이라는 input이 주어지면 1에서 2로 가는 경로를 dis[1][2] 배열에 생성한다. 즉, 0이라는 값을 배열에 넣어준다는 것이다. 그리고 여기서 중요한 것이 2에서 1로 가는 경로가 없지만, 1에서 2로 가는 경로가 있기 때문에양방향의 경로가 연결될 가능성이 있으므로, 1이라는 값을 dis[2][1]에 넣어준다. 다시말해서, 이미 단방향이든, 양방향이든 경로가 있으면 거기에는 도로를 추가할 일이 없으므로 0을 넣어주고단방향의 경로가 없지만..

풀이 저울 문제는 그래프 이론과 연관지으려고 한다면 플로이드 와샬 알고리즘을 이용해서 그리 어렵지 않게 해결할 수 있는 문제이다.물건 1보다 2가 가벼운 경우, 즉 1 > 2 인 경우, 1에서 2로 가는 유향 그래프의 경로가 있다고 생각하면 된다.이렇게 생각하면 물건 1과의 비교 결과를 알 수 없는 물건의 개수는 플로이드 와샬 알고리즘을 이용하여 각각의 물건에 대해 경로가 없는 물건의 개수, 즉 거리가 inifinite한 점들의 개수를 카운트 해주면 된다. 따라서 플로이드 와샬 알고리즘을 그대로 적용하되,무방향 그래프가 아닌 유향 그래프임을 감안하여 해결해주어야 하며, 또 한 가지 주의할 점은, 1 > 2 라는 결과값이 주어졌을 때에는물건 1에 대해 2도 비교할 수 있을 뿐더러물건 2에 대해 1도 비교할..

풀이 플로이드 와샬 알고리즘을 조금만 응용할 수 있다면 쉽게 해결되는 문제이다.그래프의 가중치를 저장하는 dis 배열과 같이 동작하는 count배열을 추가하였다.이 count 배열은 dis 배열이 갱신될 때마다 중간에 얼마나 많은 정점들이 연결되는 지를 카운트하여 저장하는 배열이다. 예를들어1 - 2 를 연결하는 가중치를 나타내는 dis[1][2] 값이1 - 3 - 2로 갱신될 때 count[1][2]값이 count[1][3] + count[3][2] 값으로 갱신되는 것이다. 이렇게 모든 점에 대해서 플로이드 알고리즘을 한바퀴 돌고 나면, dis배열과 count배열이 갱신되게 되고각각의 count값을 i값에 대해 합을 낸 것을 구하면, 각 i 값에 따른 케빈 베이컨의 수가 나오게 된다. 정리하면, 배열 ..

풀이 플로이드 와샬 알고리즘을 이용해서 각 점의 경로 여부를 확인하면 간단하게 해결할 수 있는 문제였다.플로이드 와샬 알고리즘이란 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘으로, Kruscal, Prim알고리즘과는 달리 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리할 수 있다는 장점이 있다. 하지만, 반복문을 3번 돌리기 때문에 O(n^3)의 시간복잡도를 가지므로 이 점은 유의해야 한다.3개의 반복문은 각각 다음과 같다. 첫 번째 - 거쳐가는 점두 번째 - 출발하는 점세 번째 - 도착하는 점 위 문제는 경로가 있는지 유무만 판단하는 것이므로 초기값을 100이상의 값으로 설정하고플로이드 와샬 알고리즘을 수행하여 거리를 저장한 배열의 값이 100 이상이면 경로가 없는 것으로 간주하..