개발하는 고라니

1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net [소수 판별] 정수 x를 입력받아 소수인지 확인하는 방법은 2부터 x의 제곱근까지의 수를 x와 나머지 연산했을 때 결과가 0이면 소수가 아니라고 판별한다. # Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int cnt = 0; static boolean isPrime(int x){ if(x ==..

13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net [BFS] 정답률 25%를 과시라도 하듯 결코 쉽지않은 문제이다. 문제에 주어진 조건 중 몇 가지가 특히 어떻게 접근해야할지 난해했다. 그 중에 '빨간 구슬(R)과 파란 구슬(B)은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다.' 가 특히나 골치아팠다. static class Point{ int y, x; public Point(int yy, int xx){ y=y..

2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net [이분 탐색 or Set 이용] 카테고리가 이분 탐색으로 되어있지만, 이 문제는 Set을 이용해 값이 있는지 여부를 체크하는 것도 가능하다. Set은 값을 포함하는지에 대한 시간 복잡도가 O(1)이므로 굉장히 빠르다. 다른 컬렉션인 List의 contain()은 O(N)이다. 그래서 이분 탐색을 이용한 풀이와 Set을 이용한 풀이를 해보았다. (+추가) 출력의 횟수가 최대 T * 1,000,000번 할 수 있으므로 System.out.println()을 이용한다면 메..

2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net [비트마스킹 + DP] 처음에 문제를 보고 최소 스패닝 트리 문제인 줄 알았다. 그래서 크루스칼 알고리즘을 사용해서 풀 수 있겠다 싶었지만, 최소 스패닝 트리와 완전히 달랐다. 최소 스패닝 트리는 한 정점이 2개 이상의 간선을 가질 수 있지만, 외판원 순회의 경우 한 정점은 2개만 갖을 수 있다. 그리고 반드시 출발점 -> ... -> 출발점이 되어야한다. 이때의 최소값을 구하는 문제였던 것이다. DP와 DFS에 취약한 내 ..

15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net [DFS] 몇 시간을 고민해보아도 풀지 못해 풀이를 찾아 보던 중, 너무 간단하게 푼 풀이가 있어 많은 것을 깨달았다. 나는 아직 DFS 응용을 하기에는 벅차다는 것을.. 문제의 실마리를 찾을 때 조금 더 집중하고 깊이 들여다보는 습관을 길러야겠다. 다음 풀이는 Sleeping Rabbit님의 블로그를 참고하였다. 리프노드의 높이를 구하고, 각 리프노드들의 높이를 모두 더한 합이 짝수이면 실패, 홀수이면 성공 이라는 간단한 명제로 풀이를 진행하셨는데, 내가 너무 ..

2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net [BFS] 전체적으로 스트레스를 유발하는 문제였던 것 같다. 일단 각 정점은 상하좌우로 벽을 갖을 수 있는점, 그래서 비트마스킹을 이용해야한다는 점이... 각 정점은 0~15를 갖을 수 있는데, 0 : 벽이 없음 1 : 서쪽으로 벽 2 : 북쪽으로 벽 4 : 동쪽으로 벽 8 : 남쪽으로 벽 이외의 숫자는 각 벽이 갖는 값을 더한 것이다. (예: 15는 동서남북 모두 벽으로 막힌 곳) #풀이 요약 1. 주어진 지도에 대해 방을 번호로 구분 (예: 1번방, 2..

2417번: 정수 제곱근 정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오. www.acmicpc.net [이진탐색, Binary Search] long타입의 정수 중 제곱했을 때 n보다 큰 값중 가장 작은 값을 찾는 문제. left = 0, right = n으로 세팅하고 이진탐색을 진행하면 쉽게 찾는다. # Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRea..

2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net [DFS] # Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int n; static StringBuilder sb = new StringBuilder(); static boolean isPrime(int x){ if(x == 1) return false; for(int i=2..