[JS] 알고리즘(Algorithm) 종류

알고리즘의 개념, 공부방향, 종류

완성되지 않은 문서입니다. 정리되는대로 추가할 예정입니다.

알고리즘(Algorithm)

제한된 공간과 시간 안에서 데이터를 어떻게 처리할 것인지를 정해놓은 로직(주어진 인풋으로 정의된 계산을 수행한 뒤 아웃풋을 내는 것을 말함)

알고리즘 공부방향

• 인풋 사이즈가 커질수록 Big O가 어떻게 변화하는지
• 시간 복잡도, 공간 복잡도 고려
• 어떤 자료구조를 이용하여 알고리즘을 작성하는 것이 좋을지
• 최종적으로 작은 공간과 빠른 시간안에 효율적으로 처리하는 알고리즘을 만드는 것이 목표

*

• 자동완성, 복붙 사용을 최소화할 것
• 알고리즘 풀이에 사용하는 언어를 이해하려고할 것
• 충분한 고민 & 문제에 대한 이해/풀이 아이디어, 어려웠던 점 및 해결책 생각할 것

알고리즘의 종류

탐색(Search)

• 선형 탐색(Linear Search)
• 이분(이진) 탐색(Binary Search)
  • https://im-developer.tistory.com/126
• 순차 탐색(Sequential Search)
• 해시 탐색(Hash Search)
  • 해시 테이블(Using Hash Tables)

정렬(Sorting)

• 버블 정렬(Bubble Sort)
• 선택 정렬(Selection Sort)
• 삽입 정렬(Insertion Sort)
• 퀵 정렬(Quick Sort)
• 병합 정렬(Merge Sort)
• 힙 정렬(Heap Sort)
• 기수 정렬(Radix Sort)
• 계수 정렬(Count Sort)

완전 탐색

• 브루트 포스(Brute Force)
• 비트 마스크(Bit Mask)
• 백트래킹
• 재귀함수
• 순열
• BFS(너비 우선 탐색) & DFS(깊이 우선 탐색)

분할 정복

동적 계획법(Dynamic Programming)

그리디(Greedy)

트리

• 이진 검색 트리(Binary Search Tree)

그래프

• 위상 정렬

최단 경로

• Floyd-Warshall
• 다익스트라(Dijkstra)
• Bellman-Ford

최소 신장 트리(MST, Minimum Spanning Tree)

• Kruskal
• Prim

기타

• 비트 연산
• 진수 변환
• 재귀(Recursion)
• 유클리드 호제법(최대공약수, 최소공배수)
• 투포인터(슬라이딩 윈도우)
• 조합, 순열
• 파라메트릭 서치
• 최장 증가 수열(LIS)
• 최소 공통 조상(LCA)
• 비트 마스크(BitMask)
• Matching Parenthesis problem
• Variables / Pointers manipulation
• reverse linked list(duplicates, removing duplicates)
• Custom data structures(Object oriented programming)

References

• bfs dfs
• 안경잡이 개발자
• js로 트리(bfs, dfs) 구현하기
• 알고리즘 풀 때 유용한 javascript 함수들