[알고리즘] 고오급 알고리즘 키워드

 

*블로그 주인만 알아볼 수 있음 주의*

 

 

 

 

• 삼진탐색으로 최솟값 찾기

함수의 최솟값이 x구간 [a,d] 구간 안에 있다고 하자. 구간을 같은 길이 [a,b], [b,c], [c,d]로 나누고 f(b)>f(c)가 성립함을 보인다. (미분)

• 합 최소화

abs(a1-x)+abs(a2-x)+ ... +abs(an-x) 의 최솟값으로 만드는 x의 최적해는 중앙값이다. 배열 원소가 짝수개라면 두 중앙값 사이 모든 값이 최적해가 된다.

• 트리의 지름

임의의 노드 a 선택, a에서 가장 먼 노드 b, b에서 가장 먼 노드 c를 구하면 b-c가 트리의 지름

• 트리 k번째 조상 찾기

ancestor(n,k) : n번 노드의 k번째 부모

가장 쉬운 방법은 k번 거슬러 올라가는 것인데 비효율적이다.

k가 2의 거듭제곱인 모든 경우에 대해 계산하는 것 → O(NlogN)

ancestor(n,k) 찾기 k를 2의 거듭제곱 합으로 표현하여 계산 → O(logK)

• 트리순회배열(Tree Traversao Array)

루트 노드에서 깊이 우선 탐색으로 방문하는 순서대로 담은 배열. 트리의 각 서브트리는 트리순회배열의 부분배열에 대응된다는 성질을 갖는다. 부분 배열의 첫 번째 원소가 그 서브트리의 루트 노드가 된다. 

서브트리의 크기를 저장하는 배열을 이용하면 서브트리를 쉽게 구할 수 있다.

• 최소 공통 조상(Lowest Common Ancestor)

1. 두 개의 노드의 높이를 똑같이 맞추고 한 단계씩 올리면서 탐색하는 방법

2. 오일러 투어 트리 방법 (확장된 트리순회배열 기반)

확장된 TTA : DFS를 수행하면서 이미 방문한 노드를 지나는 순간도 모두 배열에 추가한다.

각 노드의 깊이를 같이 저장한 확장된 TTA를 이용하면, 노드 [a,b] 사이 최소가 되는 깊이인 노드가 최소 공통 조상이 된다.

• 유클리드 알고리즘
  • 최대공약수 (GCD)
  • 최소공배수 (LCM)
    lcm(a,b) = a*b / gcd(a,b)
  • 확장 유클리드 알고리즘
    ax+by = gcd(a,b)의 해를 구할 수 있음.

• 오일러 정리

두 수 a,b에 대해 gcd(a,b)=1을 만족할 경우 서로소라고 부른다. 오일러피 함수는 1부터 N이하의 정수 중 N과 서로소인 정수 개수를 나타내는 함수이다. (이때 ∏는 수열의 곱 연산 기호. 중복순열의 그 파이 아님)

p^r은 n의 소인수

• 나머지 연산의 곱셈 역원(modular multiplicative inverse)

페르마 소정리 이용

 

• 방정식 풀기
  • 디오판토스 방정식
    디오판토스 방정식 : ax+by=c 형태의 방정식을 말한다.
    디오판토스 방정식의 해가 존재하는 경우 ⇔ c가 gcd(a,b)로 나누어 떨어지는 경우 
  • 중국인의 나머지 정리

디오판토스 방정식 해

• 카탈란 수

여는 괄호 n개, 닫는 괄호 n개로 만들 수 있는 올바른 괄호 문자열 개수를 카탈란 수라고 한다. Cn(C와 밑수n) 으로 표기한다. 올바른 괄호 문자열은 (1. 빈 문자열은 올바른 괄호 문자열이다) (2. A가 올바른 괄호 문자열이면 "(A)"도 올바른 괄호 문자열이다) (3. A와 B가 올바른 괄호 문자열이면 AB도 올바른 괄호 문자열이다) 규칙을 갖는다.

특정 트리 구조의 개수를 셀 때도 카탈란 수를 이용할 수 있다.

 

• 교란순열

{1, 2, ..., n} 에 대해 어떤 i도 위치 i에 있지 않는 순열을 교란순열이라고 한다.

 

• 게임이론

두 플레이어가 번갈아 가며 게임을 진행하고, 플레이어가 택할 수 있는 움직임이 둘 중 어느 플레이어의 차례인지와 상관없이 사전에 동일하게 정해져 있으며, 무작위적인 요소가 없는 게임일 때, 상대방이 어떤 움직임을 택하더라도 항상 이길 수 있는 전략이 있는 경우를 찾는 것이 목표인 알고리즘 (님게임, 스프라그-그룬디 정리)

 

• mo's 알고리즘

정적 배열에 대한 구간 질의의 집합을 처리하는 알고리즘이다. 처리해야 할 질의는 구간 [a,b]에 속하는 배열 원소들을 이용하여 어떤 값을 계산하라는 형태이다. 정적 배열이기 때문에 질의를 어떤 순서로 처리해도 무방하며, 모 알고리즘은 특정한 순서로 질의를 처리하는 트릭을 사용함으로써 효율적으로 동작한다.

 

• 2차원 세그먼트 트리

2차원 배열의 사각형 형태의 부분 배열에 대한 질의를 처리하기 위한 자료구조이다.

1. 배열의 열을 기준으로 구간 트리를 만든다.

2. 노드마다 행을 기준으로 하는 구간 트리를 저장한다.

O( (logN)^2 )시간에 처리하고, 메모리는 O(N^2)이다.

• 느리게 갱신되는 세그먼트 트리

구간 트리의 갱신을 뒤로 미루는 방법을 이용하면, 구간 단위 갱신과 구간 질의를 모두 O(logN) 시간에 처리하는 구간 트리를 만들 수 있다. 

• 희소배열

전체 인덱스를 나타내는 구간 [0, n]은 넓지만 대부분의 배열 원소가 0인 경우를 의미한다.

• 트립 Treap

어떤 배열의 내용을 저장하고 있는 이진트리이다. 배열을 두 배열로 분할하거나, 두 배열을 하나로 병합하는 연산을 효율적으로 처리한다.

 

 

 

 

수식 변환 사이트

http://www.sciweavers.org/free-online-latex-equation-editor