Readiz빠른 거듭제곱과 Modular Inverse
일반적으로 특정 수를 N 제곱하는데 걸리는 시간은 O(N) 이지만, 간단한 수학으로 이를 O(\log N)에 마칠 수 있다. 이는 거듭제곱 하고자 하는 수를 이진수로 보고, binary lifting 하는 것이라고 보면 된다.
기록
기록
개발 경험부터 알고리즘, 코드 조각과 생각까지. 배운 것을 기록하고 다시 꺼내 봅니다.
128개의 기록 중 41–50
연도별 모아보기 →최근 기록
AtCoder Beginner Contest 327
상당히 망했다. D는 문제 이해하는데 시간이 너무 오래 걸린 뒤로 graph로 변환하는 문제라는 감이 왔지만 풀이에 실패했고, E는 greedy하게 접근해봤는데 이게 아닌듯 하다. 업솔빙 필수.
기록
LCS
LCS는 Longest Common Subsequence의 약자로, 두 문자열에서 최대로 공통되는 부분 중 제일 긴 것을 찾는다. 알고리즘은 평범한 O(N^2) 인 대표 DP 유형이지만, 구현 난이도가 살짝 까다롭기 때문에, 정리해본다.
기록
Hash
hash에서 충돌 방지 정책은 중요하다. 가장 간단하게는 이미 사용중인 영역을 만났을 때 주소값을 +1 하는 Open Addressing의 Linear Probing 방식이 대표적이지만, 여기서는 Chaining 방식의 구현을 알아보겠다. Chaining 방식의 경우 값 삭제도 원할하게
기록
