알아야 할 알고리즘/자료구조 키워드 정리

출처: 포큐아카데미 (알고리듬 및 자료구조 수업의 목차)

이론적으로는 전부 다 알아두고, 코드 구현은 적어도 그래프 이전까지는 할 줄 알아야 한다.

• 점근 표기법과 빅오 표기법
• 기초 자료 구조와 시간 복잡도

• 재귀함수
• 주먹구구식(brute-force) 알고리듬
• P vs NP 문제
• 이진 탐색

• 버블 정렬
• 선택 정렬
• 삽입 정렬
• 퀵 정렬
• 병합 정렬
• 힙 정렬

• 비암호학적 해시 함수
• 체크섬과 CRC
• 암호학적 해시 함수

• 대칭 키 암호화
• 비대칭 키 암호화

• 트리 순회
• 이진 탐색 트리
• 레드-블랙 트리

• 트라이(Trie)
• 공간분할 트리

 

• 깊이 우선 탐색(DFS)
• 너비 우선 탐색(BFS)
• 미니맥스 알고리듬

• 동적 계획법(Dynamic Programming)
  • 메모이제이션(memoization)
  • 타뷸레이션(tabulation)
  • 배낭 문제
• 그리디 알고리듬
  • 동전 교환 문제
  • 인터벌 스케줄링
  • 허프만 코딩
• 데이터 압축

• 그래프
• 그래프의 깊이 우선 탐색
• 위상 정렬
• 강한 연결 요소

• 그래프의 너비 우선 탐색
• 최단 경로 찾기
  • BFS
  • 다익스트라 알고리듬 (Dijkstra's algorithm)
  • A* 알고리듬
  • 플로이드 워셜

• 최소 (비용) 신장 트리
• 외판원 문제
• 최대 유량 문제

• 유한 상태 기계
  • 정규 표현식(regex)
• K-최근접 이웃
• 기타 알고리듬 기법들
  • 선형계획기법
  • 병렬 알고리듬