구름 개발일기장

https://programmers.co.kr/learn/courses/30/lessons/64062 🐢 설명 stones 배열의 크기는 1 이상 200,000 이하입니다. stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다. 니니지의 친구들이 길이가 최대 20만인 돌다리를 건너야하고, 해당 돌다리의 내구성은 최대 2억이다. 한명씩 건너게 하고 내구도를 1씩 낮추고 배열을 탐색하면서 0의 개수를 세서 한번에 건널수 있는 최대인 k와 비교할 경우 시간복잡도는 20만개의 돌다리가 전부 2억의 내구도를 가지는 경우 O(20만 * 2억)를 갖게된다. 감히 생각도 할 수 없을 만큼 큰 연산을 해야하므로 이렇게 풀어서는 안된다. Q. 그렇다면 어떻게 접근해야 딱 k개 이상의 돌이 ..

https://programmers.co.kr/learn/courses/30/lessons/17678 🐢 설명 버스를 타기위한 시간을 구하는 문제이다. 가장 늦게까지 늦잠을 자서 회사에 가기 위해 막차를 타야하는데, 동시간대에 도착한 경우 마지막에 줄을 서게 된다. 이때 버스에는 정원이 존재하므로 인원수 체크가 필요하다. 먼저 시간대별로 들어오는 시간순으로 뽑기위해 크루들을 큐에 넣는다. 이후 n번, t분 간격으로 m명이 탈 수 있는 버스가 오는데 여기에 탈 수 있는 경우 태운다. 우리에게 중요한건 "마지막 버스 시간"과 "마지막 버스에 탑승한 마지막 승객의 도착시간"이다. 어짜피 가장 늦게 가는게 목표이므로 이때만 알면 된다. 그렇게 위에서 전부 태워서 위에서 필요한 걸 얻는다. 이때, 마지막 버스에 ..

https://programmers.co.kr/learn/courses/30/lessons/42891 🐢 설명 제각각 양이 다른 음식들이 있을 때 주어진 시간 k까지 1초에 하나씩 먹게 되고 k때 정전이 일어나면 그 이후에 먹어야 되는 음식의 번호를 구하는 문제이다. 생각해보자. 음식의 양이 9 3 5 7 1 씩 있을 때, 5번음식을 먹기 위해서는 5번의 이동이 필요하다. 한바퀴를 돌기 위해서 5번 이동해야 하므로. 그리고 난 후 3번 음식을 다 먹기 위해서는 9 3 5 7 1 -> 8 2 4 6이 되어있고 총 8번의 이동이 필요하다. 이렇게 생각하면 음식의 양이 가장 낮은 순으로 정렬하고, [(현재 음식과 직전 음식의 양 차이) * 현재 있는 음식의 개수]는 현재 가지고 있는 음식의 구성을 깨트리지 않..

https://www.acmicpc.net/problem/18116 🐢 설명 대놓고 Union - Find 인 문제이다. 단 Q가 왔을 때 해당 부품의 로봇이 가지는 모든 부품의 개수를 반환해야 하므로 union시 부품의 개수도 같이 합쳐야 한다. I가 오면 a, b를 하나의 부품을 부모로 가지도록 union한다. 즉 같은 로봇의 부품이 된다. 이때 부모가 되는 부품은 자식이 된 부품의 개수를 더해준다. Q가 오면 해당 부품의 부모를 찾아내고, 해당 부모 값으로 counts배열을 접근해서 부품 개수를 가져온다. paretns[] 배열을 만들어서 모든 부품의 부모 배열을 만든다. counts[] 배열을 만들어서 로봇 별 총 부품의 개수를 담는다. (이때 초기 값은 1) parents[parents[b]] ..

https://www.acmicpc.net/problem/20442 🐢 설명 R로만 이뤄지면 "ㅋㅋ루ㅋㅋ" 이다. "ㅋㅋ루ㅋㅋ" 양옆에 K가 붙으면 "ㅋㅋ루ㅋㅋ"이다. 주어진 문자열의 부분수열 중 ㅋㅋ루ㅋㅋ인 문자열의 최대 길이를 구한다. 부분수열이 가장 핵심적인 내용이다. 부분 수열이므로 원하는 부분은 넣고, 아닌 부분은 빼면 되는 그리디하게 문제를 접근하면 된다. 왼쪽 R이 있고, 중간에 뭐가있든 오른쪽 R이 있다면 해당 문자열은 "ㅋㅋ루ㅋㅋ"가 될 수 있다. 예를들어 R K K R K K R K K K K R K K R K 일 경우 K를 다 빼버리고 R의 개수만 구해서 "ㅋㅋ루ㅋㅋ"인 문자열로 취할 수 있다는 것이다. 하지만 여기서 양옆에 K가 동일한 개수만큼 붙으면 그것 또한 "ㅋㅋ루ㅋㅋ"라고 했..

https://www.acmicpc.net/problem/18500 🐢 설명 왼쪽, 오른쪽에서 던지는 돌에 미네랄이 깨지고, 깨진 미네랄이 바닥과 연결되어 있지 않다면 땅으로 떨어져야 한다. 이때 미네랄은 바닥과 붙어있는 미네랄과 닿을때까지 or 바닥에 닿을 때까지 떨어진다. 로직은 간단하다. 왼쪽 오른쪽 번갈아 가면서 돌을 던진다. 돌을 던져서 방향대로 가다가 해당 높이에서 만나는 첫 미네랄을 부순다. (맨밑) 바닥에서 미네랄을 탐색한다. 탐색 된 미네랄들은 전부 바닥과 연결된 미네랄들이다. 맨위 부터 탐색되지 않은 미네랄을 찾는다. 탐색되지 않은 미네랄은 미네랄이 부셔지면서 공중에 뜬 미네랄이다. 탐색되지 않은 미네랄 덩어리는 하나라고 문제에 나와있으므로 전부 하나의 리스트에 담아준다. 리스트에 있는..

https://www.acmicpc.net/problem/6068 🐢 설명 소요시간과 제한시간이 있는 작업들에 대해서 전부 처리할 수 있는지 알아내는 문제이다. 만약 처리가 가능하다면 가장 늦게 시작하는 시간을, 불가능하다면 -1을 출력하면 된다. 마감시간에 가장 근접하게 작업을 시작해야 가장 늦게 일을 시작할 수 있을 것이므로, 작업의 마감시간이 늦은 시간을 기준으로 정렬시키기 위해 우선순위큐를 사용하였다. 모든 작업중 가장 늦게 시작하는 작업의 시간을 DEADLINE으로 정한 후 (우선순위큐를) 순차 탐색하는데 해당 작업의 마감시간이 DEADLINE보다 더 빨리 시작하는 작업의 경우 : DEADLINE을 (해당 작업의 마감시간 - 해당 작업 소요시간)으로 변경한다. DEADLINE이 더 크거나 같은 ..

https://www.acmicpc.net/problem/9205 🐢 설명 2차원 평면에서 출발지점, 복수의 중간 지점, 목적지가 있을 때 이동사거리 내에 있다면 이동을 하면서 목적지까지 갈 수 있는지 푸는 문제이다. 맥주 20개에 하나당 50미터를 갈 수 있고, 편의점에 들릴때마다 충전할 수 있다고 했지만 간단히 말해서 현재 위치에서 다른 점까지의 DIST가 1000이하면 갈 수 있고 아니면 못간다로 받아들이면 된다. 따라서 출발점, 도착점, 중간 편의점들을 모두 하나의 리스트에 담고, 출발점을 큐에 넣고 방문처리 후 탐색을 한다. 큐에서 점 하나를 뽑고 (처음에는 당연히 출발점이다.) 해당 점에서 방문을 안했고 갈 수 있다면 큐에 넣어준다. 이때 큐는 우선순위 큐로 특정 점에서 목적지 점까지의 거리가..

https://www.acmicpc.net/problem/1826 🐢 설명 일직선의 경로에서 시작점이 0일때 오른쪽의 어딘가에 있는 목적지까지 가야하는 문제이다. 이때 출발지점에서 갈 수 있는 최대 거리는 연료량과 동일하고, 중간에 주유소에 들려서 연료량을 더할 수 있다. 이때의 충전 회수를 최소로 해서 목적지에 도달하도록 하면 된다. 먼저 우선순위 큐 두개를 사용한다. 거리큐 : 갈 수 있는 모든 주유소를 가까운 거리 순으로 담을 큐 연료큐 : 주유소를 담은 큐에서 갈 수 있는 거리내에 있다면 연료량을 많은 순으로 담을 큐 거리큐의 모든 주유소는 가까운 순으로 정렬되어 있으므로 자신이 갈 수 있는 주유소들에 대해서만 루프를 돌면서 연료큐에 모두 넣어준다. 연료큐의 최상단 값을 현재 연료 량에 더해준다...

https://www.acmicpc.net/problem/1781 🐢 설명 제한기간이 있는 문제를 풀어서 최대한 많은 컵라면을 얻어야 되는 문제이다. 먼저 우선순위큐를 사용해서 컵라면을 가장 많이 주는 순서로 정렬하고 해당 문제의 마감날을 통해 해당날에 이미 문제를 풀었으면 그 전날 ~ 1일 까지 확인하면서 문제를 풀수 있는날을 찾아주면된다. 하지만 단순하게 우선순위큐에서 하나씩 뽑고 날짜 확인하고 이미 차있으면 배열을 돌면서 빈날을 확인하게 하면 시간초과가 나게 된다. 총 과제의 개수가 20만개인데 최악의 경우 20만개 * d-day 20만으로 O(N^2)이 된다. Union-Find를 사용하면 이를 O(N)으로 풀수 있다. 어떻게 접근하면 되는지 정리해보자. d-day날이 총 과제의 개수 보다 크거나..

https://www.acmicpc.net/problem/2021 🐢 설명 올리브영 코테에 나온 문제랑 비슷한 문제라서 풀게되었다. 출발 역과 도착 역이 주어지면 몇번 환승해서 도달할 수 있는지 알아내는 문제이다. 처음에는 문제가 잘 이해가 안되었는데 역 번호들이 나열된 하나의 행이 노선이라고 생각하면 된다. 구현 노선별 역을 담을 리스트와 역별로 자신을 지나가는 노선을 담을 리스트 두개를 만들어주었다. 방문체크 또한 해당 노선을 방문했는지 여부와 해당 역을 방문했는지 여부를 체크하기 위해 방문체크용 배열 두개를 만들어 주었다. 최소의 환승 횟수를 출력해야하므로 환승 횟수를 기준으로 갖는 우선순위큐를 사용했다. 주어진 출발역이 하나의 노선이 아니라 여러 노선에 담겨있을 수도 있으므로 라인 별로 해당 역을..

https://www.acmicpc.net/problem/1194 🐢 설명 BFS + 비트마스킹 문제이다. 열쇠를 주운 경우의 수에 따라 탐색 시 방문처리를 다르게 해줘야 하므로 방문체크를 3차원배열로 해줘야한다. 이때 어떤 열쇠를 주웠는지 체크하는 용도로 비트마스킹을 사용하게 된다. 또한 열쇠를 줍고 자물쇠에 열쇠를 비교할 때 비트마스킹을 비교함으로써 자물쇠를 풀수있는지 확인할 수 있다. 참고로 방문 배열을 만들때는 (열쇠의 개수 + 1) 만큼 left shift를 해줘야 한다 만약 열쇠의 개수가 4개라면 최대 지닐 수 있는 열쇠는 1111이 될것이고 이때의 값은 15가 될것이다. 따라서 16크기의 배열이 필요하므로 (1