본문 바로가기

알고리즘

[백준] 17144번 - 미세먼지 안녕! (Java) ⬛ 문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net ⬛ 풀이 시뮬레이션 문제이다. 모든 먼지들을 동시에 확산시키는 부분이 핵심인 문제였던 것 같다. 프로그램 전체 로직은 다음과 같다. 1. 기존 map과 별개로 spread[][] 라는 임시 공간을 만들어 확산된 먼지들을 더해놓는다. 2. 모든 먼지 확산이 끝나면 map과 spread를 합치고 spread 공간을 0으로 초기화시켜준다. 3. 먼지확산 + 공기청정기 가동을 1cycle로 놓.. Algorithm/백준 2021. 9. 15.
[백준] 17472번 - 다리 만들기2 (Java) ⬛ 문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net ⬛ 풀이 최소신장트리(MST) 문제이다. 프로그램 전체 로직은 다음과 같다. 1. bfs를 사용해 섬 별로 번호를 붙여 country[][]를 생성한다. 2. country[][]를 탐색하여 0이 아닐 시(섬이면) 4방을 탐색하고 만약 0이라면 해당 섬의 가장자리라는 뜻이다. 3. 해당방향으로 다리 생성을 시도하고 성공한다면 Bridge를 생성하여 pq에 삽입한다. .. Algorithm/백준 2021. 9. 15.
[백준] 1992번 - 쿼드트리 (Java) ⬛ 문제 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net ⬛ 풀이 기본적인 분할-정복 문제이다. 영역을 탐색하여 하나라도 다른 숫자가 있다면 4개의 영역으로 분할한다. 다시 그 영역들은 좌측 상단 좌표부터 시작하여 탐색을 시작하고 또 그중에서 다른 숫자가 있다면 4개의 영역으로 분할한다. 만약 영역 사이즈가 1이라면 더 이상 분할하지 않고 해당 문자를 출력한다. ⬛ 코드 import java.io.BufferedReader; imp.. Algorithm/백준 2021. 8. 22.
[백준] 11559번 - Puyo Puyo (Java) ⬛ 문제 https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net ⬛ 풀이 BFS를 활용한 시뮬레이션 문제이다. 프로그램 전체 로직은 다음과 같다. 1. 이차원 배열 map을 탐색 중 R, G, B, P, Y 라면 상하좌우를 체크하고 같은 색이라면 탐색 큐에 추가한다. 2. 큐에 추가할 때 방문 체크를 해놓고, 탐색 길이가 4 이상이라면 탐색한 좌표들을 '.'으로 바꾼다. (터뜨리기) 3. 끝까지 탐색을 완료하면 chain 카운.. Algorithm/백준 2021. 8. 15.
[백준] 1068번 - 트리 (Java) ⬛ 문제 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net ⬛ 풀이 얼핏보면 주어진 입력대로 트리를 구성하고, DFS를 통해 리프노드 갯수를 구하는 단순한 문제이다. 하지만 문제 어디에도 입력 트리가 이진 트리라는 말도, 입력 값이 오름차순이라는 말도, 루트가 하나라는 전제도 없다. (물론 이번 문제는 루트는 하나이다.) 초반에 입력이 오름차순일 것이라고 가정하여 IndexOutOfBounds를 줄기차게 먹었다;; 프로그램 전체 로직은 다음.. Algorithm/백준 2021. 8. 15.
[백준] 2231번 - 분해합 (Java) ⬛ 문제 https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net ⬛ 풀이 전형적인 브루트포스 문제이다. 1 이상 1,000,000 이하인 자연수 N이 주어졌을 때 N의 가장 작은 생성자를 구해야 한다. 어떤 자연수 M의 분해합이 N일 때 M은 N의 생성자이다. (ex. 245의 분해합 = 245 + 2 + 4 + 5) 1,000,000은 생성자가 없기 때문에 N은 최대 6자리 자연수이다. 따라서 생성자를 M이라 할 때 N .. Algorithm/백준 2021. 7. 28.
728x90
반응형

티스토리툴바