알고리즘 (66) 썸네일형 리스트형 17144 - 미세먼지 안녕(G4) 문제 https://www.acmicpc.net/problem/17144 풀이 시뮬레이션 문제로, 사방탐색을 제외하면 별도의 특별한 알고리즘은 사용하지 않았다. 대개 헷갈릴 부분이 '미세먼지의 확산'을 구현하는 것이라고 생각되는데, 완전탐색으로 해당 기능을 수행하면 확산이 동시에 일어나는 것이 아니라, 이전 확산 값에 영향을 받는다. 이러한 문제를 해결하기 위해 1. 미세먼지 클래스를 생성 후, 완전탐색으로 조건에 맞는 미세먼지 객체를 생성하여 큐에 저장한다. 2. map(2차원 배열)의 값들을 전부 0으로 초기화하였다. 영향을 받게 하지 않기 위함으로, Dust Class의 내부 메서드로 확산량을 계산 후 값을 더해주는 방식으로 영향을 받지 않게 하였다. 3. 이후 자체 메서드로 구현한 바람으로 인한 .. 1780 - 종이의 개수(S2) 문제 https://www.acmicpc.net/problem/1780 풀이 간단하게 분할 정복으로 풀 수 있는 문제이다. 분할 정복을 사용하지 않으면 시간 초과 문제가 발생한다. 재귀함수를 사용하여 작은 범위로 나눈다. 나눈 범위를 카운팅하며 예외(다른 숫자)가 발생할 시 다음 단계로 분할하고, 아니라면 모두 카운팅 후 값을 증가시킨다. 코드 import java.util.*; import java.io.*; /* 분할 정복 사용. 자세한 것은 세부 주석 참조. */ public class Main { static int[][] board; static int res[] = {0, 0, 0}; // -1, 0, 1 public static void main(String[] args) throws IOE.. 2630 - 색종이 만들기(S2) 1. 문제 https://www.acmicpc.net/problem/2630 2. 풀이 색종이를 재귀함수를 통해 반복하여 분할정복하는 문제이다. 해당 문제를 풀기 위해 다음과 같은 방법을 설정할 수 있다. 주어진 색종이가 1 또는 0으로 이루어졌는지 확인한다. 해당 조건일 경우 값을 추가하고, 아닐 경우 4분할을 실행한다. 크기의 경우 size를 통해 확인하고, 분할 시행시 1/2로 줄여준다. 기저조건으로 size == 1을 설정한다. 이를 코드를 통해 보면 다음과 같다. 3. 코드 import java.util.*; public class Main { static int map[][]; static int[] res = new int[2]; public static void main(String[] a.. 11404 - 플로이드(G4) 1. 문제 https://www.acmicpc.net/problem/11404 2. 풀이 플로이드 워셜 알고리즘을 사용하여 쉽게 풀 수 있는 문제였다. 다만, 입력값 중 동일 경로에 다른 비용이 존재하는 점, INF 값을 너무 크게 할 경우 오버플로우가 날 수 있다는 점과 적을 경우 값이 적용되지 않는다는 점을 유의하도록 하자. 3. 코드 public class BOJ_11404_플로이드 { static final int INF = Integer.MAX_VALUE / 2 - 1; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.. 16928 - 뱀과사다리게임(G5) 1. 문제 https://www.acmicpc.net/problem/16928 문제 뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다. 주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까? 게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다. 플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다. 만약 주사위를 굴린 결과가 100번 칸을 넘어간.. 17141 - 연구소(G4) 문제 https://www.acmicpc.net/problem/17141 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다. 2.. 7576 - 토마토(G5) 1. 문제 https://www.acmicpc.net/problem/7576 입력 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 토마토가 하나 이상 있는 경우만 입력으로 주어진다. 출력 여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될.. 7662 - 이중 우선순위 큐(G4) 문제 이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다. 정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자. .. 이전 1 ··· 5 6 7 8 9 다음
