본문 바로가기

Algorithm

 (172)
[BOJ-1038][완전 탐색/조합] 감소하는 수 - Java 문제 바로가기 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 �� www.acmicpc.net N 번째 감소하는 수를 구하는 문제입니다. import java.io.*; import java.util.*; public class Main { static int[] numbers = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; static List nums = new ArrayList(); static List depthList; public static void comb(int depth, int idx, i..
[BOJ-16235][시뮬레이션] 나무 재테크 - Java 문제 바로가기 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 빡구현 문제입니다. 비교적 빠른 시간에 다 짜고 제출했는데 시간초과가 떠서 쪼끔 골치 아팠슴니다... import java.io.*; import java.util.*; public class Main { static List[][] trees; static int[][] map; static int[][] nutrient; static int N, M, K; static int[] dy = {-1, -1, -1, 0, 0, 1, 1..
[BOJ-16234][시뮬레이션/BFS] 인구 이동 - Java 문제 바로가기 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모�� www.acmicpc.net 인접한 나라를 고려한다? 그렇다면 BFS져! import java.io.*; import java.util.*; public class Main { static class Dir{ int y, x; public Dir(int y, int x) { this.y = y; this.x = x; } } static int[][] map; static int N, L, R; static boolean[][] v; static int[] dy..
[BOJ-15685][시뮬레이션] 드래곤 커브 - Java 문제 바로가기 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커� www.acmicpc.net 전형적인 시뮬레이션에 규칙을 찾으면 아주 쉽게 풀 수 있는 문제입니다. import java.io.*; import java.util.*; public class Main { static int[] dy = {0, -1, 0, 1}; static int[] dx = {1, 0, -1, 0}; static boolean[][] map = new boolean[101][101]; public static void makeDr..
[BOJ-2252][위상 정렬] 줄 세우기 - Java 문제 바로가기 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이�� 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(Sy..
위상 정렬(Topological Sort) 위상 정렬이란? 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 ..
[BOJ-16500][DP] 문자열 판별 - Java 문제 바로가기 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 �� www.acmicpc.net DP 엉엉 그래도 풀고야 말앗다 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)); Set A = new HashSet(); int[] d..
[BOJ-2477][구현] 참외밭 - Java 문제 바로가기 2477번: 참외밭 첫 번째 줄에 1m^2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1≤K≤20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나� www.acmicpc.net 문제에서 요구하는 답은 아주 간단합니다. 근데 인풋이 좀 희한하게 들어와서 쪼끔 생각해주어야 합니다. import java.io.*; import java.util.*; public class Main { static class Info{ int dir, length; Info(int dir, int length){ this.dir = dir; this.length = length; } } public static void main(String[]..

티스토리툴바