본문 바로가기

Algorithm

 (172)
[BOJ-2239][백트래킹] 스도쿠 - Java 문제 바로가기 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 와 스도쿠 문제입니다. 예전에 진짜 많이 했는데 n-Queen 이랑 궤를 같이 한다고 생각합니다. 둘 수 있는 애 두다가 안되면 백트래킹.. import java.io.*; import java.util.*; public class Main { static class Dir{ int y, x; Dir(int y, int x){ this.y = y; this.x = x; } } static int[][] board = new int[9][9];..
[BOJ-1644][에라토스테네스의 체/투 포인터] 소수의 연속합 - Java 문제 바로가기 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net N이 주어졌을 때 소수의 연속합으로 N을 만들 수 있는 경우의 수를 구하는 문제입니다. 에라토스테네스의 체로 소수들을 구하고 투 포인터로 간단하게 풀었습니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); ..
[BOJ-12015][이분 탐색] 가장 긴 증가하는 부분 수열 2 - Java 문제 바로가기 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net PS에서 유명한 시리즈인 LIS 를 구하는 문제입니다. 보통 DP로 많이 푸는데 이 문제는 인풋 사이즈가 커서 N^2을 돌리면 터집니다. import java.io.*; import java.util.*; public class Main { static int N; static List sequence = new ArrayList(); public static void main(String[] args) throws Exception { input(..
[SWEA-5656][BFS/백트래킹] [모의 SW 역량테스트] 벽돌 깨기 - Java SWEA에 있는 모의 SW 역량테스트 문제입니다. 쪼끔 번거로워 보이는데 백트래킹도 쓰고 BFS도 쓰고 재밌는 문제랍니다. import java.io.*; import java.util.*; public class Solution { static class Dir{ int y, x; Dir(int y, int x){ this.y = y; this.x = x; } } static int[] dy = {-1, 0, 1, 0}; static int[] dx = {0, 1, 0, -1}; static int N, W, H, answer = Integer.MAX_VALUE; static int[][] map; public static void main(String[] args) throws IOException ..
[BOJ-3954][시뮬레이션] Brainf**k 인터프리터 - Java 문제 바로가기 3954번: Brainf**k 인터프리터 각 테스트 케이스에 대해서, 프로그램이 종료된다면 "Terminates"를, 무한 루프에 빠지게 된다면 "Loops"를 출력한다. 무한 루프에 빠졌을 때는, 프로그램의 어느 부분이 무한 루프인지를 출력한다. ([ www.acmicpc.net 닉값하는 문젭니다. 메모리 초과에서 한참 걸렸네여 ㅜ import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWr..
[BOJ-17136][백트래킹/완전 탐색] 색종이 붙이기 - Java 문제 바로가기 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 아 어렵다 백트래킹~~!!! 예전에는 얼토당토않게 풀었다 틀렸는데 많은 도움받고 겨우 풀어씀다.. import java.io.*; import java.util.*; public class Main { static int[][] map = new int [10][10]; static int[] paper = {0, 5, 5, 5, 5, 5}; static int answer = Integer.MAX_VALUE; public static vo..
[BOJ-2636][BFS] 치즈 - Java 문제 바로가기 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 오랜만에 BFS 문제입니다. 치즈의 구멍을 둘러싼 치즈는 녹지 않도록 하는게 관건입니다. import java.io.*; import java.util.*; public class Main { static class Dir{ int y, x; Dir(int y, int x){ this.y = y; this.x = x; } } static int N, M; static int[][] map; static int remained, last; static int[] dy ..
[BOJ-17070][시뮬레이션/백트래킹] 파이프 옮기기 1 - Java 문제 바로가기 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 삼성 SW 역량 테스트 A형 기출 문제입니다. 아주 단순한 백트래킹 문제입니다. import java.io.*; import java.util.*; public class Main { static int N, answer; static int[][] map; static int[] dy = {0, 1, 1}; static int[] dx = {1, 1, 0}; public static void main(String[] arg..

티스토리툴바