Algorithm

최소 공통 조상(Lowest Common Ancestor, LCA)을 찾는 세 알고리즘

☝️ 서울대학교 권오남 교수님의 [정수론] 강의를 편집한 내용입니다. (링크 클릭 후 가입 시 수강 가능함) 문제 발생 시 삭제될 수 있습니다. [1] Divisibility, Congruence (1-1) 정의 Divisibility (가분성. 나눌 수 있음)

수염이 멋있어요

CCW 알고리즘

CCW를 이용해 풀 수 있는 대표적인 문제에는 두 선분의 교차 판정이 있다.

평면 상의 볼록 껍질은 여러 점들의 집합이 주어졌을 때, 이 집합의 일부만을 꼭짓점으로 가지면서 모든 점들을 감싸는 볼록 다각형의 꼭짓점 집합 중 가장 작은 것을 말한다.

폴라드 로 알고리즘은 1974년 폴라드가 만들어 낸, 합성수의 인수를 찾는 알고리즘이다.

소수를 판별하는 문제는 오랫동안 수학자들의 관심을 끌어온 문제지만 어렵다.

점수가 복사가 되는 세그먼트 트리

세그먼트 트리의 구간 갱신이 상당히 느리게 이루어짐을 봤다. 지연 전파(lazy propagation)는 이러한 문제를 해결하기 위해 쓰이는 알고리즘으로, 구간 갱신이 O(logN)의 시간에 이뤄질 수 있도록 한다.

니가 빠르면 얼마나 빠른데

넘쳐 흘러

돌고 돌아

호이가 계속되면 둘리인 줄 안다.

내 기쁨은 너가 벤틀리를 푸는 거야

BFS로 증가 경로 찾기

디닉 알고리즘(디닉 아님)

今有物，不知其數。三三數之，賸二；五五數之，賸三；七七數之，賸二。問物幾何？

시간이 지나도 변치 않는 것들이 있다.