1. Toy - 24일차
- Radix Sort 기수 정렬
비교연산을 하지 않으며, 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다
0~9의 Queue를 준비
각 1의 자리 수에 맞는 Queue에 데이터를 넣음, 0부터 다시 원래의 배열로..
다음 각 10의 자리 수에 맞는 Queue에 데이터를 넣음, 0부터 다시 원래의 배열로..
음수 << 계수 정렬이 필요
2. 자료구조 / 알고리즘
-
GCD/LCM(최대공약수 / 최소공배수)
-
순열 / 조합
순열, 순서를 생각하며 나열한다 ABC BCA ACB 등 순서가 다르면 다른 경우의 수
조합, ABC BCA ACB 등 순서가 다르더라도 같은 경우로 취급
-
멱집합, 모든 부분집합의 power set
-
DFS >> Stack
-
BFS >> Queue
-
DP
3. review
-
언어는 도구.. 생각과 논리를 세우는 것이 중요
=> 즉 언어 없이도 풀 수 있어야 함 -
문제를 푸는 순서
입력을 생각(크기, 공간 등..)
수도코드 1, 2, ... N
논리의 비약을 찾아낼 수 있고, 수도 코드의 논리를 세분화 -
시간 복잡도
O(1)
O(logN)
O(N)
O(logN*N)
O(N^2)
O(logN*N^2)
O(N^3)
5천만 ~ 1억 정도까지는 봐줌.. 그 이상은 다시 생각해보자(코딩테스트)
굳이 오버 엔지니어링 할 필요는 없음!
완전탐색(exhaustive search)
DFS, BFS 순열, 조합(부분집합) => 필수!
DFS, BFS => 그래프 류, 최단거리(다익스트라, 벨만포드, 플로이드 와샬) 등등 해결가능
바이너리서치, 다이나믹(메모리제이션), 정렬, 관점을 반대로 해석 => 요런 것도 잘 안다면 완벽
정렬은 사실 arr.sort()만 잘 쓰면 됨! 콜백주의, 최적화가 잘 되있음
졍렬은 논리 훈련을 위한 도구로 공부하기 좋음~
- 공간 복잡도
JS에서 데이터 1천만개는 80MB
ex) N = 1000 >> 이차원 행렬일 경우 1 000 000
N = 10000 >> 이차원 행렬로 푸면 1억개가 넘어감..
이차원 행렬로 풀면 안됨
조합 => pickOrNot 사용되거나 사용안되거나
직접 시행, 반복을 통한 패턴 습득이 중요함~
DP
복잡한 문제를 부분문제로 나누어 풀고, 부분 문제의 답을 저장해서 두 번 계산하지 않는다.
overlapping subproblems : 푼거 또 품
optimal substructure : 부분 문제의 해답을 합쳐, 전체 문제를 해결
50원이 목표다..
40원을 만드는 경우의 수는 몇개냐?
30원을 만드는 경우의 수는 몇개냐?
.
.
.
