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

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

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

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

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이 느끼기에 같은 값이라

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

2025년 4월 1일 1. 연구소 (S4) 문제 : 연구소 알고리즘 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, BFS 성공 여부 : 성공(20분) 풀이 : 보류 복기 : 이차원 배열에 벽이 세워져있고, 바이러스가 위치해 있고 세 개의 벽을 추가로 세웠을 때 바이러스로부터 안전한 지역의 크기가 가장 큰 것을 찾는 문제. 세 개의 벽을 무조건 세워야 하므로 dfs로 모든 벽을 세울 수 있는 경우의 수로 place한 다음에 바이러스를 bfs로 퍼뜨려서 정답을 찾았다. dfs 대신 아예 입력받을 때 벽을 세울 수 있는 위치만 저장해 뒀다가 조합으로 푸는 게 더 빠를 것 같긴 하다 2025년 4월 2일 1. 불켜기 (G2) 문제 : 불켜기 알고리즘 : 그래프 이론, 그래프 탐색, BFS 성공 여

2025년 5월 1일 1. 꼬인 전깃줄 (G2) 문제 : 꼬인 전깃줄 알고리즘 : 이분 탐색, LIS 성공 여부 : 성공(5분) 풀이 : 패스 복기 : 대표적인 LIS 응용 문제 2025년 5월 4일 1. 트리 (G2) 문제 : 트리 알고리즘 : 트리, 분할 정복, 재귀 성공 여부 : 성공 (30분) 풀이 : 패스 복기 : 전위 순회와 중위 순회의 결과를 통해서 바이너리 트리를 만들 수 있는지 묻는 문제. 중위 순회는 node의 왼쪽을 먼저 확인하고 난 뒤, 방문하므로 node는 범위의 중간에 위치한다는 특징을 알아야 한다. 2025년 5월 5일 1. 히스토그램에서 가장 큰 직사각형 (P5) 문제 : 히스토그램에서 가장 큰 직사각형 알고리즘 : 자료 구조, 분할 정복, 스택 성공 여부 : 성공 (50분

2025년 6월 2일 1. 뉴스 전하기 (G2) 문제 : 뉴스 전하기 알고리즘 : DP, 그리디, 정렬, 트리, 트리에서의 DP 성공 여부 : 성공 (1시간) 풀이 : 패스 복기 : DFS로 모든 트리를 순회하되, 한 노드에서 각 DFS한 결과를 정렬한 뒤 순서에 따른 시간을 추가해주면 된다. 2025년 6월 3일 1. 도로포장 (P5) 문제 : 도로포장 알고리즘 : DP, 그래프 이론, 최단 경로, 데이크스트라 성공 여부 : 성공 (30분) 풀이 : 패스 복기 : K개 이하의 도로를 포장해 1에서 N으로 갈 때 걸리는 최소 시간을 구하는 문제. K개 이하 의 도로를 포장한다는 문장에 주목하면 각 DP에서 다음 상태로 진행할 때, 도로 포장 여부에 따라서 상태가 변경되므로 2차원 DP로 풀면 된다. 그

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