Algorithm PS

문제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 탐색 중에 각 숫자가 여러 번 방문되지 않도록 방문 처리를 하고, 각 탐색이 끝난 ..

문제https://www.acmicpc.net/problem/24480풀이이 문제는 그래프의 정점을 입력받아서 해당 정점들만 탐색하면 되므로 인접 리스트를 사용하는게 적절하다고 판단했다. 이번에는 이중 ArrayList를 사용하여 풀어봤다. 그래프의 내용을 저장할 ArrayList> graph를 만들어서 간선 정보를 입력받는다. 그리고 DFS를 이용하여 시작 정점에서 탐색을 시작한다. 각 정점을 방문할 때, 방문한 순번을 배열에 저장하고, DFS 탐색이 끝나면 저장했던 순번을 출력한다. 매우 사소한 실수로 메모리 초과가 발생했다...Codeimport java.io.*;import java.util.*;/*- 정점과 간선의 정보를 이용해서 출발 정점에서 각 정점을 방문하는 순번을 결과로 출력한다.- 시작..

문제https://www.acmicpc.net/problem/1012풀이graph를 생성하여 값들을 모두 입력 받고, for문으로 graph를 탐색하면서 graph의 현재 위치가 1(배추)이며, visited(방문하지 않은 곳)의 값이 false이면, dfs 또는 bfs를 실행하여 해당 지점을 기준으로 연결된 부분들을 방문처리하고 애벌래 개수를 증가시킨다. Dfs와 Bfs 모두 풀이가 가능하여 두 가지 방법으로 풀어보았다.CodeDfs 적용 (주석 변경으로 Bfs로도 적용 가능)import java.io.*;import java.util.ArrayDeque;import java.util.StringTokenizer;public class Main { static int T, M, N, K; s..

문제https://www.acmicpc.net/problem/1620풀이오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네. N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력을 받고, 입력받은 후에는 M개의 줄에 내가 맞춰야하는 문제가 입력으로 들어온다. 문제가 알파벳으로만 들어오면 포켓몬 번호를 말해야 하고, 숫자로만 들어오면 포켓몬 번호에 해당하는 문자를 출력해야 한다.  즉, HashMap 형태롤 ..