스도쿠의 값이 입력으로 주어지고 결과값을 출력해내는 문제입니다. 비트마스킹을 사용해서 각 가로, 세로, 사각형 부분에 어떤 값이 더 들어올 수 있는지 체크하였습니다. 체크되어있는 값들만 브루트포스 방식으로 전부 시도해보았습니다. 모든 값들이 적절히 들어갔을 때 스도쿠의 상태를 출력해주었습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { static int[][] map; ..
브루트포스 문제입니다. 퀸을 서로가 공격 할 수 없게 놓을 수 있는 경우의 수를 구해야 합니다. 퀸은 직선과 대각선에 있으면 공격할 수 있으므로 퀸의 직선과 대각선에 다른 퀸이 존재하지 않게 두어야합니다. 비트를 사용해서 아래와 같이 처리했습니다. 1은 왼쪽 대각선 2는 직선 4는 오른쪽 대각선 비트 값을 확인하여 다음 줄에 놓을 수 있는지 체크합니다. 체크가 안 된 위치에 퀸을 두고 다음 줄을 확인합니다. 위의 과정을 반복하여 마지막 줄까지 퀸을 둘 수 있는 경우를 카운팅해서 출력해 주었습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.Output..
문자열 문제입니다. (100+1+ | 01)+ 의 규칙을 가졌는지 확인하면 됩니다. 위의 규칙을 가졌을 경우 YES 가지지 않았을 경우 NO를 출력합니다. 단일 숫자는 해당 숫자가 존재하는지를 나타냅니다. 10 => 10이라는 숫자가 있어야함 1+ => 1이라는 숫자가 N개 존재 10+1 => 1과 1사이에 0이 N개 존재함 (1+ | 01)+ (1이 N개 있거나 0다음 1이 M개 있음)이 P개 있음 위와 같이 규칙이 존재합니다. 그렇다면 (100+1+ | 01)+ 의 경우에는 (100+1+ 또는 01+)가 N개 존재하는 경우 100+1+는 1 0 (0이 N개) (1이 M개) 있는 경우 01는 01이 있는 경우 if문을 잘 설정해서 위의 경우에 해당하는지 찾으면 됩니다. import java.io.Buf..
투포인터 문제입니다. N개의 수가 있을 때 좋은 수의 개수를 찾아야합니다. 좋은 수는 해당 수를 제외한 2개의 수의 합으로 만들어질 경우 좋은 수라고 합니다. 입력받은 수의 배열을 정렬해줍니다. for문을 통해서 차례대로 좋은수인지 체크합니다. 투포인터로 두 개의 합을 구하고 값이 클 경우 right -1, 값이 작을 경우 left + 1 을 해줍니다. 만약 두 개의 값이 같은 경우 찾는 수와 인덱스가 같은지 확인해주고 둘 다 다를 경우 좋은 수로 카운팅해줍니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; impor..
입구(1)에서 목적지(N)까지 이동할 수 있는지 찾는 문제입니다. BFS를 사용해서 탐색했습니다. 갈 수 있는 방향으로 모두 이동하며 visit배열을 두어서 이전보다 나은 상황에만 중복된 이동을 허용해 주었습니다. 신경 쓴 사항으로는 하나의 케이스가 끝났을 때 변수 값 초기화 해주기 visit배열을 int로 받아서 이전보다 돈을 많이 가진 경우에만 탐색할 수 있게 해주기 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.LinkedList; i..
집합 문제입니다. N명의 사람과 M개의 파티가 있을 때 지민이가 과장된 말을 할 수 있는 수를 구해야합니다. 매번 파티에서 사람들을 집합으로 묶어줍니다. 해당 파티에 진실을 아는사람이 있는지 확인합니다. M번의 파티를 탐색해서 진실을 아는 사람이 속한 집합인지 확인하고 속하지 않은 경우 결과값에 1을 더해주었습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; import java.util.Arrays; public class Main { public sta..
다이나믹 프로그래밍 문제입니다. N을 K개의 수로 만드는 경우의 수를 구해야 합니다. 수는 1~N이 있고 중복해서 사용할 수 있습니다. 2차원 DP배열을 만들어줍니다. dp[K개][N값] dp배열에는 a개의 개수가 있을때 b값을 만들 때 경우의 수를 저장합니다. for (int i = 2; i
트리 문제입니다. 노드 클래스를 생성합니다. static public class Node { Node left; Node right; int value; public Node(int value) { this.value = value; } 노드 클래스는 왼쪽 노드와 오른쪽 노드, 현재 값을 가집니다. 노드 클래스에 자식을 붙이는 함수를 추가해 주었습니다. public void makeChild(int num) { if (num < value) { if (this.left != null) { this.left.makeChild(num); } else { this.left = new Node(num); } } else { if (this.right != null) { this.right.makeChild(nu..