Algorithm 기법 정리

공간 복잡도 O(1) 관련

 

Array Rotation Algorithm

참고 자료
https://www.geeksforgeeks.org/program-for-array-rotation-continued-reversal-algorithm/

관련 문제
https://yinq.tistory.com/239

💡 핵심 IDEA
1. 회전 시, 밀려나는 부분과 밀려나지 않는 부분으로 2개의 블럭으로 나눈다.
2. 각 블럭을 역순으로 만든다.
3. 그리고 전체 블럭을 역순으로 만든다.

 

 

Boyer-Moore 과반수 투표 알고리즘

참고 자료
https://sgc109.github.io/2020/11/30/boyer-moore-majority-vote-algorithm/

관련 문제
https://yinq.tistory.com/238

💡 핵심 IDEA
"과반수 요소의 등장 횟수가 나머지 요소들의 등장 횟수를 상쇄시키는 경우"를 이용한 것이다.

1. 배열을 순회하면서 동일한 수가 나오면 cnt+1 을 하고 다른 수가 나오면 cnt-1을 한다.
2. 특정 수의 cnt 가 0이 되면, cnt를 0으로 만든 수를 기준으로 삼은 뒤, cnt를 1로 갱신하고 1번을 다시 반복한다. 
3. 최종적으로 검색 기준이 되는 수의 역할을 하는 수가 과반수를 초과한 수이다.

 

 

Floyd 순환 찾기 알고리즘

참고 자료
https://snutiise.github.io/Floyd's-Cycle-Detection-Algorithm/

관련 문제
https://yinq.tistory.com/248

💡 핵심 IDEA

1. 속도가 다른 두개의 포인터를 루프에 진입시켰을 때, 사이클이라면 동일한 노드를 가리키는 점이 생긴다.