본문 바로가기
반응형

분류 전체보기

 (644)
백준 : 17142 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 www.acmicpc.net DFS로 순서쌍 Combi 만들고 BFS로 시간탐색 하면된다. 바이러스가 못옮기는 경우에는 max값을 반환하고 DFS마다 min값을..
백준 : 17143 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하 www.acmicpc.net 시뮬레이션 문제 이문제는 2차원 ArrayList를 설정해서 물고기가 겹친다는것을 표현해주면 푸는데 문제가없다. 문제는 속도와 방향을주..
JAVA : Uppered Bounded 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public static int UpperBounded(int left, int right, int r, ArrayList list) { if (left == right) { if (left == list.size() - 1) { if (list.get(left).r >= r) return -1; } return left; } int mid = (left + right) / 2; if (list.get(mid).r
비트 연산을 이용해 2^n 이 맞는지 판별하기 문제를 풀다가 2^n이 맞는지 판별하기 위해서 while(){ if(N==2) true N % 2 ==1 false; N /=2; } 로직을 구현한적이있다. 이러한 판별법은 2가 될때가지 구해서 판별한다. 하지만 비트연산자를 보면 1 -> 1 2 -> 10 4 -> 100 8 -> 1000 보면 첫재 자리수 빼고는 전부 0인걸 알 수 있다. 결론부터 말하자면 밑에가 참이면 2의 제곱수이다. if( N == (N&-N)) 예를들어 8을 예시로 들겠다. 8을 비트로 만들면 1000 이된다. -N = 2의보수 와같다. 과 같다. 따라서 1000 이된다. 앞전 부호비트 생략 1000 & 1000 은 1000 즉 N과 같게되서 위의 조건문을 만족한다. 만약 3일경우 11 은 01 이된다. 이처럼 N&-N 연산은 ..
백준 : 17822 JAVA https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j www.acmicpc.net 글에 대한 설명이 턱없이 부족하다. 문제를 풀면서 테스트 케이스를 돌려보면서 확인해야한다. 1. 원판은 시작할때는 인접한 것을 c..
백준 : 16236 JAVA https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크 www.acmicpc.net 부루드포스 + 최단거리(BFS)문제 N*N이라는 제한된 공간에 아기상어가 먹을 수 있는 물고기가 없을 때까지 몇칸을 이동하는지 문제..
백준 : 5373* https://www.acmicpc.net/problem/5373 5373번: 큐빙 문제 루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다. 큐브는 각 면을 양방향으로 90도 만큼 돌릴 수 있도록 만들어져 있다. 회전이 마친 이후에는, 다른 면을 돌릴 수 있다. 이렇게 큐브의 서로 다른 면을 돌리다 보면, 색을 섞을 수 있다. 이 문제에서는 루빅스 큐브가 모두 풀린 상태에서 시작한다. 윗 면은 흰색, 아랫 면은 노란 www.acmicpc.net 큐빙 maping을 이용해서 다시풀어보기
JAVA : LIS nlongN 기법 lower_bound 기법 Lower_bound 기법이란 기존 N^2 방식에서 배열 N을 탐색하면서 새로운 벡터 배열에 가장 긴 수를 뽑을 수 있게끔 수들을 저장하는 기법이다. 10 20 40 25 20 50 30 70 85 라는 배열이 있다. 처음에 벡터에 10을 넣는다. 10 10 20 10 20 40 10 20 25 10 20 25 10 20 25 50 10 20 25 30 10 20 25 30 70 10 20 25 30 70 85 N까지 탐색하면서 벡터에 들어가는순서를 생각하면 이렇게 된다. 벡터에 가장 끝에 담긴수보다 현재 수가 더크면 길이를 증가시키고 추가하면 된다. 같은 경우는 버리면 된다. 작은 경우는 이진 탐색을 통해서 현재 이값이 지금까지 쌓아온 벡터중에 어디에 들어가야하는가 생각한다...
반응형

티스토리툴바