본문 바로가기

Algorithm/BOJ

 (101)
[BOJ-1300][이분 탐색] K번째 수 - Java 문제 바로가기 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 후 급하게 삼성 면접 보고 와씀다;; 요 문제는 K- 씨리즈의 끝판왕 K-번째 수입니다.ㅎㅋ 이분 탐색으로 풀면 되는데, 어떻게 N^2를 돌리지 않고 배열에 있는 수를 체크하느냐가 관건입니다. import java.io.*; import java.util.*; public class Main { static int N, k; public static void main(String[] args) throws Except..
[BOJ-1261][BFS] 알고스팟 - Java 문제 바로가기 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 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[]..
[BOJ-1005][위상 정렬] ACM Craft - Java 문제 바로가기 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net W번 건물을 짓는데 걸리는 시간을 구하는 문제입니다. 위상 정렬을 해서 쉽게 풀 수 있씁니다. import java.io.*; import java.util.*; public class Main { static int N, K, W; static int[] buildTime; static List[] graph; static int[] inDegree; static BufferedReader br = new BufferedReader(new ..
[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(..
[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..

티스토리툴바