[Basic] 기본 알고리즘 정리노트

간단하게 정리한 알고리즘 기법 정리 노트입니다.

String

• Two pointers : 두 개의 피봇을 활용해 탐색하는 기법 (이중반복 -> 단일반복) / 배열
• Sliding window : 고정 길이 Two pointers, 시간 복잡도 최소화 / 해쉬맵과 함께 활용
• Prefix sum : 일종의 전처리 기법
• Rabin Karp algoritm : 라빈 카프 알고리즘, 긴 스트링을 해싱하여 연산량을 축소
  • e.g.) 0번째문자ASCII * 2^2 + 1번째 문자 ASCII * 2^1 + 2번째 문자 ASCII * 2^0

 

Search

• BFS :  graph, visitied, queue 활용
• DFS : recursion
• Backtracking : DFS를 주요 활용하나 탐색 도중 조건에 부합하지 않는 경우를 제외한 탐색
• Dijkstra : heap
• Binary search : 탐색 마다 1/2 로 탐색량 감소

 

문제를 푸는 단계

1. 문제 상황을 명확하게 이해한다.

당연한 걸 가지고 그러냐고 할 수 있지만 의외로 잘 못 이해하고 문제 풀이를 시도하는 경우가 많음. 또한 제약 조건을 반드시 볼 것.

 

2. 문제를 인간의 입장에서 풀어본다.

내가 머리로 못 푸는 것은 당연히 내가 코드로 구현할 수 없다.  그림을 그려가면서 내가 직접 풀어본다.

 

3. 내가 머리로 푼 방식을 알고리즘으로 적용한다.

내가 머리로 푼 방식과 가장 유사한 모든 알고리즘 기법들을 적용해본다. 문제의 특징과 규칙을 짚어내야 한다. 해당 알고리즘의 일관성을 문제 솔루션으로 적용시킬 수 있는 지 논리적으로 판단해야 한다.

머리로는 풀 수 있지만 알고리즘으로 표현하기 어려운 문제면 DP 문제일 가능성이 큽니다.

 

4. 다른 방법을 시도해본다.

문제가 안풀리거나, TLE 걸리는 경우 다른 방법을 고민한다. 기존 풀이에 집착하지 않는 것이 핵심. TLE 걸리면 알고리즘 기법을 바꾸어야 한다. O(logN) 은 이진탐색, O(N) 은 투 포인터 등의 기법이 있음을 기억하고..