요즘은 코딩테스트를 보면, 언어에 제한을 두는 경우가 있습니다.
- Front - JavaScript
- Machine Learning - python
- Server - Python, Java
python, Java, JS 로 문제 풀면서 정리해봅시다.
파이썬, 자바, 자바스크립트 3개의 언어로 풀었습니다.
리트코드의 경우 파이썬 알고리즘 인터뷰에 소개된 문제 위주로 진행했습니다.
-
앙방향 탐색
- 양방향 BFS
| 알고리즘 | 최선 | 평균 | 최악 | 공간 복잡도 | 안정 | 비고 |
|---|---|---|---|---|---|---|
| 버블소트 | O(n) | O(n^2) | O(n^2) | O(1) | O | iteration 마다 가장 큰 원소가 제일 뒤로 이동 |
| 삽입정렬 | O(n) | O(n^2) | O(n^2) | O(1) | O | 참조 지역성 높음 |
| 선택정렬 | O(n) | O(n^2) | O(n^2) | O(1) | X | |
| 퀵소트 | O(nlogn)) | O(nlogn) | O(n^2) | O(1) | X | 추가 메모리 사용 없음 |
| 병합정렬 | O(nlogn) | O(nlogn) | O(n^2) | O(n) | O | 추가 메모리 필요 |
| 팀소트 | O(n) | O(nlogn) | O(nlogn) | O(n) | O | insertion + quick |
| 계수정렬 | O(n+k) | O(n+k) | O(n+k) | O(k) | X |
1) 버블소트
2) 삽입정렬
3) 선택정렬
4) 퀵소트
5) 병합정렬
6) 계수정렬
| 수행 | 인접 리스트 | 인접 행령 | 인접 셋 |
|---|---|---|---|
| 노드 존재 여부 검사 | O(m) | O(1) | O(1) |
| 순회 | O(n) | O(m) | O(v) |
| 간선 추가 | O(1) | O(1) | O(1) |
| 간선 제거 | O(m) | O(1) | O(1) |
인접셋 문제(https://atcoder.jp/contests/abc278/tasks/abc278_c)
-
N-Queen
-
triplet - O(N^2)
-
LIS(가장 긴 증가하는 부분 수열) - O(NlogN)
-
LCS(가장 긴 공통 부분 수열) - O(nm)
-
Knap sack(배낭 문제) - O(nm)
문자열에서 중첩된 부분까지 정규표현식으로 찾기 - 전방탐색
정수형 범위 - 예시) 1) shift 연산 vs Math.pow, 2) not not vs Math.trunc