Today I Learned

오늘은 기존에 봤던 코딩테스트 문제를 풀어보면서, 다른 사람들의 공부방법이나 팁을 찾아봤다.

구현 시간복잡도 팁

참고 영상 : 저세상 개발자

• 보통 1초 = 10의 8승 = 100,000,000 연산 1억번

1. n=20 범위
   O(n!) = 3,628,800 O(2^n) = 1,048,576
   어지간한 구현 가능

2. n =100 범위
   O(n^3) = 10^6
   삼중루프, 플로이드 워셜 가능

3. n = 1,000 범위
   O(n^2) = 10^6
   이중루프, 벨만포드 가능

4. n = 10,000 범위
   O(n) = 10000, O(nlogn) = 40000
   DP, 이분탐색, 다익스트라, 유니온파인드, 세그먼트 트리, 투포인터 가능

5. n=10^8 범위
   O(log n)= 8
   유클리드호제법 같은 수학적 기믹이 필요

코테 공부 팁

알고리즘 - 자료구조

기업 코테의 5분류 : 정렬 구현 탐색 DP 수학
구현 정렬 탐색이 비중이 제일 높으니 집중하자
기본자료구조 : 선형-배열,링크드리스트,스택,큐,힙 / 비선형-트리,그래프
심화자료구조
리스트(링크드, 더블링크드, 환형) / 스택(배열기반, 링크드리스트기반) / 큐(환형 큐, 링크드큐)
트리(이진트리, LCRS, 레드블랙) / 그래프(방향, 무방향) / 힙(배열기반, 링크드리스트기반)
그외 트라이, 레드블랙트리도 고급형으로 알면 좋다.

코테 유형 비율

구현>DFS+BFS>그리디>DP>정렬(보통 자료구조문제)>이진탐색>최단경로>그래프이론
앞에 5개 먼저 공부하자

필수 알고리즘

DFS / BFS - 최소 1문제 나온다. 가장 기본 (완전탐색)
이분탐색, 투포인터, 슬라이딩윈도우 (구간탐색) - 여기서도 자주 나온다
구현 or 수학 : 구간 내 누적합 구하기, 유클리드(최소공배수/최대공약수), 에라토스테네스의 체(소수 빠르게 구하기)

• DFS
  Recursion 재귀 쓰자!
  깊이로 쭉 들어갔다가 거꾸로 역연산을 할 수 있기때문에 재귀가 좋다.

• BFS
  묻지도따지지도 말고 무조건 큐!
  큐로 같은 레벨인 애들 다 집어넣고 하나씩 다 빼내서 순회
  그리고 다음 레벨인 애들 큐에 또 집어넣고 하나씩 빼면서 순회 반복
  하지만 방문 정보 저장을 해서 재방문을 회피해야한다.

선택 알고리즘

다익스트라, 플로이드와샬(최단거리 구하기니까 둘중 하나 알아야)
유니온파인드(같은 그룹인지 확인. 유니온파인드 로직만 알면 바로 풀린다)
Monotonic Stack(불규칙한 수 주어줄때 최소한의 오름차순/내림차순 개수)
Bitmask(적은 메모리로 최대 효율)
Trie(문자열 검색)
크루스칼, 프림(Minimum Spanning Tree) - 거의 안나오긴함