IT recording...

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net [풀이] 낚시왕을 이동시키고, 해당 열에 제일 가까운 상어를 없앤다. 상어들을 이동시킨다. (한번에 이동시켜야 하므로 Map에 바로 상어들을 이동시키지 않고, Copy를 이용하여 거기에 값들을 넣어놓는다.) Copy에 있는 상어들을 Map에 넣는다. 그 후 한 칸에 2마리 이상 있으면 제일 사이즈 큰 애만 남기고 삭제 - 사이즈 제일 큰 상어를 골라내기 위해서 PriorityQ..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net [풀이] 1. 존재하는 미세먼지를 확산시킨다. 한 번에 확산시켜야 하므로 모든 칸을 돌면서 Plus와 Minus를 구하고, 다 돌면 한 번에 갱신한다. 2. 공기청정기 시계방향, 반시계 방향 회전시킨다. 회전시키는게 골때린다. 일단 공기청정기는 무시하고 일반적으로 시계방향으로 회전시키는 것을 생각해보자. 1) 순환하므로 값이 사라지는 것이 존재할 것이다. 그 점을 빨간색칸이라고 해보고, 그 값을..

https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net [풀이] 문제에 적혀있는대로 구현하면 되는 문제였다. * 봄 - 어린애부터 나이만큼 양분 먹고, 양분 못 먹는애는 여름에 죽이기 * 여름 - 봄에 양분 못 먹는애 죽이기 * 가을 - 나이가 5배수인 나무 8방으로 나이 1인 애 생성 * 겨울 - 땅에 양분 추가 A[][] 만큼 ** 주의 - 봄에 양분 못 먹는애를 바로 죽이면 안되고, 봄애 모든 애들 다 체크하고 죽일애들 모아놓고 ..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net [풀이] dfs를 이용하여 몇 개의 뭉텅이로 이루어져있는지를 구하는 것을 응용하는 문제였다. 생각할 부분은 1. 하루 동안에 인구이동이 일어날 때 어느 지역들이 연합을 이루는지, 각 연합의 sum -> AllArr 과 sumArr 에 각각의 값들을 담았다. 2. 총 몇일이 지날지 -> 하루 동안 인구이동이 일어나는지 볼 때 인구의 차이가 L break) 나머지는 코드 주석으로 확인하..

https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr [풀이] 마지막 예제에서 xababcdcdababcdcd 의 경우 맨 앞에서부터 잘라야 한다는 것을 보지 않아서 삽질했다. x다음부터는 비교를 할 수가 없고, 항상 맨 처음부터 비교해야 함 1. 1개 단위로 자를 때, 2개 단위로 자를 때, ... 를 모두 실행한 후 압축한 문자열의 길이를 비교한다. 2. 몇 개 단위까지 자를 수 있을까? => 문자열의 ..

https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net [풀이] 규칙을 찾는 것이 힘들어 키보드 잡기까지 한 시간이 넘게 걸린 문제.. 규칙은 이전 세대의 (끝점 -> 시작점) 방향을 차례로 시계방향으로 회전한 후 그것을 새로운 끝점에 더하는 것이었다. (쓰고보니까 문제의 설명이랑 같은데 왜이렇게 이해하기 어려웠는지.. 사실 아직도 어렵다) (그림에서 1을 시계방향 회전에서 끝점에 더하고, 2를 시계방향 회전해서 새로운 끝점..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net [풀이] 사방으로 이동하면서 연결된 집들의 갯수를 구하는 문제 1. 집들을 모두 ArrayList에 넣어두고, 방문하지 않은 집을 모두 방문하며 dfs를 들어간 횟수를 구한다. (answer) 2. 하나의 집단 탐색이 끝났을 때 총 몇 번 지나왔는지 세기 위해서 전역변수로 count를 두고 새끼dfs를 들어갈 때마다 증가시킨다. 그리고 하나의 집단 탐색이 끝나면 queue에 add (오름차순으로 정..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net [풀이] 문제를 보고 키보드를 잡기까지 상당한 시간이 걸렸다. 어떻게 풀이 방법을 생각해야할지를 모르겠었기 때문이다 처음에는 다음과 같이 생각했다. 홀수개의 사다리 선이 있으면 i -> i 제자리로 돌아올 수 없으므로 홀수인 애들한테 가서 dfs를 돌리면 되지 않을까? 그래서 짝수인 경우는 사다리를 놓지 않고, 홀수인 경우에만 하나씩 놓아서 문제를 해결하려 해보았다. 그런데 테케는 다 맞았지만 ..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net [풀이] 백트래킹에 조금의 응용이 더 들어간 문제였다. 1. 일단 조합을 구해야 한다는 점에서 처음 백트래킹을 사용해야겠구나 생각했다. 2. 근데 생각해보니까, 총 6명일 때 [1,2,3]조합을 구한다면 [4,5,6]은 자동으로 상대 팀이 된다. 그럼 dfs를 절반만 돌릴 수 있다는거 아닌가? 라는 생각에 일단 6C3값(factorial이라고 써놓음)을 구해서 그 이상이면 컷하게 했다. 3. 그리고 팀 구성의 경우 원..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net [풀이] 1. CCTV의 위치들을 저장한다. (얘네 차례로 돌리면서 dfs끝까지 갈거임) 2. CCTV종류마다 어느 방향으로 가야하는지 switch문으로 분류해줌 (parameterXXX 호출) - 1이면 상, 하, 좌, 우 - 2면 상하, 좌우 - 3이면 상우, 우하, 하좌, 좌상 - 4면 좌상우, 상우하, 우하좌, 하좌상 - 5면 상하좌우 3. 근데 범위를 벗어나거나, 벽을 만날때까..