![article thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FViqQo%2Fbtsro8MeZ06%2FQkg9nnikYTIFpFPtB4Vns0%2Fimg.png)
Level 2. 택배 배달과 수거하기 이동 경로를 최소화하기 위해서는 가장 먼 곳부터 배달과 수거를 마쳐야 한다. 배달과 수거를 각각 진행하면서 가장 먼 집을 유지하고, 가장 먼 집까지의 거리를 더하는 방식으로 진행한다. 카카오 문제 치고는 파싱이나 다양한 개념들이 섞여있진 않은데, 그렇다고 구현이 마냥 쉽지도 않았다. #include #include #include using namespace std; long long solution(int cap, int n, vector deliveries, vector pickups) { long long answer = 0; int ed = n - (find_if(deliveries.rbegin(), deliveries.rend(), [](int num) { ..
![article thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F01Fa0%2FbtsrqwZ8Fk1%2FTscvubdAp1Ey97CqUw1k6k%2Fimg.png)
Level 2. 숫자 블록 10,000,000 이하의 가장 큰 약수를 찾는 문제다. 수의 제곱근까지만 순회하면 되고, 약수와 수/약수를 최댓값을 구하는 데 사용하면 된다. #include #include #include #include using namespace std; int max_divisor(int num) { if (num
![article thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FrWKWr%2Fbtsq1Je2NfS%2FbB5xjz1l2NB4gSwddShpq1%2Fimg.png)
Level 2. 요격 시스템 Level 3. 단속카메라와 정확히 같은 문제다. 새로운 구간으로 넘어갈지 검사할 때 =을 붙이는 것만 다르다. 구간이 나온다면 항상 시작점을 기준으로 정렬해 생각하면 된다. 두 구간이 겹치는 경우가 대부분이지만, 구간을 완전히 포함하는 경우도 있으므로 끝점을 최솟값으로 갱신해주어야 한다. #include #include #include #include using namespace std; struct Section { int start; int end; friend bool operator B.start; } }; int solution(vector targets) { i..
![article thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbQNHgC%2FbtsqLSpoPDv%2FkK2y8fkwbdDIhOwkwVZB0K%2Fimg.png)
Level 2. 순위 검색 레벨 2가 맞나 싶을 정도로 파싱, 해시, 이진 탐색 그리고 효율성까지 정말 다양한 것들을 잘 알고 활용해야 하는 카카오 문제다. 꽤 어려웠지만 나름 성장했다고 느낀다. 우선 첫 번째 시도에서 시간 초과가 발생했다. 파싱은 정규 표현식을 이용해 and를 없애고 istringstream을 이용했다. 이후 언어부터 점수까지 조건에 맞는 인덱스를 구하는 방식으로 해결했다. [0, 1, 2, 3, 4, 5, 6, 7] [0, 2, 3, 5, 7] [0, 5, 7] [0, 5] [5] // 이 풀이는 시간 초과가 발생한다. #include #include #include #include #include #include using namespace std; enum class LANG {..
![article thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F2SWjf%2FbtsqJsDuVl3%2FdpKKVUF16Ee4K4nKYqkQ70%2Fimg.png)
Level 2. 디펜스 게임 정답이 몇 라운드가 되던지, 그 중 무적권을 사용한 라운드는 가장 몬스터가 많이 나오는 n개여야 하므로 우선순위 큐를 사용해야 할 것 같았다. 이번 문제는 솔직히 당연히 틀릴 줄 알고 제출했는데 정답 처리돼서 당황스러웠다. 무적권을 사용할 수 있으면 일단 사용하고 최소힙에 넣는다. 이후 무적권이 없을 때부터는 최소힙의 최솟값과 현재 라운드의 몬스터 수를 비교해, 이전에 썼던 것보다 현재 라운드에 쓰는 게 이득이면 이전 라운드의 몬스터 수를 n에서 빼고 현재 라운드에 무적권을 사용한다. 나중에 현재 라운드에 사용한 것보다 이득인 상황이 올 수 있으므로, 현재 라운드의 몬스터 수도 최소힙에 넣어 주어야 한다. 현재 라운드보다 이전에 썼던 것이 이득이면, 현재 라운드의 몬스터 수를..
![article thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FAdIxL%2FbtsqBv1Qe4z%2FRFvk8HBEt3rcBooSeVH5Sk%2Fimg.png)
Level 3. 단속카메라 여러 개의 구간이 주어진 문제라면, 일단 시작점을 기준으로 정렬할 생각부터 해야 한다. 이 문제에서는 최소힙을 구성하기 위해 Section의 < 연산자를 반대로 오버로딩했다. set, map 등과 달리 우선순위 큐는 최대힙이 기본이기 때문이다. 별도 관리하는 끝점과 각 구간의 시작점을 비교하므로, 끝점은 정렬하지 않아도 된다. 현재 단속 카메라를 배치할 수 있는 끝점을 end 변수로 관리하고, end보다 큰 시작점이 나오면 새로운 카메라를 배치해야 한다. end보다 작거나 같은 시작점이 나오면 현재 카메라를 공유할 수 있다는 뜻인데, 이 때도 가능한 작은 위치에 카메라를 배치해 더 많은 카메라를 공유할 수 있도록 갱신해야 한다. #include #include #include ..