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

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

들어가며 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence; LIS)은 DP로 풀 수 있는 유명한 문제 유형 중 하나입니다. 문제의 핵심은 주어진 시퀀스에서 오름차순으로 정렬된 가능한 가장 긴 부분 수열을 찾는 것 입니다. 참고로 답이 되는 부분 수열은 꼭 하나가 아니라 여러 개가 될 수도 있습니다. 이 문제를 푸는 방법은 크게 두 가지가 알려져 있습니다. DP로만 풀기 와 DP + 이분탐색으로 풀기 입니다. 각각 O(n²)와 O(n log(n))의 시간복잡도를 가집니다. n이 작으면 전자의 방법으로도 충분할 수 있지만 n이 더 커지면 힘들겠죠. 풀어볼 문제는 가장 긴 증가하는 부분 수열5 입니다. 문제는 아주 짧고 명확합니다. 예를 들어 수열 A가 A = {10,