구름 개발일기장

https://www.acmicpc.net/problem/23829 🐢 설명 이분탐색과 누적합을 이용해서 풀 수 있는 문제였다. 간단하지만 lower_bound로 구한 위치에서의 나무가 자신의 위치와의 차이 별로 따로 처리해야 하는 부분이 좀 어려웠었다. 주어진 나무들이 있고 자신의 위치가 주어진다. 이때 자신의 위치와 나무의 위치를 비교해서 모든 거리의 합을 각 위치별로 출력하면 되는 문제이다. 이때 모든 나무들을 먼저 정렬하고, 누적합을 만들어 준다. 정렬된 나무들에 대해서 자신보다 크거나 같은 최초의 나무 위치를 구하기 위해 lowerBound()를 이용해 구한다. 이 작업은 logN 이므로 10만개의 나무에 대해 빠른 비교를 할 수 있다. 이렇게 구한 위치의 나무가 자신의 위치와 차이가 어떻냐에 ..

https://www.acmicpc.net/problem/19845 🐢 설명 넴모넴모들이 왼쪽아래에 모여있다는 조건이 있으므로 쉽게 풀 수 있다. 우리가 구해야할 값은 레이저의 설치 좌표가 주어졌을 때 오른쪽에서 지울수 있는 넴모의 개수와 자신의 위 행에서 지울 수 있는 넴모의 개수의 합을 구하기만 하면 된다. 오른쪽에서 지울 수 있는 넴모 개수 구하기 이때 오른쪽은 비교적 쉽게 구할 수 있는데 각 층마다 알려준 넴모의 개수가 있으므로 이를 이용해서 계산하면 된다. (y, x) 레이저 설치 시 지울 오른쪽 넴모의 개수 = 층에 존재하는 넴모 개수 - x (레이저 열 위치) + 1 (자기위치) 를 통해 구할 수 있다. floorInfo[row - 1] - col + 1 만약 음수라면 0으로 치환해주는걸 잊..

https://www.acmicpc.net/problem/1477 🐢 설명 처음에는 휴게소를 세울 때 기존 휴게소 사이에 (중간)에 세우면 되는게 아닌가 생각했다. 하지만 이부분은 거리가 300일 때 150으로 나눌순 있지만 100, 100, 100으로 나누는 방법은 제공하지 못한다.  새로운 접근 방법은 이분탐색이다. 휴게소간 사이 거리 S를 정하고 S일 때 휴게소를 몇개 세울 수 있나 확인한다. 이때 세운 휴게소의 수가 세워야 하는 휴게소 M개보다 크다면 -> 간격이 너무 좁으므로 간격을 늘려서 휴게소를 덜 짓는다. 세워야 하는 휴게소 M개보다 작거나 같다면 -> 간격을 더 줄일 수 있다는 의미이므로 간격을 줄여서 휴게소를 더 짓는다. 위와 같이 이분탐색을 통해 적절한 휴게소 사이 거리를 탐색하고,..

https://www.acmicpc.net/problem/13397 🐢 설명 처음에는 좀 막막하게 다가온 문제이다. N개의 수가 주어졌을 때 어느 구간으로 나눴을 때 구간 내 최대값의 차이가 최소인 수를 구하는 문제이다. 구간의 크기를 동적으로 바꿔줘야 하는 문제인가 했지만 이분탐색으로 풀 수 있는 문제였다. 그럼 뭘 이분탐색할지가 중요한데 바로 구간 내 값의 차이를 이분탐색하면 된다. 주어진 수는 1 ~ 10000의 수가 주어진다 하였으므로 해당 수를 이분탐색해서 mid값으로 분할을 할 수 있는지 본다. 즉 정리하면 1. 0 ~ 10001 범위에서 mid를 잡는다. 해당 mid는 구간 내 차이의 값을 의미한다. 2. 해당 mid값으로 구간을 나눠보고 전부 나눴을 때 구간의 개수를 반환받는다. 3 -1...

https://www.acmicpc.net/problem/17490 🐢 설명 원형의 호수를 둘러싼 건물들에 대해 최소 스패닝 트리를 만들어야 한다. 이때 중요한 점은 건물군(동일한 부모를 갖는 건물들)이 하나라면, 즉 건물 사이를 막는 공사가 없거나 하나라면, 아무리 다리를 만드는 비용이 비싸도 모든 다리를 만들 필요없이 모든건물들을 갈 수 있으므로 무조건 YES 이다. 위 예외 사항을 제외하면 일반적인 유니온 파인드로 문제를 풀 수 있다. 1. 각 건물들의 부모를 자신의 번호로 지정하고, 건물 사이의 공사 여부를 체크해준다. 2. 각 건물들을 돌면서 같은 건물군인지 확인하고 & 사이에 공사구간이 없다면 같은 건물군으로 묶어준다. 이때 마지막 건물은 첫번째 건물까지 확인하게 해준다. 3. 건물번호와 부모..

https://www.acmicpc.net/problem/12764 🐢 설명 싸지방 컴퓨터를 사용하는 순서가 주어졌을 때 최소 몇개의 컴퓨터가 있어야 대기없이 컴퓨터를 사용할 수 있는지 구하는 문제이다. 이때 사용가능한 컴퓨터 중에서 번호가 가장 빠른 컴퓨터 사용한다는 점이 중요하다. 1. 모든 컴퓨터의 이용시간을 시작 시간을 기준으로 user_우선순위큐에 넣는다. 2. 사용하는 컴퓨터를 담는 usingCom_우선순위큐에는 끝나는 시간을 기준으로 담는다. 2-1. 만약 usingCom이 없다면 컴퓨터 자리를 새로 만들어서 추가한다. 2-2. 만약 usingCom이 있다면 자신의 시작 시간과 컴퓨터의 사용가능한 시간대를 확인하고 가능한 컴퓨터의 자리는 좌석순서_우선순위큐에 담는다. 2-2-1. 좌석순서_우..

https://www.acmicpc.net/problem/2174 🐢 설명 로봇들이 2차원 공간에 존재하고 주어진 명령에 따라 움직인다. 이때 주의할 점은 좌표평면의 원점이 좌측 하단이라서 일반적인 2차원 배열의 인덱스와 다르다는 점이다. 하지만 굳이 신경쓰지 않고 그대로 사용해도 문제는 없는데 다만 그렇게 하려면 움직이라는 명령에서 방향은 변경을 해줘야 한다. 동, 서 쪽은 위아래가 반대여도 그대로이니 상관이없고 북쪽은 남쪽으로 / 남쪽은 북쪽으로 변경해주면 좌표값은 그대로 사용해도 무방하다. 로봇이 로봇이 부딫힌 경우에는 해당 로봇의 번호도 알려줘야 하므로 맵에 각 로봇의 번호를 적어놨고 이동할 때 같이 수정하도록 했다. 로봇들은 배열에 담아 놓은 후 주어진 로봇 번호로 접근하여 로봇을 움직이게 했다..

https://www.acmicpc.net/problem/5427 🐢 설명 벽이 있는 방에서 불이나 탈출해야하는 문제이다. 이때 불은 빈공간으로만 퍼진다는 특징이 있고, 사람도 빈공간으로만 다닐 수 있다. 불이 났거나 날 공간으로는 이동할 수 없다는 조건이 있다. 방 모습이다. 이 경우 5회의 이동끝에 탈출한다. ###.### #*#.#*# #.....# #.....# #..@..# ####### 먼저 불이 난 좌표를 불 큐에 넣어주고 내가 존재하는 위치를 저장해 뒀다. 이후 탈출자 먼저 BFS탐색으로 이동을 하고 불에 대해 BFS 탐색 후 이동하도록 했다. 이때 큐에 담은 불이나 탈줄자의 개수만큼만 탐색을하고 번갈아 가면서 하도록 했으며 사람이 먼저 이동하고 불이 이동하도록 했다. 만약 사람이 이동한 ..

https://www.acmicpc.net/problem/3190 🐢 설명 2차원 맵을 뱀이 돌아다닌다. 이때 뱀이 자신의 몸에 닿거나 or 벽을 넘어가면 종료된다. 맵에 있는 사과를 먹으면 몸의 길이가 1 늘어난다. 그렇지 않으면 앞으로 계속 간다. 특정 초에 이동을 완료하고 방향만 바꾸는 명령이 주어진다. 사과를 안먹은 경우에는 이동 후 꼬리를 땡겨야 하는데 이를 위해서 뱀의 이동 내역을 담기 위한 Deque을 사용했다. 이동할 때 다음 위치의 유효성 검사를 하고 유효한 경우 사과 여부에 따라 구분하여 처리한다. 사과가 없다면 덱의 마지막을 뽑아서 제거하고, 있다면 다음 좌표를 덱의 앞에 넣어준다. 이동이 끝나면 명령의 시간과 현재 시간을 비교해서 같다면 왼쪽 / 오른쪽으로 방향만 바꿔준다. 조심할 ..

https://www.acmicpc.net/problem/20058 🐢 설명 하나의 보드에서 부분사각형으로 회전을 하고 모든 회전이 끝나고 나면 각 좌표들에 대해서 인접 노드의 얼음 개수가 3미만인 경우를 찾고, 해당 좌표의 얼음을 1 감소시킨다. 이 후 모든 얼음의 개수를 세고, 가장 큰 얼음덩어리의 면적을 구한다. 이때 각 작은 사각형마다 회전을 하기위해 작은사각형의 크기만큼 x좌표와 y좌표를 이동시켜서 회전을 했다. 🐢코드 //얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다 public class 마법사상어와파이어스톰_20058 { static int N, Q, L; static int[] dy = {-1, 1, 0, 0}; static int[] dx = {0,..

https://www.acmicpc.net/problem/20057 🐢 설명 모래가 정사각형 공간에 존재한다. 토네이도는 반시계 방향으로 정가운데에서 불기 시작한다. 이때 방향은 , ㅗ 순서이다. 바람이 불면 해당 방향 바로 앞 좌표에 존재하는 모래가 이동한다. (3, 3)에서 바람이 왼쪽으로 불면, (3, 2)의 모래가 이동한다. 모래가 이동하면 문제에서 나오는데로 모래가 먼저 다 퍼진다. 이때 0이하의 모래는 무시한다. 기존 모래 - 실제로 퍼진 모래만이 a부분으로 이동한다. 이때 기존 모래는 0이 된다. 이동거리가 m일 때 총 2회씩 이동하고 m의 길이가 1 증가한다. 또한 m이 총 공간의 길이 - 1에 도달할 경우 3회 이동을 하고 종료된다. 토네이도가 왼쪽으로 이동할 때 모래가 이동하는 경우와 ..

https://www.acmicpc.net/problem/20665 🐢 설명 09:00시부터 21:00시 까지의 독서실 시간을 채워서 원하는 자리에 앉을 수 있는 총 시간을 구하면 된다. 먼저 시간, 분, 총 좌석으로 이뤄진 3차원 배열을 만들고 손님이 올 때 해당 손님의 시작 시간부터 종료 시간을 체크한다. 이때 시작시간을 가지고 앉을 수 있는 자리를 찾는다. 자리는 1번을 가장 선호하고, 이후 부턴 다른 사람과의 거리가 가장 멀고 그중에서 앞자리수인 자리에 앉게 하면 된다. 따라서 1~N개의 자리번호에 대해서 자신의 자리외에 다른 자리의 손님들과의 거리중 가장 짧은 값을 구하고, 해당 각 좌석 번호별 손님까지의 최소 길이의 최대값을 갖는 자리 번호를 반환하도록 한다. 예들들어 1~5번 좌석에 대해서 ..