들어가며 코드트리 투어 삼성 SW 역량 테스트 2024년 상반기 오전 2번 문제입니다. 출발점이 되는 기준 도시가 존재하고, 기준 도시로부터 어떤 도시로 가는 여행 상품이 존재할 때, 여행 상품 수익 - 최단 경로 비용 가 최대가 되는 상품을 찾아 판매해 나가는 문제입니다. 각 명령에 대해 최적화를 하지 않으면 시간 초과가 나는 문제였습니다. 문제설명 코드트리 여행사는 코드트리 랜드에서 다양한 여행 상품을 만들어 관리하는 회사입니다. 코드트리 랜드는 n개의 도시와 각 도시 사이를 연결하는 m개의 간선으로 이루어져 있습니다. 각 도시는 0번부터 n - 1번까지의 번호가 붙여져 있고 각 간선은 방향성을 갖지 않습니다 . 또, 두 도시를 연결하는 간선은 여러 개가 존재 할 수 있으며, 자기 자신을 향하는

들어가며 여왕 개미 삼성 SW 역량 테스트 2025년 상반기 오후 2번 문제입니다. 삼성 문제 치곤 간단한 문제였습니다. 문제설명 1차원 수직선으로 표현되는 땅에 여왕 개미와 일 개미들이 개미집을 짓습니다. 좌표는 0 이상 10⁹ 이하의 정수로 한정됩니다. 그리고 다음과 같이 네 개의 명령을 합니다. 마을 건설 : 여왕 개미의 집을 x = 0 위치에 건설. 입력받은 위치들을 이용해 N개의 개미집 건설 개미집 건설 : 새로운 개미집을 p좌표에 건설. 새로운 개미집은 기존 개미집 좌표들보다 큰 값으로 주어짐 개미집 철거 : q번 개미집 하나를 철거. q번 개미집이 이미 철거된 상태거나 아직 지어지지 않은 경우는 주어지지 않음 개미집 정찰 : 정찰을 나갈 개미의 수 r이 주어졌을 때, 모든 개미집의 범위를 커

들어가며 현대모비스와 함께하는 편안한 주행 간만에 찾은 재미있는 문제입니다. 문제설명 승환이는 2차원 평면 위에서 (0, 0) → (a, b)로 이동해야 합니다. 승환이는 자동차를 타고 단위길이만큼 움직일 때마다 1의 스트레스를 받습니다. 승환이는 현대모비스 로고가 그려진 간판과의 거리가 1 이하인 곳에서는 스트레스를 받지 않는다고 합니다. 간판은 N개 존재해요. 스트레스를 최소화할 수 있는 경로를 찾자. (-10⁹ ≤ a, b ≤ 10⁹, 0 ≤ N ≤ 2000, 정답과의 절대/상대 오차는 10⁻⁹ 까지 허용) 해설 1. 스트레스를 받지 않는 구간 최소로 하기 먼저 어떻게 하면 스트레스를 받지 않는 구간을 최소로 할 수 있을까를 고민해야겠죠. 먼저 백준에서 제공한 예제를 보면 다음과 같습니다. --

들어가며 공항 완전탐색으로 생각한 풀이를 어떻게 최적화시킬 수 있는지 묻는 문제입니다. i번째 비행기를 1번부터 gi번째 게이트 중 하나에 도킹해, 비행기를 최대한 많이 도킹한다는 뜻은 gi번째 게이트에 도킹하거나 gi번째 게이트에 최대한 가까운 가능한 게이트에 도킹해야 한다는 아이디어를 떠올려야 합니다. 문제설명 1부터 G까지의 번호를 가진 게이트가 있을 때, P개의 비행기가 순서대로 도착합니다. 이 때, i번째 비행기를 1번부터 gi(1 ≤ gi ≤ G) 번째 게이트 중 하나에 영구적으로 도킹하려고 합니다. 순서대로 도착하다가 더 이상 도킹할 수 없을 때, 공항이 폐쇄됩니다. 최대 몇 대를 도킹시킬 수 있을까요? 해설 앞서 ‘들어가며’에서 설명한 것처럼 비행기를 최대한 많이 도킹하기 위해서는 gi번째

들어가며 이중우선순위큐 힙을 이용한 대표적인 테크닉인 이중우선순위큐 문제입니다. 문제설명 이중 우선순위 큐란 숫자를 삽입하는 insert연산, 그리고 최댓값/최솟값을 제거하거나 리턴하는 delete_max_value/delete_min_value연산을 할 수 있는 자료구조입니다. 최대 1,000,000개의 연산이 주어졌을 때, 모든 연산을 처리한 후 큐가 비어있으면 [0, 0], 비어있지 않으면 [최댓값, 최솟값]을 리턴하는 solution함수를 구현하세요. 해설 이중 우선순위 큐는 다음과 같은 개념을 알고 있으면 풀 수 있습니다. 힙 자료구조 Max-Heap, Min-Heap 두 개의 힙 사용하기 lazy하게 처리하기 힙 자료구조 먼저 힙 자료구조는 최댓값, 최솟값을 빠르게 찾아내기 위해 고안된 완전이

들어가며 Candy Splitting (Large) 솔브드에서 제공하는 랜덤 마라톤에서 나온 문제입니다. XOR 연산에 대한 이해가 있어야 풀 수 있는 문제였습니다. 문제설명 형제 Sean과 Patrick은 부모님으로부터 캔디가 든 가방을 받았습니다. 가방 안에는 값이 다른 여러 개의 캔디가 들어있는데, 이를 공정한 방법으로 나누려고 합니다. Sean이 두 더미로 나누면 Patrick이 둘 중 하나를 골라 가져가는 방식이죠. 불행하게도 Patrick은 너무 어려서 캔디의 값을 올바르게 더하는 방법을 모릅니다. 대신 이진법 덧셈을 거의 할 줄 아는데, 올림을 까먹었습니다. 예를 들어, 12(1100), 5(101)이 있을 때 올바른 덧셈 결과는 17(10001)이지만, Patrick의 방식으로는 9(1001)