들어가며 알고리즘 문제를 풀다보면 boolean집합을 공간적으로 압축하기 위해 비트마스킹을 사용할 때가 종종 있습니다. [True, False, False, True, True, False, True, False]와 같은 배열을 10011010₂와 같이 표현하면 정수 하나로 표현 가능하기 때문이죠. 문제 중에는 정수의 특정 비트가 0인지 1인지 확인 해야 하거나 1의 개수를 세어야 할 경우 도 있습니다. 전자의 경우, 즉 특정 비트의 ON/OFF를 판단해야 하는 문제라면, ((임의의 정수) & (1 << n)) > 0와 같이 간단히 구할 수 있습니다. 오른쪽에서 n번째 비트가 1인 정수를 생성하고 임의의 정수와 AND 비트 연산을 하면, 다음과 같이 해당 비트가 1이라면 2^n, 아니라면 0을 결과로 산

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

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

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

들어가며 순차 탐색 vs 이분 탐색 배열에서 특정 값을 찾는 가장 쉬운 방법은 배열의 맨 앞에서부터 차례대로 찾아나가는 방법입니다. 이는 순차 탐색(Sequential Search) 혹은 선형 탐색(Linear Search) 이라고 하며 최대 n개의 원소들을 확인해야 하므로 O(n)의 시간복잡도를 가집니다. 하지만 배열이 오름 차순이나 내림 차순으로 정렬되어 있음이 보장된다면, 이 정보를 활용해 특정 값을 더 빠르게 찾을 수 있습니다. 예를 들어, 오름 차순으로 정렬된 A = [?, ?, ?, 16, ?, ?, ?] 라는 배열이 존재할 때, 15라는 값이 배열 내 몇 번째에 존재하는지 찾고자 한다고 가정할게요. 이 때, 배열의 3번 인덱스 즉, index = 3을 탐색했을 때, A[3] = 16입니다.

외판원 문제란? 외판원 문제(Traveling Salesman Problem; TSP)는 컴퓨터 과학 및 수학 분야에서 잘 알려진 조합 최적화 문제입니다. 이 문제의 핵심은 주어진 각 도시(노드)를 정확히 한 번만 방문하고 시작 도시로 돌아가는 가능한 최단 경로를 찾는 것 입니다. 이때, A도시에서 B도시로 가는 거리(d)는 가중치가 존재합니다. 문제의 경우에 따라서 시작점으로 돌아가지 않을 수도 있는데, 이 제약 조건이 없다고 해도 계산 복잡도는 변하지 않습니다. 어쨌든 TSP는 대표적인 NP-난해(NP-hard) 문제로 모든 문제에 대해서 다항식 시간에 해결할 수 있는 알려진 알고리즘은 없습니다. 대신 작은 N의 경우(일반적으로 N ≤ 16) 에는 분기한정법(Branch and Bound; B&B