아래 모든 내용은 “프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략, 구종만 저, 인사이트” 책을 바탕으로 공부하여 정리하였습니다. 요약 유니온 파인드가 할 수 있는 일은 대부분 다른 그래프 알고리즘이나 자료 구조로도 할 수 있다. 하지만 구현이 매우 간단하고 동작 속도가 아주 빠르기 때문에 가능한 경우 유니온 파인드를 사용하는 것이 좋다...

알고리즘 분류 : 최단 거리, 다익스트라 https://www.acmicpc.net/problem/1504 요약 두 노드 사이에 가중치가 있는 그래프이므로 다익스트라를 이용할 수 있다. 이 때 두 정점을 통과해야 한다는 추가 조건이 있는데 두 정점을 A, B라고 하자. 이 문제는 1번 정점 -> A -> B -> N번 정점,...

요약 static 메서드를 mockito-inline과 PowerMockito 등으로 mocking을 할 수 있다. 하지만 static 메서드를 mocking하기 전에 애초에 static 메서드가 잘 설계 되어 있는지 고려해야 한다. Instant.now(Clock)과 같이 static 메서드가 순수 함수로 잘 설계되었다면 static 메서드의 moc...

알고리즘 분류 : 최단 거리, 다익스트라 https://www.acmicpc.net/problem/1238 요약 두 노드 사이에 가중치(시간)가 있는 그래프이므로 BFS를 이용한 최단 거리 탐색은 사용할 수 없다. 하지만 음의 간선은 존재하지 않으므로 이 경우 대표적인 다익스트라 알고리즘을 이용하여 풀 수 있다. 다익스트라는 한 노드에서 다...

알고리즘 분류 : 그래프 이론, 그래프 탐색, 트리, 깊이 우선 탐색 https://www.acmicpc.net/problem/1167 요약 모든 노드 사이의 거리를 그래프 탐색으로 구해서 최장 거리를 찾을려고 하면 시간 초과가 발생하는 문제이다. 트리에서 임의의 한 점에서 가장 먼 지점은 트리 지름의 시작점이다는 점을 알고 있으면 임의의 ...