Algorithm/BaekJoon

[JAVA] 백준 2042 : 구간 합 구하기

문제 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 해결방법 안녕하세요 ! 글은 쓰고 있지 않지만 꾸준히 알고리즘을 풀이하고는 있는데 최근에 세그먼트 트리를 하게 되면서 기본 구조를 알 수 있는 문제는 기록을 해두면 좋을 것 같아서 오랜만에 글을 작성해 봅니다. 세그먼트 트리는 누적합의 다음 형태라고 볼 수 있는데 누적합의 경우 구간의 합은 O(1)에 구해지지만 중간에 값이 업데이트가 될 경우 O(N)만큼 시간이 소모되기 때문에 업데이트 횟수가 많다..

[JAVA] 백준 12764 : 싸지방에 간 준하

문제 12764번: 싸지방에 간 준하 첫째 줄에 사람의 수를 나타내는 \(N\)이 주어진다. \((1 \le N \le 100,000)\) 둘째 줄부터 \(N\)개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 \(P\)와 종료 시각 \(Q\)가 주어진다. \((0 \le P \lt Q \le 1,000 www.acmicpc.net 해결방법 대기하는 인원 없이 모두가 싸지방에 오자마자 컴퓨터를 이용하는데 필요한 컴퓨터의 개수를 구하고 각 자리별로 사용한 인원을 구하는 문제이다. 총 3개의 우선순위 큐를 활용했다. waitQ -> 대기인원 : 시작 시간이 적은 사람부터 먼저 꺼내서 확인하기 위함 playerQ -> 이용인원 : 현재 싸지방을 이용 중인 사람 comQ -> 사용가능한 컴퓨터 : 사용 가능한..

[JAVA] 백준 17141 : 연구소 2

문제 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 해결방법 오랜만에 BFS 탐색 문제이다. 이 문제의 경우 연구소에 특정 위치에 바이러스를 놓아서 연구소 전체를 바이러스에 감염시키려는 승원이의 계획을 도와주는 문제이다. 문제에서 맵에 2로 표시된 구역이 바이러스를 놓을 수 있는 공간인데, 그 공간 중 M만큼 바이러스를 놓았을 때 연구소 전체를 감염시킬 수 있는 가장 빠른 시간을 구해야 한다. 즉, 모든 경우의 수를 탐색해야 하는 완전 탐색 문제라고도 할 수 있다. 조합을 찾을 때는 비트 마스킹을 사용해서 방문 처리를..

[JAVA] 백준 1766 : 문제집

문제 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 해결방법 위상 정렬의 대표적인 문제 중에 하나이다. 근래 위상정렬 문제를 꾸준히 풀어보고 있는데, 풀 때마다 헷갈려서 정리를 한 번 해두려고 한다. 일단 위상정렬은 Topological Sort 라고 부르며, 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 쉽게 말하면 순서가 정해져있는 것들을 순서대로 나열하는 건데, 수학 2를 하기 전에 수학 1을 먼저 배워야 하고 그전에 기초수학을 배워야 하는..

[JAVA] 백준 1162 : 도로포장

문제 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 해결방법 1번에서 N번까지 가는 최소 시간을 출력하는 문제인데, 추가적으로 도로포장이라는 조건이 주어져있다. 포장이 가능한 횟수는 K로 주어지고, 포장을 하게 되면 해당 도시를 잇는 도로를 통과하는 시간이 0이 된다. 그래서 기본 다익스트라에 추가적으로 포장횟수를 기록해야 한다. 원래 배열은 dijk[해당 도시까지 최솟값] 을 나타낸다고 하면 이번 문제에서는 dijk[해당 도시까지 최솟값][포장 횟수] 를 사용한 2차원 ..