Algorithm

[BOJ] 17471. 게리맨더링 (Java)

문제 출처 백준 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 처음에 이 문제를 봤을 때, Union-Find 문제인 줄 알았으나, union-find로 접근하면 문제가 많이 복잡해진다. 해당 상황은 그래프가 서로 다 연결되어 있을 수 있지만, 구역을 나눔에 따라서 인접하고 인접하지 않고가 나뉘므로 생각을 다시 해봐야 한다. 필요한 개념 부분집합 구하기 그래프 탐색 → bfs 또는 dfs 풀이 N의 범위가 2≤N≤10 이므로, 시간 복잡도 안에 들어오므로 두 선거구로 나누는 부분은 부분집합을 재귀로 구현할 수 있을 것 같다. 선거..

[BOJ] 16437. 양 구출 작전 - Java

백준 16437 문제 풀이 과정 처음에는 그래프 문제라고 생각했고, 깊이 우선 탐색을 해야한다고 생각해서 깊이 우선으로 방문하는 코드를 짰다. 가장 끝 정점을 알고 그 부분부터 시작하면서 양을 만나면 더해주고, 늑대를 만나면 빼주는 코드로 짰지만 맞지 않았다. 트리를 통해 풀었더니 제대로 된 답을 낼 수 있었다. 해당 문제는, 어떠한 섬에서도 1번 섬으로 가는 경로가 유일하기 때문에 가장 끝 노드인 자식 노드부터 차례대로 늑대, 양의 개수를 누적하면서 1번까지 오면 결과가 나올 수 있는 문제이다. 따라서 트리 자료 구조를 이용하면 되고, postOrder(후위 순회) 방식을 이용하면 쉽게 풀 수 있다. 트리의 순회 전위 순회(preorder traverse) : 뿌리(root)를 먼저 방문 (Root →..

[BOJ] 1992. 쿼드트리 - Java

문제 출처 백준 기본적인 실수를 한 문제이다. 문제에서 전체가 0이거나 1이면 괄호가 출력되면 안되는데, 괄호 출력으로 틀린 문제이다. 풀이법 기본적인 분할 정복 문제이다. 절반씩 작아지며 분할 정복 기법을 사용하고, 4등분하여 재귀적으로 풀었다. 자세한 풀이는 주석을 달아서 생략한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_1992_쿼드트리 { static int N; static char[][] map; static StringBuilder sb = new StringBuilder();..

[BOJ] 17135. 캐슬디펜스 - Java

Java 알고리즘을 처음 연습하는 과정에서 어려움을 겪은 문제이다. 나는 해당 문제는 조합과 시뮬레이션을 함께 사용해서 풀었다. 어려움을 겪었던 부분이 몇 가지 있고, 알게 된 내용이 있다. 오류를 해결했던 부분 전체 맵을 계속 복사할 temp[] 배열에서 적을 없애는 과정을 하지 않아서 제대로 된 답이 나오지 않았었다. 중복으로 적을 공격해도 된다는 제약사항으로 HashSet 컬렉션을 사용했는데, 처음에 HashSet 를 사용하여 중복 제거가 제대로 이루어지지 않았던 것 같다. 이를 통해 클래스를 만들어 hashCode()와 equals() 메서드를 이용하여 중복체크 하는 부분을 공부하게 되었다. → 해당 과정에서, static 메서드 안에서 클래스를 사용하려면 static class를 만들어주어야 한..