2025년 3월 1일 1. 택배 기사 민서 (S2) 문제 : 택배 기사 민서 알고리즘 : 수학, 구현 성공 여부 : 실패 풀이 : 보류 복기 : 실버 2 문제라고 얕봤는데, 의외의 복병이었다. 좌표의 범위가 -10억 ~ 10억이기 때문에 좌표에 대한 각각의 거리를 전부 저장할 수 없다. 따라서 좌표에 따른 거리의 수학적인 규칙을 찾아내야 하는 문제였다. 여기서 수학적인 테크닉이 필요했다. 등비수열의 합 까먹은 거 다시 한번 보기 2025년 3월 4일 1. 가장 긴 증가하는 부분 수열 2 (G2) 문제 : 가장 긴 증가하는 부분 수열 2 알고리즘 : 이분 탐색, LIS 성공 여부 : 성공 (5분) 풀이 : 가장 긴 증가하는 부분 수열(LIS) 복기 : 배열의 범위가 100만이라서 O(n^2) 풀이는 불가

2025년 2월 19일 1. 分 (Minutes) (B5) 문제 : 分 (Minutes) 알고리즘 : 사칙연산 성공 여부 : 성공 (1분) 풀이 : 패스 복기 : 일본어 문제라 당황했지만, 시간 H와 분 M이 주어졌을 때 총 몇 분인지 계산하는 간단한 문제 2. Candy Splitting (Large) 문제 : Candy Splitting (Large) 알고리즘 : 그리디, 비트마스킹 성공 여부 : 실패 풀이 : Candy Splitting (Large) 복기 : Sean과 Patrick이 캔디를 나누는 문제. Patrick은 이진법 연산을 잘하지만 두 수를 더했을 때 remainder를 다음 비트로 옮기는 걸 까먹는다. 이를 이용해 캔디를 두 부분으로 나눴을 때 Patrick이 느끼기에 같은 값이라

들어가며 배낭 문제(Knapsack Problem)는 조합 최적화 문제의 기본적인 문제 유형으로 동적 계획법(DP)을 이용해 풀 수 있습니다. 코딩 테스트에서 배낭 문제 혹은 냅색이라고 하면 바로 이 유형이구나 생각하면 됩니다. 배낭 문제의 핵심은 각각 가중치(Weight)와 가치(Value)를 가진 집합이 주어졌을 때, 총 가중치의 한계 내에서 유지하면서 총 가치가 가장 커질 수 있도록 어떤 원소를 포함시킬 것인지 결정하는 것 입니다. 쉽게 말해 10kg 용량 배낭에 [5kg, 5만원, 신발], [6kg, 4만원, 패딩], [4kg, 3만원, 속옷]이 있을 때 어떤 것들을 가져가야 용량에 넘치지 않으면서 최대 가치를 챙길 수 있는지 찾는 것입니다. 위 예시에서는 신발과 속옷을 챙기는 것이 8만원으로

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

들어가며 알고리즘 문제를 풀다보면 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을 결과로 산

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

들어가며 공항 완전탐색으로 생각한 풀이를 어떻게 최적화시킬 수 있는지 묻는 문제입니다. 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)