알고리즘/백준
-
[백준] 22942. 데이터 체커 - Java알고리즘/백준 2021. 9. 14. 22:17
🖇️ 문제 링크 22942번: 데이터 체커 원 이동하기 2 문제를 만들고 만든 데이터가 문제의 조건에 맞는지 확인하는 코드를 작성해야한다. 해당 문제의 데이터는 아래 조건들을 만족해야한다. 모든 원의 중심 좌표는 $x$축 위에 존재해야 한다. $N$개의 원 중 임의의 두 원을 선택했을 때, 교점이 존재하지 않아야 한다. 즉, 하나의 원이 다른 원 안에 존재하거나 외부에 존재한다. https://www.acmicpc.net/problem/22942 💡 문제 분석 모든 원의 중심 좌표는 x축에 위치합니다. 원{왼쪽 좌표, 오른쪽 좌표}형태로 리스트에 저장 후, 왼쪽 좌표 기준 오름차순으로 정렬합니다. 정렬 후 인접 원과 겹치는 부분이 있다면 false를 리턴합니다. ⌨️ 코드 import java.io.*;..
-
[백준] 2800. 괄호 제거 - Java알고리즘/백준 2021. 9. 14. 22:17
🖇️ 문제 링크 2800번: 괄호 제거 https://www.acmicpc.net/problem/2800 💡 문제 분석 괄호쌍의 인덱스를 리스트에 저장해놓습니다 괄호쌍들의 집합으로 공집합을 제외하고 모든 부분집합을 생성합니다. 생성한 부분집합에 따라, 괄호쌍들을 제거하고 결과 리스트에 저장합니다. 사전순으로 정렬한 후 출력합니다 ⌨️ 코드 import java.util.*; public class Q2800 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.next(); Deque stk = new ArrayDeque(); List pair = new ArrayList(); List ..
-
[백준] 2346. 풍선 터뜨리기 - Java알고리즘/백준 2021. 9. 14. 22:17
🖇️ 문제 링크 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다. https://www.acmicpc.net/problem/2346 💡 문제 분석 덱 자료구조를 이용해서 앞, 뒤를 연결시켜줍니다. 덱에서 원소를 poll()했을 때, 자동으로 오른쪽으로 한 칸은 이동하기 때문에, 오른쪽으로 이동할 때는 1칸 덜 이동시킵니다. ⌨️ 코드 import java...
-
[백준] 2075. N번째 큰 수 - Java알고리즘/백준 2021. 9. 14. 22:17
🖇️ 문제 링크 2075번: N번째 큰 수 이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다. https://www.acmicpc.net/problem/2075 💡 문제 분석 TreeSet을 통해서 내림차순 정렬을 유지합니다. 입력을 받으면서 가장 큰 n개의 수만 저장합니다. ⌨️ 코드 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); TreeSet ts = new TreeSet(Comparator.reverseOrder()); for(int i = 0; ..
-
[백준] 13209. 검역소 - Java알고리즘/백준 2021. 9. 14. 22:16
🖇️ 문제 링크 13209번: 검역소 3번 도시와 5번 도시를 잇는 도로와 4번 도시와 3번 도시를 잇는 도로에 검역소를 설치하면 치료제를 11 인분만 비축해도 된다. 1번 도시에 전염병이 발생할 경우 1번 도시와 3번 도시의 10명의 사람들이, 2번 도시에 전염병이 발생할 경우 2번 도시와 4번 도시의 11명의 사람들이, 3번 도시에 발생할 경우 10명, 4 번 도시에 발생할 경우 11명, 5번 도시에 발생할 경우 5명이 감염될 수 있으므로 어느 경우에도 11인분의 치료제로 충분히 전염병을 막을 수 있다. https://www.acmicpc.net/problem/13209 💡 문제 분석 파라메트릭 서치로 검역소마다 limit개 이하의 치료제로 K개의 검역소를 운영할 수 있는지를 구합니다. 검역소 한 개..
-
[백준] 17953. 디저트 - Java알고리즘/백준 2021. 9. 4. 15:14
🖇️ 문제 링크 17953번: 디저트 창호는 매일 점심마다 디저트를 먹는다. 그런데 같은 디저트라도 매일 느끼는 맛이 달라진다. 어떤 날에는 마카롱을 먹고 매우 행복함을 느끼는 반면 어떤 날에는 '차라리 케이크를 먹는게 나았지 않았을까' 하는 식이다. 이럴 때 케이크를 다시 먹으면 좋겠지만, 창호는 건강을 위해 디저트는 하루에 한 가지만 먹기로 정해 놓았다. 어느 날 창호는 이런 '만족감'에 패턴이 있는 것을 알아냈다. https://www.acmicpc.net/problem/17953 💡 문제 분석 💡 dp(day, prev) = 전날에 prev번째 디저트를 먹었을 때, day일 이후 얻을 수 있는 만족도 전 날에 먹은 디저트가 무엇인가에 따라 다음날 만족도가 바뀌기 때문에, 전날 먹은 디저트를 함께 ..
-
[백준] 17471. 게리맨더링 - Java알고리즘/백준 2021. 9. 4. 15:14
🖇️ 문제 링크 17471번: 게리맨더링 문제 백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다. https://www.acmicpc.net/problem/17471 💡 문제 분석 각 구역을 두 개의 선거구로 나눕니다. 총 N개의 구역이 있다면, (1, N - 1), (2, N - 2) ... (N/ 2, N/2) 형태로 나눕니다. 두 개로 나눈 선거구가 각각 연결되어 있는지 그래프 탐색으로 확인합니다. 만약 ..
-
[백준] 17070. 파이프 옮기기 - Java알고리즘/백준 2021. 9. 4. 15:14
🖇️ 문제 링크 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. https://www.acmicpc.net/problem/17070 💡 문제 분석 💡 dfs(y, x, d) = 현재 파이프가 (y, x) 위치이고 방향이 d일 때 목표 지점에 갈 수 있는 경우의 수 파이프의 위치와 방향에 따라 경우의 수를 계산하며, 다이내믹 프로그래밍을 진행합니다. ⌨️ 코드 import java...