OneMoreEnergyDrink OneMoreEnergyDrink

유클리드 호제법유클리드 호제법은 두 수 A,B의 최대공약수를 구하는 알고리즘이다.  방법A=0이면 GCD(0,B)=B이므로 GCD(A,B)=B이고 멈춤.B=0이면 GCD(A,0)=A이므로 GCD(A,B)=A이고 멈. A를 A = B⋅Q + R의 형식으로 씀. (Q는 A를 B로 나눈 몫.)GCD(A,B) = GCD(B,A-B)이므로 유클리드 호제법을 이용하여 GCD(B,A-B)를 찾음. 예시:270과 192의 최대공약수 - GCD(270,192)GCD(270,192) - 270과 192의 최대공약수 찾기A=270, B=192A ≠ 0B ≠ 0270 = 192 * 1 +78GCD(270,192)=GCD(192,78) - 이기 때문에 192와 78의 최대공약수 찾기A=192, B=78A ≠0B ≠0192 =..

CCW 알고리즘: 3개의 점 A, B, C가  있을 때 이 점 3개를 이은 직선의 방향을 알고자 할 때 유용한 기하 알고리즘. 위 알고리즘을 사용하면 선분 AB에 대해 점 C가 선분의 왼쪽에 있는지 오른쪽에 있는지 판단할 수 있다.다른말로 표현하면 시계방향을 그리는지 반시계 방향을 그리는지 알 수 있다. 세 점 A(x1, y1), B(x2, y2), C(x3, y3)이 주어졌을 때두 벡터 (x2-x1, y2-y1), (x3-x1, y3-y1)의 외적의 부호가 방향을 결정한다. 일반화한 외적의 식은 다음과 같다: (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1) 시계, 반시계, 직선 총 3가지 경우가 존재할 수 있음.시계: -1, 직선: 0, 반시계: 1int ccw(int x1, int y1,..

부분 합:A[n]배열이 있을 때, a,b (0A[a]~A[b]까지 더하는 문제. 1. Brute-force1. 순회하여 부분 합을 구한다. 전처리: x시간복잡도: O(n) 2. O(n) 전처리, O(sqrt(n)) 질의1. 배열 A를 sqrt(n)개의 원소씩 그룹으로 묶음2. 각각의 합을 구함3. a, b가 주어지면 양 끝부분의 합만 직접 구하고 중간 부분은 미리 구한 합을 더해줌  전처리: O(n)시간복잡도: O(sqrt(n))    전처리 후 sqrt(n)개의 그룹,    worst case: a=1, b=n-1    중간 값을 처리하는 시간복잡도: sqrt(n)-2 (총 그룹의 수-양 끝의 2그룹)    양 끝 값을 처리하는 시간복잡도: 2sqrt(n) (양 그룹의 원소의 수)    총 시간 복잡도..

RMQ(Range Minimum Query): (query란 단어의 뜻은 문의하다, 질문하다) 참고자료 숫자가 n개 있는 배열이 하나 있고, 해결해야 하는 (l,r)의 쿼리가 q개 들어오는 상황 기준 1. Brute Force q(l,r)일 때 l부터 r까지 전부 훑어서 RMQ를 찾음. 전처리: x 시간 복잡도: O(n) 업데이트: O(n) 직관적이고 쉬움, 배열의 값을 업데이트하는 것이 자유로움. 2. 미리 전부 전처리 전처리로 테이블을 미리 만들어 놓고 테이블에서 가져옴 전처리: O(n^2) 시간복잡도: O(1) 업데이트: O(n^2) 시간복잡도가 낮으나 전처리가 길고, 배열의 값을 하나만 바꿔도 테이블을 O(n^2)을 들여 만들어야 함 3. Sqrt Decomposition root(n)개로 n을 ..