문제 링크 : https://www.acmicpc.net/problem/1753 이 문제는 다익스트라 알고리즘을 사용할 줄 아는지 묻는 문제이다.따라서 다익스트라 알고리즘을 코드로 구현만 해주면 된다. 간단하게 다익스트라 알고리즘을 알아보자. 만약 위와 같은 모양의 그래프가 있다고 가정해 보자.그래프 문제에서 가중치가 있는 간선을 다룰 때는 인접 리스트를 표현할 때클래스를 하나 생성하여 다음 정점과 해당 정점까지의 거리를 표현할 수 있다. 인접 리스트로 가중치가 있는 그래프를 표현한다면위와 같이 표현할 수 있을 것이다. 이제 다익스트라 알고리즘을 시작하기 전에시작 정점에서 각각의 정점까지의 거리를 나타내는 dist 배열과PriorityQueue인 pq를 초기화한다.이때 (정점, 시작정점부터 해당 정점까지..

문제 링크 : https://www.acmicpc.net/problem/1043 문제를 살펴보면 처음에는 단순히 진실을 말해야 하는 사람들이 포함되어 있는 파티에 참여한 모든 사람들에게만진실을 말해야 한다고 생각할 수 있다. 위의 예제는 보면 진실되게 말해야만 하는 사람이 포함되어있지 않은 상태이다.이럴 때는 모든 파티에서 과장되게 말해도 된다.이번에는 예제 5번을 보자여기서 1, 2, 3, 4번은 이미 진실을 알고 있는 사람들이다.따라서 첫 번째 파티의 참여한 1, 5번 중 5번은 진실을 모르는 사람이지만 1번이 포함되어있기때문에 지민이는 진실을 말해야 하고 따라서 5번도 진실을 알게된 사람이 된다.  만약 5번이 임의의 파티에 참석했다고 가정하자해당 파티에는 이미 진실을 알고 있는 1, 2, 3, 4..

문제 링크 : https://www.acmicpc.net/problem/1976 해당 문제는 유니온 파인드를 사용해야 한다는 것만 알아차리면나머지는 유니온 파인드를 구현하는 문제이기 때문에 쉽게 해결할 수 있다. 처음에는 각각의 노드의 집합의 대표노드는 자기 자신인 상태를 만든다.이후 문제에서 들어오는 입력을 잘 받아 union 메서드를 호출한다. 예제의 입력대로 1번 노드와 2번 노드가 이어져있기 때문에2번 노드가 속한 집합의 대표노드를 1로 변경해준다. 이후 들어온 입력값으로 3번 노드는 2번 노드와 이어져있으니여기서도 3번 노드가 속한 집합의 대표노드를 1로 변경해 준다. 마지막에 들어오는 입력값을 통해 목적지로 가려고 하는 곳들의대표노드를 검사하여 모두 동일한 집합이라는 것을 확인하면"YES" 다..

문제 링크 : https://www.acmicpc.net/problem/1377 문제를 접근하면 C++ 을 이용하여 정렬을 하는데 이때 버블 소트 알고리즘을 이용해서 정렬 하였다.위 문제에서는 오름차순 정렬을 하고있다.버블 소트 알고리즘은 배열에서 arr[i] 값과 arr[i+1] 값을 비교하여 만약 arr[i] 값이 더 크다면arr[i]와 arr[i+1] 의 값을 swap 한다. 이런식으로 하나하나 값을 비교하며 정렬하기 때문에정렬에 필요한 시간복잡도는 O(N^2)이 된다. 해당 문제에서 C++ 로 작성된 코드를 보면스왑이 한번도 일어나지 않는경우의 i의 값을 출력하는것을 알 수 있다. 단순히 위의 C++ 코드로 구현된 버블 소트 알고리즘을 자바로 옮겨서 풀 수 있지만문제는 문제의 입력값이 최대 500..