구름 개발일기장

https://www.acmicpc.net/problem/3114 🐢 설명 누적합 문제이다. 사과 나라는 트랙터가 지나는 아래쪽의 사과를 얻고 바나나 나라는 트랙터가 지나는 위쪽의 바나나를 얻는다. 이때 트랙터가 지나는 길의 과일은 아무도 얻지 못한다. 따라서 트랙터가 지나는 길을 기준으로 사과나라에서 얻을 수 있는 사과 갯수와 바나나 나라에서 얻을 수 있는 바나나 갯수를 별도로 확인해주는 것이 필요하다. 예제에서 주어진 2차원 맵을 생각해보자 현재 지도에는 바나나와 사과가 존재하고 트랙터가 어디로 갔냐에 따라 얻을수 있는 사과와 바나나의 개수는 달라진다. 이를 그림으로 나타내보면 아래와 같다. 트랙터가 (0, 0)에 위치한다면 사과 나라는 0열에서 0행을 제외한 아래 1~3행 중 사과 3 + 2개를 얻..

https://www.acmicpc.net/problem/10800 🐢 설명 공의 개수 : 최대 20만개 공의 색 : 최대 20만개 공의 크기 : 최대 2000 위 제한사항을 유념하도록하자. 색이 20만개 이므로 색별 크기 배열을 만들경우 20만 * 2000으로 4억개의 int가 만들어진다. 이러면 당연히 메모리 초과가 발생하니 1차원배열에 O(N^2) 미만으로 풀 수 있어야한다. 먼저 하나의 볼에 대해서 자신보다 작고, 색이 다른 볼만 이길 수 있다했다. 따라서 먼저 모든 볼을 크기순으로 정렬을하고, 각 볼에 대해서 (현 볼보다 가벼운 모든 볼의 무게 합) - (현재 볼 색깔의 무게 합) 을 하면 현재 볼이 이긴 모든 볼의 무게를 구할 수 있다. 볼을 뽑고 현재 볼보다 가벼우면 계속 더하는데, 이때 색..

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

https://www.acmicpc.net/problem/8972 🐢 설명 내가 조종하는 아두이노 기기 [I]와 미친 아두이노 [R] 들이 만나지 않고 주어진 명령을 수행하는지 확인하는 문제이다. 또한, 주어진 8방향은 순서가 정해져있으므로 그에 맞춰서 dir 배열을 만들어야 한다. 나의 아두이노가 실패하는 경우 내가 이동할 때 미친 아두이노를 만난 경우 미친 아두이노가 나에게 가깝게 이동하는데 만난 경우 내가 성공하는 경우 주어진 명령 방향을 온전히 수행하는 경우 주어진 명령이 맵을 벗어나는 경우가 없어서 맘편히 돌리면 되어서 좀 편했다. 일단 모든 미친 아두이노를 리스트에 담고 지도에 -1로 표시해주었다. 이 후 나의 아두이노가 주어진 명령 하나를 수행하고, 모든 미친 아두이노들에 대해서 8방향 중 ..