CS/알고리즘

Merge Sort & Quick Sort (JAVA)

Merge Sort - best : $\ O(n \log{n})$ - avg : $\ O(n \log{n})$ - worst : $\ O(n \log{n})$ - out-of-place - stable public static void mergeSort(int[] arr, int low, int high) { if (high-low < 1) return; int mid = (low+high)/2; mergeSort(arr, low, mid); mergeSort(arr, mid+1, high); int[] tmp = new int[high-low+1]; int i = low, j = mid+1, idx = 0; while (i

LCS

LCS의 길이 구하기 두 문자열 A, B 가 있다고 하자. $X_i$ = A[0]...A[i] $Y_j$ = B[0]...B[j] 로 정의하자. d[i][j] 를 LCS($X_i$, $Y_j$)의 길이라고 하자. 먼저 다음과 같은 사실이 자명하게 성립한다. d[i-1][j-1] $\leq$ d[i-1][j] $\leq$ d[i][j] d[i-1][j-1] $\leq$ d[i][j-1] $\leq$ d[i][j] d[i-1][j-1], d[i-1][j], d[i][j-1], d[i][j] 에서 어떤 둘을 골라도 그 차이는 1 이하이다. 1. a[i] == b[j] 일 때, a[i] == b[j] 라는 사실과 별개로 d[i][j] = d[i-1][j-1] 혹은 d[i][j] = d[i-1][j-1] + 1 ..

그래프 사이클 관련 문제

기본적인 원리 일단 DFS로 푼다고만 생각하자. BFS로 될 수도 있는데 생각보다 어려움... parent list 만들어서 부모 노드를 기록한다. 부모 노드가 아닌데 방문했던 노드를 다시 방문하는 경우 사이클이 존재하는 것이다! 또, 사이클을 찾는 순간 y(사이클의 시작점), x(사이클의 끝점) 를 알게 된다! x부터 쭉 x = parent[x] 해주면서 cycle list에 넣어준다. y까지 넣고 나면 종료한다. 함수 자체는 사이클의 존재 여부를 반환하게 한다. 이러면 사이클을 저장한 뒤 True를 반환하고 이 함수를 호출했던 부모 함수가 계속 True를 반환해서 모든 프로세스가 거의 즉시 종료된다. 소스코드 cycle = [] check = [False]*(n+1) parent = [-1]*(n+1..

에라토스테네스의 체

def sieve(n): prime = [] isprime = [False, False] + [True]*(n+1) for i in range(2, n+1): if not isprime[i]: continue prime.append(i) isprime[2*i::i] = [False] * len(isprime[2*i::i]) return prime prime = sieve(4000000) print(prime[:20])