[문제]https://www.acmicpc.net/problem/32620그래프를 탐색하는 데 있어서, 이웃 노드를 하나 이상 점령한다는 점에서 BFS 탐색을 떠올렸습니다. 또한 i번 노드로 이동하는 데 있어, 현재 기력이 요구하는 기력 이상이라면 이동할 수 있다는 점에서 그리디 접근 법을 떠올렸습니다. 즉 이동하고자 하는 노드와 인접한 노드를 방문한 상태이고, 요구하는 기력이 현재 기력 이하라면 모든 노드를 탐색할 수 있다는 점에서 최대한 많은 노드를 탐색해야 얻을 수 있는 기력을 최대로 만들 수 있습니다. 그렇기 때문에 BFS 탐색에 사용하는 자료구조로 일반적인 큐를 사용하지 않고 우선순위 큐를 사용해, 인접하면서 요구하는 기력이 작은 순으로 탐색하는 것입니다. 요약하자면다음 노드를 방문하기 위해서는..
java
[문제]https://www.acmicpc.net/problem/7490 단순한 백트래킹에 공백이라는 조건을 추가해서 약간의 생각을 하게 만드는 문제였습니다.[초기화] static ArrayList results; static int n; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int tc = Integer.parseInt(br.readLine()); for (int t = 0; t (); search("1", 1, 1, 1)..
[문제]https://www.acmicpc.net/problem/18430주어진 위치에 모든 부메랑을 놔보며 강도를 최대로 만들어야 하는 문제입니다. 어떤 모양, 어떤 위치일 때 최대인지 모르기 때문에 백트래킹을 통해 모든 경우의 수를 검사하면 되겠습니다.[초기화] static int[][][] boomerangs = { // 부메랑의 4가지 형태를 표현 (중심 포함) {{0, 0}, {1, 0}, {0, 1}}, // 「 {{0, 0}, {0, 1}, {-1, 0}}, // ㄱ {{0, 0}, {-1, 0}, {0, -1}}, // 」 {{0, 0}, {0, -1}, {1, 0}} // ㄴ }; public static void ma..
[문제]https://www.acmicpc.net/problem/13975 비용을 줄일 수 있는 가장 직관적인 방법은 비용이 가장 작은 파일 두 개를 선택해서 취합하는 것입니다. 취합된 파일을 다시 선택지에 두고, 다시 한번 비용이 가장 작은 파일 두 개 선택. 위 과정을 하나의 파일이 남을 때까지 반복하면 해결할 수 있는 그리디 문제로 Python이 아닌 경우 데이터의 자료형에 신경 써야 합니다.[초기화] public static void main(String[] args) throws IOException { t = Integer.parseInt(br.readLine()); for(int tc = 0; tc 합산되는 숫자들이 커질 것을 대비해, 처음부터 long 타입으로 데이터를 입력받습니다.[풀..
[문제]https://www.acmicpc.net/problem/2169 처음에는 다익스트라를 생각하고 문제에 접근했으나, 모든 정점을 확인할 수 없어 dp로 풀어낸 문제입니다. dp 문제답게 풀이가 길지 않습니다. 또한 코드트리에서 연습했던 dp 빈출 유형과 유사한 문제였습니다.[초기화] static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int n, m; static int[][] map; public static void main(String[] args) throws IOException { st = new StringTokenizer(br..
[문제]https://www.acmicpc.net/problem/14442조건에 따라 최단 경로가 달리지는 문제입니다. 벽 부수고 이동하기와의 차이점은 벽을 부수는 횟수 차이입니다. 최근에 봤던 기업의 코딩테스트에서 유사한 유형의 문제가 출제되었습니다. 조건에 따라 다르게 이동하는 테크닉을 익혀두는 것도 좋을 거 같습니다. https://www.acmicpc.net/problem/1600위 문제도 해당 문제와 풀이 방식이 유사합니다.[초기화] static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int n, m, k; static char[][] map;..
[문제]https://www.acmicpc.net/problem/2295처음에는 세 용액 문제처럼 기준을 잡고 나머지 두 수에 대해 투 포인터로 탐색을 진행하려고 했습니다. 하지만 최대에 대한 기준이 없기 때문에 적용하지 못했고, 집합 자료구조를 이용해 만들어낼 수 있는 수를 체크하는 방식으로 문제를 풀이했습니다.[초기화] static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static int n; static int[] u; static int answer = 0; public static void main(String[] args) throws IOException { n = Integer.parseInt(..
[문제]https://www.acmicpc.net/problem/13913일반적인 그래프 형태의 BFS가 아닌 특이한 형태의 BFS입니다. 해당 시리즈 문제를 풀어본 경험이 있어서 풀 수 있었고, 처음 해당 유형의 문제를 풀 때는 정답을 보고 이해했었습니다. 해당 문제는 BFS + 경로 역추적을 수행하는 문제로 보면 되겠습니다.[초기화] static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int n, k; static int[] time; public static void main(String[] args) throws IOException { s..
[문제]https://www.acmicpc.net/problem/12100오랜만에 높은 난이도의 문제를 풀어보았는데, 전혀 Easy하지 않았습니다. 풀이 방식 자체는 어렵지 않게 떠올렸는데, 보드를 조작하는 과정에서 원상 복귀하는 것을 고려하지 않아 디버깅에 3시간을 헤맨 문제입니다. 또한 생각한 풀이가 너무나도 삼성스럽길래 찾아보니 기출문제가 맞았습니다.https://www.acmicpc.net/problem/15683이 문제와 유사한 거 같습니다.[초기화]public class BOJ_12100_2048Easy { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer s..
[문제]https://www.acmicpc.net/problem/9466문제를 단순하게 표현하면, 형성된 그래프에서 사이클에 속하지 않는 노드의 수를 찾으면 되는 문제입니다. 여기서 노드는 학생을 의미합니다.12345673137346문제의 예시를 그래프로 나타내면 다음과 같은 모습을 나타내게 됩니다. 여기서 사이클에 속하지 않는 노드는 1, 2, 5 총 3개가 됩니다. 위와 같이 그래프로 표현해 보고, 문제에서 제시하는 바가 사이클에 속하지 않는 노드를 찾아야 한다는 것을 알 수 있었습니다. 문제 자체는, BFS와 DFS 모두 수행가능하지만, 최단 경로를 찾는 문제도 아니고 탐색 과정을 추적하는 과정에서 별도의 비용일 발생하는 BFS보다 DFS가 적합하기 때문에, 해당 방식으로 문제를 풀어냈습니다. 제 ..
