개발하는 고라니

16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net [BFS] 사람이 먼저 BFS 탐색을 하고, 그 다음 벽이 움직이는 벽 BFS가 실행된다.이 문제에서, 벽은 8턴 이후에는 맵에 없으므로(8줄이기 때문에 8턴 후 모든 벽은 사라진다) 9턴 째 까지 왔다면 탐색할 필요 없이 탈출에 성공한 것이다. 그래서 visit배열을 3차원 배열로 선언해 몇 번째 턴일 때 방문한 것인지 체크하였다. 플레이어는 상하좌우, 대각선, 제자리 이렇게 9곳을 탐색할 수 있다. 그리고 가장중요한 것은 다음과 같은 상황일 때의 처..

13701번: 중복 제거 문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 225 = 33554432, i=1,2,…,N. 입력의 개수 N은 1 www.acmicpc.net [Collection 사용] 사실 이 문제의 알고리즘 카테고리는 '비트마스킹'이지만,,, 비트마스킹으로 어떻게 풀어야할지 몰라 3가지 방법으로 풀었다. 1) Set 2) boolean[] 3) Map 방법은 간단하다. 각 자료구조에 특정 값이 없다면 추가하고, 특정 값이 있다면 스킵한다. # Code 1) Set public static void main(String[] args) thr..

1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net [소수 판정] 1부터 n까지 반복문을 돌며 소수인 것을 prime 배열에 저장했다. 그러면 prime에는 n이하의 소수만 저장되게 된다. 이제 이중 루프를 이용해서 prime을 돌며 연속 합이 n보다 같은 경우를 찾아 count를 증가시킨다. # Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static boolean isPrime(int x){ if(x == 1) return false; for(int i=2; i

1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net [소수 판별] 소수를 판별하는 간단한 알고리즘은 특정 숫자 x에 대해 2 ~ x의 제곱근까지 나머지연산을 해보며 결과값이 0이면 소수가 아니라고 판별한다. 자바의 경우 출력이 많을 수 있으므로 System.out.println()을 이용한다면 메모리와 시간을 많이 잡아먹는다. 따라서 StringBuilder를 이용했다. 혹시 메모제이션으로 할 수도 있지 않을까 했지만 굳이 필요는 없었다. import java.io.BufferedReader; import java.io.IOException; ..

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에 취약한 내 ..