Algorithm PS

문제https://www.acmicpc.net/problem/7562풀이이전에 풀었던 BFS 관련 문제들과 거의 유사하며 차이점으로는 방향이 8방향으로 변형된 형태이다.도착지까지의 최소 이동 횟수를 구해야 하기 때문에 출발지에서 BFS 탐색을 하여 게임판 모든 좌표까지의 최소 이동 거리를 구한다.이후에 출력할 때, 도착지의 좌표에 저장된 이동 횟수를 출력한다.Codeimport java.util.*;import java.io.*;public class Main { static int [][] board; static boolean [][] visited; static int count = 0; static int l, nowX, nowY, desX, desY; static Qu..

문제https://www.acmicpc.net/problem/7569풀이해당 문제는 이전의 10026: 적록색약 문제와 유사하면 높이만 추가된 문제이다. 높이가 추가되었기 때문에 dh 배열을 추가하여 기존의 4방향(상, 하, 좌, 우)에 2방향(위, 아래)을 추가로 탐색해야 한다. 배열 선언은 3차원 배열이기 때문에 storage[h][n][m]처럼 첫 값에 높이가 들어가야 한다.Codeimport java.util.*;import java.io.*;public class Main { static int m, n, h; static int days = 0, yet = 0; static int [][][] storage; static boolean [][][] visited; s..

문제https://www.acmicpc.net/problem/10026 풀이적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못하는 것으로 빨간색과 초록색을 같은 색으로 판단한다.왼쪽의 그림을 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개(R: 2, G: 1, B: 1)이다.하지만, 적록색약인 사람이 봤을 때, 빨간색과 초록색을 같다고 판단하기 때문에 오른쪽의 그림처럼 총 3개(R/G: 2, B: 1)로 판단한다. 이 문제를 풀기 위해서는 적록색약인 경우와 아닌 경우를 구분하여 BFS 탐색을 하도록 풀면 된다.Codeimport java.util.*;import java.io.*;public class Main { static int n; static char [][] graph; ..

문제https://www.acmicpc.net/problem/20040풀이문제를 정리해보면 0부터 n-1 까지의 고유한 번호가 부여된 평면상의 점 n개가 주어지며, 이 중 어느 세점도 일직선 위에 놓이지 않는다.매 차례마다 이를 잇는 선분을 그린다. → 이전에 그은 선분을 다시 글을 수 없으며, 이미 그린 선분과 교차는 가능하다.처음으로 사이클(플레이어들이 그린 선분들의 부분집합)이 완성되는 순간 게임이 종료된다.게임의 진행 상황이 주어지면 몇 번째 차례에서 사이클이 완성 되었는지를 판단하고, 혹은 게임이 진행 중인지를 판단하는 프로그램을 작성해야 한다. 연결을 할 때마다 카운트를 하며 사이클이 생기면 종료를 해야하는데, 사이클을 판단하는 방법으로 Union-find 자료구조를 사용하면 된다.Union-..

문제https://www.acmicpc.net/problem/19238풀이위 문제의 핵심을 나열해 보며 아래와 같다.택시의 현재 위치 기준 가장 가까운 고객을 태워서 목적지에 데려다 준다.만약, 거리가 가까운 고객이 여러 명일 경우 행과 열이 작은 고객을 먼저 태운다.고객을 태우기 전 택시의 위치에서 고객의 위치까지 이동하는 동안 소비된 연료를 총 연료에서 차감한다. 그리고 목적지에 도착하면 손님이 탑승한 위치에서 목적지 까지의 연료를 차감한 후, 고객의 위치부터 목적지까지 이동하면서 소비한 연료의 양의 2배를 채운다.단, 연료가 떨어지면(0이 되면) 즉시 운행을 종료한다.모든 고객을 목적지에 데려갔을 때, 남아있는 연료의 양을 결과로 출력한다.모든 고객을 목적지에 데려가지 못할 경우, -1을 결과로 출..

문제https://www.acmicpc.net/problem/1629풀이그냥 단순하게 풀면 BufferOverflow 및 시간 초과가 발생하므로 분할 정복을 활용해야 하며, 지수 법칙과 모듈러 방식을 사용하여 진행해야 한다. 지수 법칙은 a^(n+m) = a^n * a^m으로 이를 활용하여 지수가 짝수인 경우와 홀수인 경우의 전개를 보면 아래와 같다.이를 트리 구조로 표현해 보면 아래와 같이 되는 것을 확인할 수 있다.여기까지만 간단하게 코드를 작성해보면 아래와 같다.public static long pow(long A, long exponent) { // 지수가 1일 경우 A^1 이므로 A % C를 리턴 if (exponent == 1) return A % C; /..

문제https://www.acmicpc.net/problem/1074풀이좌측의 그림은 8x8로 이를 4등분을 하면 우측의 그림이 된다. (row, column)의 좌표까지의 칸수를 계산하는 건데, 한 변은 2^N으로 정의한다. 예를 들어 r=4, c=3,N=3 일 때, 일단 한 변의 길이는 8이 되므로 cut(8, 4, 3)가 실행된다. half는 4등분을 했을 때, 4등분 한 사각형의 한 변의 길이이다. 첫 번째로 쪼개졌기 때문에 한 변의 길이인 half = 4가 된다.1 사분면의 시작 값인 0의 좌표 = (0, 0)2 사분면의 시작 값인 16의 좌표 = (0, half)3 사분면의 시작 값인 32의 좌표 = (half, 0)4 사분면의 시작 값인 48의 좌표 = (half, half)구하려는 좌표가 ..

문제https://www.acmicpc.net/problem/1780풀이색종이의 수가 모두 같은 수라면 이 색종이를 그대로 사용하지만 좌측의 그림과 같이 모두 같은 수가 아니라면 우측 그림처럼 9등분을 한다.현재는 row와 column 모두 9이므로 9등분을 하면 나눠진 색종이의 size는 이전의 size/3이 되어 3이 된다.나누어진 색종이를 좌표로 표현해보면 위와 같이 표현할 수 있다.N이 9 일 때의 결과를 보면 위 그림과 같이 나오는 것을 알 수 있다.Codeimport java.io.*;import java.util.StringTokenizer;public class Main { static int N; static int [][] arr; static int [] answer ..

문제https://www.acmicpc.net/problem/11725풀이해당 문제는 루트 없는 트리에서 각 노드의 부모를 찾아야 한다. 트리의 루트를 1로 정했을 때, 각 노드의 부모를 구하여 출력해야 한다. 우선 노드의 개수인 N을 입력받고, 이후 N-1개의 줄에서 두 노드의 연결 정보를 인접 리스트 구조로 입력는다.그리고 DFS를 시작하여 루트 노드(1)를 방문 처리하고, 연결된 모든 노드를 탐색하면서 각 노드의 부모 노드를 찾는다. DFS는 재귀적으로 호출되며, 현재 노드를 방문 처리하고, 연결된 노드 중 방문하지 않은 노드를 탐색하면서 부모 노드를 설정한다. 모든 노드의 부모를 찾은 후, 2번 노드부터 순서대로 부모 노드를 출력한다. Codeimport java.io.*;import java.u..

문제https://www.acmicpc.net/problem/2668풀이문제를 보면 표는 두 줄로 구성되어 있으며, 첫째 줄에는 1부터 N까지의 숫자가 순서대로, 둘째 줄에는 임의의 1이상 N 이하의 숫자가 들어 있다. 첫째 줄에서 숫자를 선택해서, 선택한 숫자들과 그 아래 둘째 줄의 숫자들이 이루는 집합이 일치해야 한다. 그리고 선택된 숫자들의 개수가 최대가 되어야 한다. 각 숫자에서 시작하여 둘째 줄의 숫자를 따라가다가 출발 숫자를 다시 만나면 사이클이 형성된다. 사이클을 찾기 위해 DFS를 사용했다. 각 숫자의 출발점으로 DFS를 수행하여 사이클을 찾아내고, 그 사이클에 속하는 숫자들을 결과 리스트에 추가한다.DFS 탐색 중에 각 숫자가 여러 번 방문되지 않도록 방문 처리를 하고, 각 탐색이 끝난 ..