tag · 13 posts

#cs

전부 해보는 것과 그러지 않는 것 - 이름과 비용: 알고리즘 ep.00
  • series
  • cover
  • develop
  • frontend
  • backend
  • cs
  • algorithm

전부 해보는 것과 그러지 않는 것 - 이름과 비용: 알고리즘 ep.00

완전탐색을 출발점으로 두고, 탐색 공간을 줄이는 네 가지 근거를 축으로 알고리즘 시리즈의 지도를 그립니다. 그래프 탐색부터 정수론까지 여섯 편의 구성과 서로의 의존 관계를 정리합니다.

read →
문제를 그래프로 바꿔 보기 - 이름과 비용: 알고리즘 ep.01
  • series
  • develop
  • frontend
  • backend
  • cs
  • algorithm
  • graph
  • bfs
  • dfs

문제를 그래프로 바꿔 보기 - 이름과 비용: 알고리즘 ep.01

그래프 표현 두 가지의 선택 기준을 정리하고, 격자와 상태 공간을 그래프로 읽는 방법을 다룹니다. 깊이 우선 탐색과 너비 우선 탐색이 각각 어떤 질문에 답하는지, 너비 우선이 최단 거리를 보장하는 근거는 무엇인지 확인합니다.

read →
탐색 공간을 줄이는 근거 - 이름과 비용: 알고리즘 ep.02
  • series
  • develop
  • frontend
  • backend
  • cs
  • algorithm
  • binarysearch
  • twopointer
  • backtracking

탐색 공간을 줄이는 근거 - 이름과 비용: 알고리즘 ep.02

이분탐색의 전제를 정렬이 아니라 단조성으로 다시 정의하고, 답 자체를 이분탐색하는 파라메트릭 서치로 확장합니다. 경계 조건을 안정적으로 처리하는 템플릿과 투 포인터, 백트래킹의 가지치기, 비트마스킹을 같은 관점으로 묶습니다.

read →
언제 욕심내고 언제 기억하는가 - 이름과 비용: 알고리즘 ep.03
  • series
  • develop
  • frontend
  • backend
  • cs
  • algorithm
  • greedy
  • dp

언제 욕심내고 언제 기억하는가 - 이름과 비용: 알고리즘 ep.03

그리디가 성립하는 두 가지 조건을 정리하고, 증명 대신 반례를 찾는 실용적인 판별법을 다룹니다. 그리디가 깨질 때 동적 계획법으로 넘어가는 과정과 점화식을 세우는 절차, 배낭 문제의 두 변형을 확인합니다.

read →
가중치와 순서와 연결성 - 이름과 비용: 알고리즘 ep.04
  • series
  • develop
  • frontend
  • backend
  • cs
  • algorithm
  • graph
  • dijkstra
  • unionfind

가중치와 순서와 연결성 - 이름과 비용: 알고리즘 ep.04

가중치가 있는 그래프의 최단 경로를 다익스트라로 풀고, 음수 간선과 전체 쌍 최단 거리라는 변형을 확인합니다. 연결 여부만 필요할 때의 유니온 파인드, 최소 비용 연결을 만드는 최소 신장 트리, 순서 제약을 처리하는 위상정렬까지 신호별로 정리합니다.

read →
문자열 안에서 패턴 찾기 - 이름과 비용: 알고리즘 ep.05
  • series
  • develop
  • frontend
  • backend
  • cs
  • algorithm
  • string
  • kmp
  • trie

문자열 안에서 패턴 찾기 - 이름과 비용: 알고리즘 ep.05

나이브 문자열 매칭이 버리는 정보가 무엇인지 짚고, KMP의 실패 함수가 그 정보를 어떻게 저장하는지 다룹니다. 해시로 비교하는 라빈카프와 접두사를 공유하는 트라이까지 문자열 전용 구조를 정리합니다.

read →
정수를 다루는 도구들 - 이름과 비용: 알고리즘 ep.06
  • series
  • develop
  • frontend
  • backend
  • cs
  • algorithm
  • numbertheory
  • modular
  • bigint

정수를 다루는 도구들 - 이름과 비용: 알고리즘 ep.06

유클리드 호제법과 에라토스테네스의 체를 원리부터 정리하고, 모듈러 연산이 어떤 성질 위에서 안전한지 확인합니다. 자바스크립트에서 정수 정밀도가 깨지는 경계와 BigInt로 넘어가는 기준까지 다루며 두 시리즈를 마칩니다.

read →
이미 쓰고 있는 것들의 이름 - 이름과 비용: 자료구조 ep.00
  • series
  • cover
  • develop
  • frontend
  • backend
  • cs
  • datastructure
  • algorithm

이미 쓰고 있는 것들의 이름 - 이름과 비용: 자료구조 ep.00

자료구조와 알고리즘을 두 개의 시리즈로 나눠 다룹니다. 자료구조 시리즈는 데이터를 담고 정리하는 구조를, 알고리즘 시리즈는 그 안에서 찾고 결정하는 방법을 봅니다. 각 편이 독립적으로 읽히도록 구성했고, 이 편은 전체 지도 역할을 합니다.

read →
크기가 접근법을 정한다 - 이름과 비용: 자료구조 ep.01
  • series
  • develop
  • frontend
  • backend
  • cs
  • datastructure
  • complexity
  • bigo

크기가 접근법을 정한다 - 이름과 비용: 자료구조 ep.01

시간 복잡도를 정의부터 다시 정리하고, 입력 크기 N에서 허용 가능한 복잡도를 역산하는 방법을 다룹니다. 상수를 버리는 표기법의 이점과 한계, 최선과 평균과 최악을 구분해야 하는 이유, 공간 복잡도를 함께 세는 습관까지 확인합니다.

read →
배열과 해시의 진짜 비용 - 이름과 비용: 자료구조 ep.02
  • series
  • develop
  • frontend
  • backend
  • cs
  • datastructure
  • array
  • hashmap
  • queue

배열과 해시의 진짜 비용 - 이름과 비용: 자료구조 ep.02

배열이 연속된 메모리라는 사실에서 따라오는 비용 구조를 정리하고, 해시 테이블의 충돌 처리 방식과 평균 성능이 깨지는 조건을 확인합니다. 자바스크립트 배열로 큐를 만들 때 생기는 함정과 그 해법도 함께 다룹니다.

read →
내장 정렬이 보장하는 것 - 이름과 비용: 자료구조 ep.03
  • series
  • develop
  • frontend
  • backend
  • cs
  • datastructure
  • sorting
  • javascript

내장 정렬이 보장하는 것 - 이름과 비용: 자료구조 ep.03

자바스크립트 기본 정렬이 값을 문자열로 바꾼다는 사실에서 출발해, 안정 정렬이라는 성질이 다중 기준 정렬에서 어떻게 작동하는지 다룹니다. 퀵 정렬과 병합 정렬과 힙 정렬의 성격 차이, 비교 정렬의 하한과 그것을 우회하는 계수 정렬까지 정리합니다.

read →
트리의 모양이 성능을 만든다 - 이름과 비용: 자료구조 ep.04
  • series
  • develop
  • frontend
  • backend
  • cs
  • datastructure
  • tree
  • heap
  • priorityqueue

트리의 모양이 성능을 만든다 - 이름과 비용: 자료구조 ep.04

이진탐색트리가 절반씩 버리는 원리와 그 전제가 무너지는 편향 상황을 확인하고, 균형 트리가 어떤 방식으로 높이를 통제하는지 정리합니다. 힙이 완전 정렬을 포기해서 얻는 이득과, 자바스크립트에 없는 우선순위 큐를 직접 구현하는 방법도 다룹니다.

read →
같은 구간을 반복해 묻는다면 - 이름과 비용: 자료구조 ep.05
  • series
  • develop
  • frontend
  • backend
  • cs
  • datastructure
  • prefixsum
  • segmenttree

같은 구간을 반복해 묻는다면 - 이름과 비용: 자료구조 ep.05

누적합으로 구간 질의를 상수 시간으로 만드는 방법과 2차원 확장을 다루고, 중간에 값이 바뀌는 상황에서 그 전략이 무너지는 지점을 확인합니다. 세그먼트 트리가 질의와 갱신을 모두 O(log N)으로 유지하는 원리와 선택 기준을 정리합니다.

read →