요약 Knpasack Problem은 보통 배낭 문제로 불리며 여러 바리에이션이 존재한다. 대표적인 바리에이션인 분할 가능한 아이템을 사용한 배낭 문제는 그리디 알고리즘을 이용하여 해결할 수 있다. 하지만 분할 가능하지 않은 아이템을 사용할 경우 완전 탐색과 다이나믹 프로그래밍 중 시간 복잡도를 비교하여 선택할 수 있다. 다이나믹 프로그래밍에서 최적...

요약 LCS 문제는 두 수열의 최장 공통 부분 수열을 찾아야 한다. 이 문제는 최적화된 부분 문제를 가지고 있다. X와 Y 일부분(prefix)의 LCS를 찾은 결과는 X와 Y의 LCS를 찾을 때 재활용된다. 따라서 이는 다이나믹 프로그래밍으로 해결할 수 있다. LCS를 찾기 위해 브루트 포스를 사용하면 O(N2^N)의 시간 복잡도를 가지지만 다이나믹...

알고리즘 분류 : 자료 구조, 해시를 사용한 집합과 맵, 분리 집합 https://www.acmicpc.net/problem/4195 요약 기존의 유니온 파인드 알고리즘은 입력이 정수로 주어지는데 이번 문제는 문자열이 주어졌다. 평소 Map을 사용한 경험이 있다면 문자열을 어렵지 않게 정수로 변환할 수 있다. 문제에서 전체 사람 수가 주어지...

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

알고리즘 분류 : 최단 거리, 다익스트라 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 요약 모든 노드 사이의 거리를 그래프 탐색으로 구해서 최장 거리를 찾을려고 하면 시간 초과가 발생하는 문제이다. 트리에서 임의의 한 점에서 가장 먼 지점은 트리 지름의 시작점이다는 점을 알고 있으면 임의의 ...