LIS(Longest Increasing Subsequence)는 알고르짐 입문자에게는 필수지만,실전 코딩테스트나 알고르짐 경시에서는 단순 LIS 문제가 거의 출제되지 않습니다. 대신, LIS를 응용하거나 변형해서 풀어야 하는 문제가 다양하게 등장합니다.예를 들어:수열을 최소 횟수로 정렬하는 법정렬을 방해하는 "장애물 수열" 탐지여러 수열을 동시에 중첩 배치하는 문제문자열, 트리 구조, LCS 문제를 LIS로 환원하는 문제 등 실전에서 자주 등장하는 변형 유형 5가지유형키워드핵심 로직정렬 최소 편집정렬을 위해 제거해야 할 최소 원소 수n - LIS수열 재배치 최적화재배치 횟수 최소화LIS 활용두 수열 매핑LCS 문제를 LIS로 변환위치 배열 매핑장애물/포함 관계 처리중첩 가능한 상자/사람/건물 수 최대정..

왜 확장이 필요한가?기본 LIS(최장 증가 부분 수열)는단조 증가하는 수열 하나만 고려합니다. 하지만 실전 문제에서는 다음과 같은 유형도 등장합니다: LDS (Longest Decreasing Subsequence) – 감소하는 수열 Bitonic (이중 수열) – 증가했다가 감소하는 수열 Double LIS – 앞에서 LIS, 뒤에서 LIS 또는 LDS 등 양방향 접근 문제 – 양쪽에서 동시에 LIS/LDS 계산 최장 감소 부분 수열 (LDS)정의: LSD는 원소들이 점점 작아지는 부분 수열 중 가장 긴 것을 의미합니다. 예시:arr = [5, 3, 4, 8, 6, 7]→ LDS: [5, 4] or [8, 6] → 길이 = 2 핵심: LIS와 구조가 거의 동일, 단 부등호 방향만 반대입니다. Pytho..

LIS (Longest Increasing Subsequence) 란? 어떤 수열에서 순서를 바꾸지 않고, 값이 점점 증가하는 부분 수열 중가장 긴 것의 길이를 구하는 문제입니다.예시:수열: [10, 20, 10, 30, 20, 50] → LIS: [10, 20, 30, 50] → 길이 = 4 여기서 말하는 “부분 수열”은연속된 값이 아니어도 되고, 원래 순서를 유지하기만 하면 됩니다. 이 문제, 왜 중요한가요? LIS는 1차원 DP의 대표 문제입니다.또한, 이분 탐색을 접목한 시간 최적화 기법까지 등장하는 알고리즘 진화 사례이기도 합니다.실무에서도 아래와 같은 패턴으로 자주 등장합니다: 실전 분야 활용 사례 주식 분석오름차순으로 수익을 최대화하는 거래 흐름 탐색게임 점수/레벨 분석상승하는 상..

문제 개요: “두 문자열에서 가장 긴 공통 부분 수열을 찾아라”LCS(Longest Common Subsequence) 문제는,두 문자열 A와 B가 주어졌을 때"순서를 유지하면서 가장 긴 공통 부분 수열"의 길이를 구하는 문제입니다. 주의: 부분 문자열(substring)이 아니라 부분 수열(subsequence)입니다. 예시:A = "ACAYKP"B = "CAPCAK"→ LCS = "ACAK" → 길이 = 4부분 수열 vs 부분 문자열 차이 항목부분 수열부분 문자열 정의순서 유지, 중간 문자 건너뛰기 가능연속된 문자의 부분예"ACAYKP" → "AYK", "AK" 가능"ACAYKP" → "ACA"만 가능문제 예시LCS, 부분 집합 문제슬라이딩 윈도우, 연속 최대합 등핵심 사고 방식: DP 테이블로 두..

MST란? – 최소한의 비용으로 그래프를 ‘연결’하는 법최소 신장 트리 (Minimum Spanning Tree)란,모든 정점을 연결하면서, 전체 간선 가중치의 합이 최소가 되도록 구성된 트리즉,모든 노드를 연결하되사이클 없이전체 비용이 최소가 되도록여기서 "트리(Tree)"는 사이클이 없는 연결 그래프를 의미합니다.언제 필요한가? (실전 예시) 실전 상황설명 전기 배선 설계건물 간 최소 전선 비용으로 연결네트워크 케이블 배치컴퓨터/라우터를 최소 거리로 연결도로, 철도 노선 설계최소 토목 비용으로 모든 지역 연결데이터 클러스터링거리 기반 클러스터 연결 구조 도출MST 문제의 조건 정리그래프는 연결 그래프여야 함모든 간선의 가중치는 0 이상여러 개의 MST가 존재할 수 있음 (중복 간선 비용)핵심: 사이..

문제 정의: 출발점이 고정되지 않은 최단경로 탐색앞선 다익스트라와 벨만-포드는 모두“특정 시작점에서 다른 모든 노드까지의 거리”를 구하는 알고리즘입니다.하지만 실전에서는 이런 상황도 자주 생깁니다:A → B 최단거리?모든 도시 쌍 간의 최소 소요 시간은?특정 노드에서 어떤 노드로 거쳐 갈 때 경로는 어떤가?이렇게 모든 정점 쌍 (i, j)에 대해 최단 거리를 구해야 하는 경우,플로이드–워셜 알고리즘이 가장 효과적입니다.개념 요약: 경유지를 하나씩 늘려가며 최단 거리 갱신플로이드–워셜 알고리즘은"한 노드에서 다른 노드로 갈 때, 어떤 노드를 거치면 더 짧아질 수 있을까?"를 매 반복마다 전체 쌍에 대해 확인합니다.이 알고리즘의 핵심은 **DP 테이블(2차원 배열)**을 쓰는 것입니다.핵심 아이디어:모든 노..

벨만-포드 알고리즘이란?벨만-포드(Bellman-Ford) 알고리즘은 음수 가중치 간선이 포함된 그래프에서도 한 시작점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. 다른 정리로는,Dijkstra는 음수 가중치 간선이 있으면 작동하지 않습니다.반면 Bellman-Ford 알고리즘은음수 간선이 존재하는 그래프에서도 최단 경로를 안전하게 구할 수 있는 알고리즘입니다.또한, 사이클 판별 기능까지 갖춘 다목적 알고리즘입니다.언제 Bellman-Ford를 써야 할까? 조건설명그래프 유형방향 또는 무방향 그래프 (음수 간선 포함)가중치음수/양수 모두 허용목적단일 출발점 기준 최단 거리사이클음수 사이클도 탐지 가능실전 예시환율 우회 이익(Arbitrage) 계산일정/자원 배분 시 마이너스 패널티가 존재..

위상 정렬이란?여러 작업이 있고, 어떤 작업은 다른 작업이 끝난 후에만 시작할 수 있을 때,전체 작업의 합리적인 순서를 정리하는 방법입니다. 예를 들어:1학년 수학을 들어야 2학년 미적분을 들을 수 있고,미적분을 들어야 3학년 공업수학을 들을 수 있다면→ 이 관계를 반영한 전체 수강 순서를 정해주는 게 위상 정렬입니다.비유로 말하자면,위상 정렬은 요리를 할 때, 어떤 재료를 언제 준비해야 할지를 알려주는 순서표와 같습니다.감자 껍질을 벗기고 삶은 다음에야 감자 샐러드를 만들 수 있듯이, "선행 과정이 끝난 후에만" 다음 단계로 넘어갈 수 있습니다. 이렇게 작업간의 선후관계가 존재하는 상황에서,그 순서를 위배하지 않고 전체 작업을 나열하는 알고리즘이 바로 위상 정렬 (Topological Sort) 입니다..

백트래킹이란?Backtracking은"모든 가능성을 시도하되, 가능성이 없는 가지는 빠르게 포기하는 전략" 입니다.DFS기반으로 경로를 탐색하다가 조건을 만족하지 않으면 되돌아가서(Backtrack) 다시 다른 경로를 시도는 하는 방식입니다.백트래킹이 필요한 문제의 특징해가 여러 개 존재 (조합, 순열, 경로 등)모든 경우를 탐색해야 하되, 중간에 가지치기(pruning) 가능대표 키워드:"모든 경우의 수""최대/최소""가능한 배치""n개의 원소를 이용해 조건 만족하는 케이스 찾기" DFS와 백트래킹의 차이항목DFS백트래킹목적그래프 전체 탐색조건 만족하는 해 찾기되돌아오기단순 순회조건 만족 못하면 되돌아감 (Pruning)사용 구조재귀/스택재귀 + 조건 분기 + 가지치 1: 순열 (Permutation)..

Union-Find란?여러 개의 원소가 있을 때,어떤 원소가 어떤 집합에 속해 있는지 빠르게 알 수 있도록 해주는 자료구조입니다.Find: 어떤 원소가 어느 집합에 속해 있는지 찾기Union: 두 집합을 하나로 합치기 어떤 상황에서 쓰일까? 그래프의 사이클 판별크루스칼 알고리즘 (최소 신장 트리)네트워크 연결 여부 판단집합의 묶음 관리기본 구현 (Python)# 1. 자기 자신을 부모로 초기화parent = [i for i in range(10)]# 2. Find 함수 (재귀)def find(x): if parent[x] != x: return find(parent[x]) return x# 3. Union 함수def union(x, y): root_x = find(x) ..