https://www.acmicpc.net/problem/16234 문제 유형BFS & DFS구현 문제 난이도Gold 4 문제 분석해당 문제를 읽어보면 누가봐도 BFS를 활용하면 된다는 것을 알 수 있다.다만, 문제를 잘읽고 문제에서 필요한 구현에 맞춰서 약간의 커스터마이징이 필요하다.1. 상하좌우로 국경을 마주치는 구역들의 인구수의 차(절댓값)이 L이상 R이하일 경우, 연합으로 친다.2. 모든 구역에 대해 연합들을 묶은 다음"연합에 해당하는 칸들의 모든 인구수 = 연합의 인구수 / 연합을 이루고 있는 칸의 개수" 로 모두 갱신해준다.3. 이와 같은 행동을 반복하되, 만약 인구 이동의 변화가 없을 경우 종료한다.요구사항에 대한 코드는 아래에 나와있다.전체 코드package _250821;import ja..

https://www.acmicpc.net/problem/14438 문제 유형세그먼트 트리 문제 난이도Gold1 문제 분석해당 문제는 다음과 같다.길이가 N인 수열이 주어진다. 주어진 쿼리에 따라 수열의 값을 갱신 혹은 구간에 대한 최솟값을 출력한다.기본적으로 구간에 대한 합 또는 최솟값 등을 찾는데 구간에 대한 범위가 크다면 세그먼트 트리를 떠올리면 좋을 것 같다는 생각이 들었다. 그렇지 않으면 일반적인 선형 탐색으로는 시간초과를 피할 수 없기 떄문이다.해당 문제는 일반적인 세그먼트와 다른 부분이 있다면, 세그먼트 트리는 구간에 대한 구간 합을 구하는 것이었다면 해당 문제는 구간에서 가장 최솟값을 출력하는 것이었다. 그래서 이전 세그먼트 트리 코드와 약간 차이가 있다. 코드 분석 세그먼트 트리 높이크기..

https://www.acmicpc.net/problem/1766 문제 유형위상정렬 문제 난이도Gold2 문제 분석해당 문제는 위상 정렬을 이용하는 문제이다.문제의 조건은 다음과 같다.1. N개의 문제는 모두 풀어야 한다.2. 먼저 푸는 것이 좋은 문제가 있는 문제는 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.3. 가능하면 쉬운 문제푸터 풀어야 한다.2번의 조건을 보고, 선후관계를 가진 조건을 가지고 있다는 것을 보고 위상 정렬을 생각하였다.3번의 조건을 보고 풀어야 될 문제라면 문제의 번호가 적은 번호 먼저 풀어야 하므로, minHeap을 생각하게 되었고, 우선순위 큐를 활용하여, 문제 번호가 작은 것부터 출력하도록 하였다. 전체 코드package _250811;import java.util..

https://www.acmicpc.net/problem/2169 문제 유형다이나믹 프로그래밍 문제 난이도Gold 2 문제 분석 해당 문제는 DP를 활용하는 문제이다.문제의 조건은 다음과 같다.1. 로봇은 왼쪽, 오른쪽, 아래쪽으로만 이동할 수 있다.2. 한 번 지나간 지역은 다시 지나지 않는다.3. (1,1) -> (N, M)으로 이동할 때, 지역들의 가치가 최대가 되도록 출력한다.따라서, 다음 방향중에서 가치가 최대가 되는 것을 찾아야한다.1. 위 -> 아래2. 왼쪽 -> 오른쪽3. 오른쪽 -> 왼쪽 우선 첫번째 행 같은 경우, 왼쪽에서 오른쪽으로 가는 값들을 더할 때가 최대가 될 수 밖에 없다.-> 시작점(1,1)을 기준으로 다른 방향으로 이동해서 도착시, 아래 -> 위 방향으로 이동할 수 밖에 ..

https://www.acmicpc.net/problem/2252 문제 유형위상 정렬 문제 난이도Gold3 문제 분석해당 문제는 주어진 선후 관계 조건이 있을 때, 이를 고려해서 노드의 순서를 고려하는 위상 정렬의 문제였다.위상 정렬 관련 문제는 처음 풀어보는거라서 위상 정렬 관련 정리 블로그들을 참고해서 문제를 풀어보았다.위상 정렬의 조건은 다음과 같다.1. DAG(Directed Acyclic Graph), 방향성이 있으며, 사이클이 없는 그래프 ex) A -> B, B -> A (X)2. DFS를 사용하거나 indegree 배열을 사용하여 구현한다.쉬운 방법은 indegree를 사용해서 진입 차수에 대해서 카운팅을 해준뒤, 진입 차수가 0인 노드, 해당 문제에서는 다른 노드와의 관계가 없거나, 가..