알고리즘
자료구조와 알고리즘을 개념마다 그림과 단계 애니메이션으로 정리했다. 단계 그림은 ◀ ▶ 버튼으로 한 단계씩 넘겨 보거나 재생할 수 있다.
기초와 자료구조
값을 어떻게 담아 두느냐: 복잡도, 배열과 리스트, 해시, 트리
- 복잡도와 기초입력이 커질 때 시간과 메모리가 어떻게 늘어나는지 재는 법과, 메모리·재귀처럼 모든 자료구조의 바탕이 되는 개념이다.빅오 표기 · 최선·평균·최악 · 분할 상환 분석 · 메모리 계층과 캐시 지역성 · 재귀와 호출 스택
- 배열·리스트·스택·큐값을 한 줄로 늘어놓는 자료구조들이다. 어디에 넣고 어디서 꺼내는지가 서로 다르다.배열과 동적 배열 · 연결 리스트 · 스택 · 큐와 덱 · 원형 버퍼
- 해시키를 숫자로 바꿔 곧장 자리를 찾는 방법과, 자리가 겹칠 때의 처리, 확률로 답하는 블룸 필터다.해시 함수 · 체이닝 · 오픈 어드레싱 · 부하율과 재해시 · 블룸 필터
- 트리값을 위아래로 나눠 담아 찾기·넣기를 로그 시간에 하는 자료구조들이다.트리의 낱말 · 이진 탐색 트리 · AVL·레드-블랙 트리 · B-트리 · 이진 힙과 우선순위 큐 · 트라이 · 세그먼트 트리·펜윅 트리
알고리즘
담아 둔 값으로 무엇을 하느냐: 그래프, 정렬, 설계 기법, 문자열
- 그래프점과 선으로 이루어진 관계를 표현하고, 훑고, 가장 짧은 길과 가장 싼 연결을 찾는 알고리즘이다.인접 행렬·인접 리스트 · BFS · DFS · 위상 정렬 · 다익스트라 · 벨먼-포드 · 플로이드-워셜 · 유니온 파인드 · 크루스칼·프림
- 정렬과 탐색값을 순서대로 늘어놓는 여러 방법과, 정렬된 값에서 빠르게 찾는 이진 탐색이다.버블 정렬 · 선택·삽입 정렬 · 병합 정렬 · 퀵 정렬 · 힙 정렬 · 계수·기수 정렬 · 안정성 · 이진 탐색과 lower/upper bound
- 설계 기법새 문제를 만났을 때 꺼내 쓰는 풀이의 틀이다. 나누고, 기억하고, 욕심내고, 되돌아간다.분할 정복 · 동적 계획법 · 탐욕법 · 백트래킹 · 두 포인터·슬라이딩 윈도
- 문자열글 속에서 패턴을 빠르게 찾고, 두 글이 얼마나 다른지 재는 알고리즘이다.단순 탐색 · KMP 실패 함수 · KMP · 라빈-카프 · 편집 거리 · 접미사 배열
- 더 나아가기실무에서 자주 만나는 캐시·확률적 자료구조와, 빠른 풀이가 없는 문제의 이론이다.LRU 캐시 · 스킵 리스트 · HyperLogLog · P와 NP · 근사 알고리즘