구름 개발일기장

https://www.acmicpc.net/problem/23830 🐢 설명 아주 간단한 이분탐색 문제이다. 결국 K를 찾기 위해 가능한 범위를 지정한 후 해당 범위내에서 K값을 지정해보고 이때의 평균값과 선생님이 원하는 S값과의 비교를 통해 범위를 조정해가면 된다. 평균을 높이기 위해서는 결국 K를 올려야 하므로 left = mid + 1, 평균을 낮추기 위해서는 K를 낮추기 위해 right = mid 로 해주면 된다. 가능한 가장 작은 K를 구해달라 하였으므로 lower bound로 구하면 된다. 여기서 놓칠 수 있는 부분은 문제의 첫 문장에 양의 정수 K라고 하였으므로 K의 하한 범위를 0이 아닌 1로 잡아줘야 한다. 🐢코드 public class 제기차기_23830 { static int N; s..

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://programmers.co.kr/learn/courses/30/lessons/60059 🐢 설명 자물쇠와 열쇠가 있고 열쇠를 좌우상하 움직여보고 90도씩 돌려보면서 겹치는 부분만 딱 들어 맞는다면 열린다고 판정하고 그외의 경우는 아니라고 해야하는 문제이다. 이때 자물쇠와 열쇠의 크기가 다를 수 있음에 유의하자. 다음과 같은 그림을 보면서 이해해보자. Lock을 Key가 움직이면서 비교하기 위한 좌표 공간을 먼저 만들어준다. 이 공간은 원점을 기준으로 (key길이 - 1, key길이 - 1) 부터 (lock길이, lock길이)까지의 정사각형의 좌표평면을 갖게 된다. 이후 차례대로 모든 좌표에 대해서 확인을 해준다. 각 좌표에서 키를 둬보고 key 크기만큼 비교를 한다. 이때 좌표명면의 좌표값..

https://programmers.co.kr/learn/courses/30/lessons/1836 참고로 이 문제는 프로그래머스에서 문제를 풀 때 전역변수로 등록된 값들을 main함수에서 초기화를 해줘야 통과가 된다. 🐢 설명 한쌍의 짝으로 존재하는 카드들에 대해서 단 두번의 이동으로 매칭이 될 수 있는지 없는지 확인하고 결과적으로 모든 카드가 매칭이 될 수 있는지 확인하는 문제이다. 하나의 카드의 쌍이 매칭이 되면 해당 카드는 제거 되며 공백이 된다. 모든 카드의 쌍이 제거되면 제거된 카드를 순서대로 문자열로 반환한다. 모든 카드 쌍을 제거할 수 없다면 IMPOSSIBLE을 반환하면 된다. 해결을 위한 로직 지도에 카드 쌍은 무조건 1 대 1로 존재한다고 되어있으므로 모든 카드의 종류를 list에 담..

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