#algorithm
노트 60개
Frontend › JavaScript
정규식 엔진: 탐욕·게으름·전후방탐색·백트래킹JavaScript 정규식 엔진은 백트래킹 방식이다. 탐욕 수량자는 최대한 먹고 한 글자씩 돌려주며, 게으른 수량자는 최소한으로 먹고 하나씩 늘린다. 둘보다 제외 세트가 정확할 때가 많다. 전후방탐색은 결과에 넣지 않고 조건만 건다. 겹치는 중첩 수량자는 실패할 때 경우의 수가 지수적으로 늘어 페이지를 멈추게 하며(재앙적 백트래킹·ReDoS), 경우의 수를 줄이거나 전방탐색으로 원자 그룹을 흉내 내 막는다.
Backend › Architecture
실시간 공동 편집: OT와 CRDT구글 문서처럼 여럿이 동시에 고치는 편집기는 편집을 문서 전체가 아니라 연산(삽입·삭제) 단위로 WebSocket으로 주고받고, 동시에 일어난 연산을 충돌 없이 합치는 알고리즘이 핵심이다. 중앙 서버가 연산을 변환하는 OT, 연산 자체를 교환·결합 가능하게 만든 CRDT, 차이를 주고받는 차등 동기화가 있다.
Backend › Architecture
실시간 트렌딩과 Top-K 집계최근 시간 창에서 가장 많이 언급된 상위 K개를 구하는 문제를 정리했다. 슬롯 링 버퍼로 만드는 슬라이딩 창 카운터, 키별 카운트 → 부분 순위 → 전역 순위의 3단 집계, 창이 밀릴 때 다시 계산하지 않는 최소 후보 집합(MinTopk), 키가 너무 많을 때의 근사 Top-K, 과거 패턴과의 거리로 트렌드를 일찍 잡는 비모수 방법까지 다룬다.
Backend › Architecture
위치 기반 서비스 설계: 지오해시, 쿼드트리, 지도'내 주변 식당'은 모든 점과의 거리를 계산하면 느리므로 지도를 격자로 나눠 색인한다. 지오해시는 위경도를 접두사가 같으면 가까운 문자열로 바꿔 DB 색인으로 찾고, 쿼드트리는 밀도에 따라 칸을 쪼갠 메모리 트리로 찾는다. 지도 서비스는 위치 수집, 미리 잘라 둔 타일의 CDN 서빙, 지오코딩과 경로 계산으로 나뉜다.
Backend › Database
검색엔진의 원리: 역인덱스와 랭킹검색엔진은 문서를 토큰으로 쪼개 단어 → 문서의 역인덱스를 만들고(색인), 질의어를 같은 방식으로 처리해 찾은 뒤 TF-IDF·BM25 같은 점수로 순서를 정한다(질의). 한국어는 형태소 분석이나 N-gram이 필요하다.
Backend › Database
웹 검색엔진의 동작: 크롤링, 색인, 랭킹, 질의 처리웹 검색엔진은 크롤러가 링크 그래프를 따라 페이지를 모으고, 중복을 묶어 샤딩된 역인덱스에 넣은 뒤, 질의가 오면 의도를 해석해 후보를 뽑고 여러 랭킹 신호로 순서를 정한다. 크롤러의 URL 프런티어, PageRank, 2단계 랭킹, 구글의 랭킹 시스템과 네이버 통합검색의 컬렉션 구조를 자료구조·알고리즘 관점에서 정리했다.
Computer Science › Programming Languages
C++ STL 컨테이너와 시간 복잡도C++ 표준 라이브러리의 vector·deque·list·set·map·unordered 컨테이너가 내부적으로 어떤 자료구조인지, 그래서 연산별 시간 복잡도가 어떻게 되는지 정리한다. vector 끝 삽입은 용량을 배수로 늘리기 때문에 분할 상환 O(1)이고, set·map은 레드-블랙 트리라 O(log n)이다.
Computer Science
데이터 압축: 무손실과 손실데이터를 더 적은 비트로 표현하는 압축의 두 갈래를 정리한다. 무손실 압축은 반복을 줄이는 런 렝스 부호화, 반복 구간을 참조로 바꾸는 사전 방식(LZ 계열), 자주 나오는 기호에 짧은 부호를 주는 허프만 부호화로 만들고, 손실 압축은 사람의 지각이 둔한 정보를 버리는 지각 부호화다. 동영상은 프레임 사이의 중복까지 없앤다.
Computer Science
베지어 곡선베지어 곡선은 제어점 몇 개로 매끄러운 곡선을 정의하는 방법이다. 두 점 사이 선형 보간을 겹겹이 반복하는 드 카스텔조 알고리즘으로 1차(직선)·2차·3차 곡선 식과 행렬 표현을 유도하고, 펜 툴·SVG·CSS·폰트에서 어떻게 쓰이는지 정리한다.
Computer Science
양자 컴퓨터의 원리: 큐비트, 양자 알고리즘, 양자 게이트양자 컴퓨터는 중첩된 큐비트를 쓰지만 모든 답을 한꺼번에 확인하지는 못한다. 핵심은 확률 진폭의 간섭으로 정답이 관측될 확률을 키우는 양자 알고리즘이다. 큐비트, 블로흐 구면과 X·H·CNOT 게이트, 그로버·쇼어 알고리즘, 암호에 미치는 영향과 흔한 오해를 정리했다.
Computer Science
피드백 제어와 PID 제어기: 로봇이 목표값에 닿는 법로봇은 컴퓨터 제어로 물리 세계에서 일련의 동작을 자동으로 하는 기계다. 센서 → 오차 → 제어기 → 구동기로 도는 음의 피드백 루프, 무거운 물체가 목표를 지나쳐 진동하는 오버슈트, 현재·과거·미래의 오차를 비례·적분·미분 항으로 더하는 PID 제어기, 제어 루프 위에서 목표값을 정하는 상위 계획, 사람에게 쉬운 일이 로봇에게 어려운 모라벡의 역설을 정리한다.
Algorithm
자료구조, 탐색, 그래프, 알고리즘 설계 패러다임, 정렬, 복잡도 분석과 코딩 테스트 전략을 모은 알고리즘 노트.
Algorithm
자료구조알고리즘 문제에서 데이터를 담고 꺼내는 방식을 정하는 기본 자료구조 모음.
Algorithm › Data Structure
세그먼트 트리배열을 구간별로 나눠 각 구간의 합·최솟값 같은 요약을 이진 트리에 저장해, 값이 바뀌는 배열에서도 구간 질의와 갱신을 모두 O(log n)에 처리하는 자료구조. 배열 크기 잡기, 재귀 구현, 지연 전파와 펜윅 트리 비교까지 정리한다.
Algorithm › Data Structure
트리와 이진 탐색 트리계층 구조를 표현하는 트리의 용어, 이진 트리의 종류와 배열 표현, 네 가지 순회와 반복 구현, 이진 탐색 트리의 연산·편향·검증, 균형 트리의 종류와 AVL 회전, 레드-블랙 트리가 널리 쓰이는 이유, B 트리와 B+ 트리의 차이.
Algorithm › Data Structure
해시 테이블키를 해시 함수로 배열 인덱스로 바꿔 평균 O(1)에 찾는 해시 테이블의 원리, 해시 함수 설계(나눗셈·곱셈·다항·보편 해싱), 개방 주소법과 분리 연결법의 충돌 해결 비교와 이중 해싱의 약점, 적재율과 리사이즈, Java HashMap·Python dict 같은 실제 구현, 빈도 세기·애너그램 같은 문제 풀이 패턴, 해시 맵과 연결 리스트로 만드는 O(1) LRU·LFU 캐시.
Algorithm
그래프정점과 간선으로 관계를 표현하는 그래프의 기본 개념과 최단 경로 알고리즘.
Algorithm › Graph
그래프의 기본과 표현 방법정점과 간선으로 이루어진 그래프의 종류, 사이클 없는 그래프와 트리의 차이, 인접 행렬·인접 리스트로 저장하는 방법과 밀집·중복 간선의 처리, 탐색 기법과 놓치기 쉬운 경우.
Algorithm › Graph
다익스트라 최단 경로음이 아닌 가중치 그래프에서 한 정점으로부터 모든 정점까지의 최단 거리를 우선순위 큐로 구하는 알고리즘.
Algorithm › Graph
단절점과 단절선지우면 그래프가 끊어지는 정점(단절점)과 간선(단절선)을 DFS 방문 순서와 low 값으로 O(V + E)에 찾는 방법.
Algorithm › Graph
오일러 경로와 오일러 회로모든 간선을 정확히 한 번씩 지나는 경로·회로의 존재 조건(차수의 짝홀)과, 히어홀저 알고리즘으로 O(V + E)에 회로를 구하는 방법. 다중 간선에서 이미 쓴 간선을 다시 훑지 않는 요령을 함께 정리한다.
Algorithm › Graph
위상 정렬방향 비순환 그래프(DAG)의 정점을 모든 간선 u→v에서 u가 앞에 오도록 나열하는 위상 정렬. 진입 차수와 큐를 쓰는 칸 알고리즘, DFS 후위 순서를 뒤집는 방법, 사이클 판별, 사전순 최소 순서를 정리한다.
Algorithm › Graph
최단 경로 알고리즘 고르기가중치 유무, 음수 간선·음수 사이클, 출발점 하나인지 모든 쌍인지, 목적지가 하나인지에 따라 BFS·0-1 BFS·다익스트라·벨만-포드·플로이드-워셜·DAG 최단 경로·A*를 고르는 기준과 각 알고리즘의 원리, 트리와 밀집 그래프에서의 선택.
Algorithm › Graph
최소 공통 조상 (LCA)트리에서 두 노드의 가장 가까운 공통 조상을 찾는 LCA. 깊이를 맞춰 함께 올라가는 O(N) 방법과, 2^k번째 조상 표(희소 테이블)로 질의마다 O(log N)에 답하는 이진 올리기(binary lifting), 두 노드 사이 거리 구하기까지.
Algorithm › Graph
최소 신장 트리: 크루스칼과 프림가중치 그래프의 모든 정점을 사이클 없이 가장 싸게 잇는 최소 신장 트리와, 간선을 고르는 크루스칼·정점을 넓혀 가는 프림 알고리즘의 동작·복잡도·선택 기준, 결과가 늘 트리인 이유와 비연결 그래프의 최소 신장 숲.
Algorithm
알고리즘을 위한 수학점화식의 일반항, 벡터공간, 내적·외적과 거리처럼 알고리즘 분석과 계산 기하에 쓰이는 수학 노트 모음.
Algorithm › Math
미분과 적분 기초극한과 연속, 순간변화율로서의 도함수와 미분 규칙(곱·몫·연쇄 법칙), 지수·로그·삼각함수의 도함수, 증감과 극값을 이용한 최적화, 누적으로서의 적분과 미적분학의 기본 정리를 정리하고 수치 미분·경사 하강·수치 적분 코드로 연결한다.
Algorithm › Math
벡터 내적·외적과 거리내적이 수직과 정사영을, 외적이 방향과 넓이를 알려 주는 원리. 법선 벡터로 점과 초평면 사이 거리 공식을 유도하고, 계산 기하에서 쓰는 CCW·점과 직선 거리 계산, 제곱 거리 비교와 원·직사각형 겹침 판정을 정리한다.
Algorithm › Math
비트 연산 기법정수의 비트를 직접 다루는 연산자와 관용구. k번째 비트 검사·설정·끄기·뒤집기, 2의 거듭제곱 판별, 최하위 1비트, XOR의 성질, 비트마스크로 집합 표현하기, 언어별 정수 폭과 음수 처리 차이.
Algorithm › Math
선형 점화식의 일반항상수 계수 선형 점화식의 일반항을 생성함수, 특성방정식, 행렬 대각화 세 가지로 구하고, 세 방법이 같은 고유값을 찾는 일임을 야콥스탈 수열로 보인다.
Algorithm › Math
수학적 최적화와 정수 계획법배정·일정·적재 같은 조합 문제를 결정 변수·제약 조건·목적 함수로 적어 솔버에 맡기는 방법. 전용 알고리즘·휴리스틱·솔버 모델링의 차이, 정수 선형 계획법 모델링 예(구간 배정), 목적 함수 설계와 운영에서의 주의점을 정리했다.
Algorithm › Math
순열과 조합순서를 따지는 순열과 따지지 않는 조합의 공식을 재귀적으로 유도하고, 파스칼 점화식과 이항 정리, 중복 순열·중복 조합, 완전 탐색의 경우의 수 추정과 파이썬 구현을 정리한다.
Algorithm › Math
정수론 기초: 소수·최대공약수·합동식알고리즘 문제와 암호에 자주 나오는 정수론을 정리한다. 산술의 기본 정리와 나눗셈 정리, 유클리드 호제법과 베주 항등식(확장 유클리드), 에라토스테네스의 체로 소인수분해, 선형 합동식과 중국인의 나머지 정리, 오일러 피 함수와 페르마의 소정리, 약수 함수와 뫼비우스 함수, 선형 합동 생성기와 자릿수 묶음으로 큰 정수 더하기.
Algorithm › Math
푸리에 변환신호를 여러 주파수의 사인·코사인 성분의 합으로 분해해 시간·공간 영역을 주파수 영역으로 바꾸는 변환. 디지털 신호에는 이산 푸리에 변환(DFT)을 쓰고 FFT로 O(n log n)에 계산한다. 크기(스펙트럼)는 성분의 세기, 위상은 위치 정보를 담으며, 주파수 영역에서 필터링한 뒤 역변환한다.
Algorithm
알고리즘 설계 기법문제를 쪼개고, 기억하고, 매 순간 최선을 고르는 등 알고리즘을 설계하는 대표적인 사고방식.
Algorithm › Paradigm
그리디 알고리즘매 선택의 순간마다 당장 가장 좋아 보이는 것을 골라 최종 해답에 도달하는 방법과 그 정당성 확인. 거스름돈과 로마 숫자 변환을 예로 든다.
Algorithm › Paradigm
동적 계획법 (DP)겹치는 하위 문제의 답을 한 번만 계산해 저장하고 재사용하여 큰 문제를 효율적으로 푸는 기법. 하위 문제를 찾는 연습(타일링)과 구간 DP(연쇄 행렬 곱셈)를 함께 다룬다.
Algorithm › Paradigm
분할 정복문제를 서로 독립적인 작은 하위 문제로 나누어 재귀적으로 풀고, 그 결과를 합쳐 원래 문제를 해결하는 기법과, 실행 시간을 점화식(반복 대입·추정 후 증명·마스터 정리)으로 구하는 법.
Algorithm › Paradigm
스위핑 (Sweep Line)데이터를 정렬해 한 방향으로 한 번만 훑으며 답을 갱신하는 기법. 구간 겹침 판정·병합 같은 구간 문제의 기본 부품, 겹치는 구간 세기와 평면을 직선으로 나누는 기하 문제를 예로 든다.
Algorithm › Paradigm
재귀 함수자기 자신을 다시 호출해 문제를 더 작은 같은 문제로 줄여 가는 함수와 그 종료 조건. 예제로 팩토리얼과 유클리드 호제법(최대공약수·최소공배수)을 다룬다.
Algorithm › Paradigm
최장 증가 부분 수열 (LIS)수열에서 순서를 지키며 고른 증가 부분 수열 중 가장 긴 것을 구하는 문제. O(n²) DP, 이분 탐색으로 길이를 구하는 O(n log n) 방법, 실제 수열까지 복원하는 방법.
Algorithm › Paradigm
투 포인터와 슬라이딩 윈도우인덱스 두 개를 규칙에 따라 움직여 이중 반복문 O(n²)을 O(n)으로 줄이는 기법. 양 끝에서 좁히기, 같은 방향 윈도우, 두 배열 병합·교집합, 빠른·느린 포인터의 네 가지 모양과 회문 판정·중심 확장을 정리한다.
Algorithm
탐색가능한 경우를 빠짐없이, 또는 영리하게 줄여 가며 답을 찾는 탐색 알고리즘 모음.
Algorithm › Search
깊이 우선 탐색 (DFS)한 갈래를 갈 수 있는 데까지 파고든 뒤 되돌아오는 그래프 탐색으로, 스택이나 재귀로 구현한다.
Algorithm › Search
너비 우선 탐색 (BFS)시작점에서 가까운 노드부터 큐를 이용해 차례로 방문하는 그래프 탐색으로, 가중치 없는 그래프의 최단 거리를 구한다.
Algorithm › Search
완전 탐색과 백트래킹가능한 모든 경우를 나열해 답을 찾는 방법과, 가망 없는 경로를 일찍 잘라내는 백트래킹.
Algorithm › Search
이분 탐색정렬된 데이터에서 탐색 범위를 절반씩 줄여 O(log n)에 원하는 값을 찾는 방법과 그 복잡도 증명, lower bound·upper bound, 경계 조건 실수, 삼분할이 빠르지 않은 이유, 순차 탐색과 어느 쪽을 고를지.
Algorithm
정렬데이터를 일정한 순서로 나열하는 대표적인 정렬 알고리즘과 그 복잡도.
Algorithm › Sorting
기본 정렬: 버블·선택·삽입·셸·계수·기수 정렬구현이 단순한 O(n²) 비교 정렬 세 가지와 입력 상태에 따른 실제 속도 비교, 간격을 줄여 가며 삽입 정렬하는 셸 정렬, 비교 없이 정렬하는 계수 정렬·기수 정렬(LSD·MSD).
Algorithm › Sorting
병합 삽입 정렬 (Ford-Johnson)비교 횟수를 최소화하도록 설계된 Ford-Johnson 알고리즘. 짝짓기로 큰 원소를 재귀 정렬하고, 작은 원소를 야콥스탈 수 순서로 이진 삽입해 이진 탐색 비용을 낭비하지 않는다.
Algorithm › Sorting
병합 정렬과 퀵 정렬분할 정복으로 평균 O(n log n)에 정렬하는 두 대표 알고리즘과 상향식 병합 정렬, 퀵 셀렉트, 정렬 알고리즘 복잡도·안정성 비교, 언어별 표준 정렬, 메모리보다 큰 데이터의 외부 정렬.
Algorithm
구간 합과 접두사 합앞에서부터의 누적 합을 미리 구해 두고, 임의 구간의 합을 뺄셈 한 번으로 구하는 기법. 접미사·곱 변형과 해시를 곁들여 합이 k인 부분 배열을 세는 방법.
Algorithm
빅오 표기법과 시간 복잡도입력 크기가 커질 때 알고리즘의 연산량이 어떻게 늘어나는지를 최고차항으로 표현하는 방법과, 상한(O)·하한(Ω)·딱 맞는 범위(Θ)의 차이.
Algorithm
코딩 테스트 접근법주석으로 설계하고 테스트 케이스를 먼저 적는 문제 풀이 순서, 출제 빈도별 알고리즘 우선순위, 막혔을 때 풀이를 볼 시점을 정하는 연습법과 그 방식이 자기기만이 되는 함정, 랜덤 비교 테스트로 반례 찾기, 막혔을 때 접근을 찾는 관점과 이론상 최선 복잡도(BTTC)를 기준으로 시간·공간을 줄이는 최적화 기법, 파이썬·자바스크립트 실전 팁.
Algorithm
파싱 알고리즘과 프랫 파서토큰열을 구문 트리로 만드는 파싱 알고리즘의 흐름. BNF 규칙을 함수로 옮기는 재귀 하향 파서(JSON 예제), 연산자 우선순위로 그리디하게 묶는 플로이드의 상향식 파서, 바인딩 파워로 둘의 장점을 합친 프랫 파서를 셸 문법 예제로 정리한다.
Algorithm
현실 시스템을 움직이는 알고리즘과 자료구조일상 소프트웨어에서 자료구조가 쓰이는 곳(피드의 리스트, 실행 취소의 스택, 캐시의 해시 테이블, DOM의 트리, 지도 검색의 R-트리), 대규모 시스템 설계에 자주 나오는 알고리즘(일관된 해싱, 지오해시·쿼드트리, 블룸 필터, HyperLogLog, 토큰 버킷, 머클 트리, 합의 알고리즘), 세상을 움직이는 아홉 가지 알고리즘을 정리한다. 블룸 필터는 중복 URL 크롤링 방지 예로 자세히 본다.
Algorithm
KMP 문자열 검색 알고리즘텍스트에서 패턴을 찾을 때 불일치가 나도 텍스트 포인터를 되돌리지 않는 KMP 알고리즘. 패턴의 접두사이자 접미사인 가장 긴 부분의 길이를 담은 실패 함수(pi 배열)로 점프할 위치를 정해 O(N + M)에 검색한다. 롤링 해시로 창을 비교하는 라빈-카프와 다른 문자열 검색 알고리즘도 비교한다.
AI & Data
문자열·문서 유사도: 편집 거리와 코사인 유사도검색어와 제목처럼 짧은 문자열은 편집 거리·Jaro-Winkler로, 키워드 묶음처럼 긴 문서는 벡터화 후 코사인 유사도로 비교한다. L1·L2·L∞ 거리와 자카드 유사도, 희소 벡터의 한계, 문서가 많을 때의 역색인·LSH와 k-means 군집도 다룬다. 영화 검색·추천 기능에 적용한 파이썬 예제와 함께 정리.
Career › Job Search
기술 면접 준비: 유형별 대비와 시스템 디자인 7단계개발자 기술 면접은 코딩, 시스템 디자인, 객체 지향 설계(OOD), 행동(behavioral) 면접으로 나뉜다. 유형별로 무엇을 보는지와 준비 자료, 퀴즈·온라인 코딩 테스트·과제·화상 면접·온사이트 같은 진행 형식별 대비, 면접 언어 고르기, 남은 시간에 맞춘 준비 계획(주제 우선순위, Blind 75·Grind 75), 코딩 인터뷰를 자기소개 → 질문 명확화 → 접근 논의 → 말하며 코딩 → 테스트 → 역질문으로 진행하는 법을 정리하고, 시스템 디자인 면접의 유형과 요구 사항 확인 → 용량 추정 → 상위 설계 → DB 설계 → 인터페이스 설계 → 확장성 → 신뢰성의 7단계를 다룬다.
Career › Work
컴퓨팅 사고와 개발 실력 늘리는 법컴퓨팅 사고는 문제를 분해·패턴 인식·추상화·알고리즘으로 다듬어 컴퓨터가 실행할 수 있는 절차로 바꾸는 사고다. 요구사항을 데이터의 관점으로 다시 정의하는 법, 알고리즘을 자연어·순서도·의사 코드로 적는 법과 순차·선택·반복의 세 제어 구조, 알고리즘 공부가 프론트엔드 개발자에게도 필요한 이유, 개발을 운동처럼 훈련하는 방법을 정리했다.