웹개발 성장기

톱니바퀴문제에서 톱니 개수를 늘리고 정답 구하는 부분만 바꿔주면 되는 문제 15662번: 톱니바퀴 (2) 총 8개의 톱니를 가지고 있는 톱니바퀴 T개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 풀이 예전에 썼던 톱니바퀴에서 톱니 개수를 늘리고 정답 구하는 부분만 바꿔주면 되므로 포스트 링크와 코드만 첨부한다. [백준] 14891. 톱니바퀴 (Java) 시뮬레이션에 간단한 BFS가 추가된 문제 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. melthlee..

시뮬레이션에 간단한 BFS가 추가된 문제 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 풀이 톱니바퀴를 돌릴 때 인덱스 값만 조정해서 실제 톱니바퀴는 돌리지 않는다. 인덱스 값이 변하는 규칙은 톱니바퀴 방향에 -1을 곱한 값을 더해주는 것이다. queue를 사용해서 현재 톱니바퀴 기준 양옆을 조사하면서 뻗어나간다. 톱니바퀴는 이동할 톱니바퀴를 모두 저장 후 마지막에 동시에 돌려야 하므로 별도의 큐로 관리했다. 마지막에 12시 위치의 인덱스 값을 계산해서 답을 구한다. int[][] cog: 톱니바퀴 정보 ..

deque (double-ended queue)를 사용하면 손쉽게 구현 가능한 문제 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 우선 문제를 꼼꼼히 잘 읽어야 한다! X초와 방향전환 정보가 주어지는데 게임 시작 시간으로부터 X초가 끝난 뒤 방향 전환을 한다. 이동시 snake의 tail을 head로 한 칸씩 옮겨가면 된다. 앞, 뒤 insert가 용이한 deque를 사용했다. Java에서의 deque method는 snake에 대조해보면 다음과 같다. 소스코드를 실제로 돌려보니 deque 상에선 snake ..

DFS 백트래킹 문제에 cctv를 설치하는 부분만 신경써주면 쉬운 문제 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 CCTV의 5가지 종류에 대해 조합으로 방향 정보를 구성하고 DFS를 짜주면 끝나는 간단한 문제이다. 방향 정보를 어떻게 나타낼지 고민을 많이 했다.. 우선 처음에 사무실 정보를 입력받을 때 카메라 번호 및 위치, 그리고 해당 카메라의 방향 정보 개수 (d)를 ArrayList에 넣는다. 방향 정보 개수는 아래 그림과 같다. 방문체크는 visited 2차원 배열을 만들어 해당 ..

아기상어 크기 설정시 주의! (무한루프에 빠질 수 있음)16236번: 아기 상어N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가www.acmicpc.net풀이문제 자체는 어렵지 않으나 반례를 잘 생각해야 한다. (문제 푼 시간보다 디버깅 시간이 더 오래걸렸다..) 테스트 케이스는 다 맞는데 2%에서 틀리길래 뭔가 했더니 아기상어 크기가 9보다 커질 수 있다는 사실을 생각 못하고 있었다.. 그리고 사소한 실수지만 만약 y, x가 아니라 x, y로 받았을 경우 위쪽은 y가 아니라 x이다. BABY_SHARK: 현재 아기상어 위치값. N 범위는 최대 20이므로 5..

수직선 상의 실제 위치를 구현하는 것이 아닌 가상 위치를 지정하는 것이 핵심!18513번: 샘터첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤www.acmicpc.net풀이3달전엔 실패했지만 다시 마음을 다잡고 풀어보니 의외로 간단한 문제였다.샘터 위치가 -1억~1억이기 때문에 배열로 수직선을 구현할 생각을 하지 말고 map을 써서 해당 위치에 값이 있는지 없는지만 검사하면 메모리 상에서 효율적인 문제풀이가 가능하다.final int LOWER_BOUND, UPPER_BOUND 변수를 통해 미리 boundary를 지정해줬다.of..