one Book a Day

1번은 재귀 분할정복이고 2번은 반복문 분할 정복이다. 1번 def power(n, p): if p == 0: return 1 # Call this only once, instead of two times. power_p_divided_by_2 = power(n, p // 2) if p % 2: return n * power_p_divided_by_2 * power_p_divided_by_2 else: return power_p_divided_by_2 * power_p_divided_by_2 2번 def power(a, n): ret = 1 while n > 0: if n % 2 != 0: ret *= a a *= a n //= 2 return ret

Cut Vertex ( 절단점 찾기 ) Cut Vertex(절단점) 그래프의 절단점이란 해당 정점을 삭제했을 때 그래프가 두 개 이상의 그래프로 나누어 지는 점을 말합니다. 이 때 그래프는 항상 undirected graph입니다. 1) 직관적으로 절단점을 찾는 방법을 생각해 봅시다. (러프한 방법. 직접 삭제해본다. 섬나누기 or 연구소 같은 방법.) 느낌상 모든 정점에 대해 그 정점을 삭제한 후의 그래프를 먼저 따로 구합니다. 그 다음 DFS 혹은 BFS 로 몇 번만에 전체 그래프를 cover할 수 있는지를 보면 될 것 같습니다. 그러나 이 방식은 각 정점마다 알고리즘을 돌려야 하니 정점이 많아 질수록 매우 불리해 집니다. 2) 무향그래프의 DFS Spanning tree를 보면 cross edge가..

강한 연결 요소(SCC) 무향 그래프에서 절단점이 존재하지 않는 그래프를 우리는 Biconnected component라고 부릅니다. 절단점이 없다면 그래프 상의 어떤 점을 삭제하더라도 임의의 두 정점은 서로로 가는 경로가 존재하게 됩니다. Biconnected Component Undirected Graph에서 절단점이 존재하지 않는 그래프 Strongly Connected Component 만약 그래프의 임의의 한 정점에 대해 다른 모든 정점으로 가는 경로가 존재한다면 그 그래프를 SCC(Strongly Connected Component)라고 한다. SCC(Strongly Connected Component)특징 같은 SCC내에서 뽑은 임의의 U, V 점에서 U->V 혹은 V->U의 경로(직/간접적..

Manacher's 알고리즘 : 펠린드롬 탐색. 문자열에서 i번째 문자를 중심으로 하는 가장 긴 팰린드롬 길이를 반지름 r을 저장해 사용한다. O(N)에 다끝나버린다. ## 동작방식 i는 배열의 길이만큼 진행된다. 짝수 팰린드롬 경우 #으로 패딩을 주어 진행한다.(강제로 홀수만듬) aa -> #a#a# a 배열에는 해당 인덱스를 중심으로 한느 가장 긴 팰린드롬의 길이를 저장한다. 반지름 길이를 저장한느 것이지만 #으로 확장 시켰으므로 전체 길이가 된다. r, c변수 r : 해당 인덱스까지 가장 긴 팰린드롬의 우측 끝 c: 해당 인덱스까지 가장 긴 팰린드롬이 중심 인덱스 팰린드롬이라고 정해져 있는 인덱스에 속해 있는지 검사하며 a[i]값을 초기화한다. #b#a#n#a#n#a# -> a의 경우 이미 ..

고지식한 매칭 text = 'ABABCA' for i in range(len(text)-len(target)): for j in range(len(target)): if text[i+j] == target[j]: j+=1 else: break print('Identified') break KMP 알고리즘.(시작위치 후보를 잡아놓자) 불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행. 패턴을 전처리하여 배열 next[M]을 구해서 잘못된 시작을 최소화함. next[M]: 불일치가 발생했을 경우 이동할 다음 위치 패턴내에서 반복하는 구간이 있을것이라는 전제.. 하지만 없다면 무의미. 하지만 패턴이 길다는 전..

투포인터는 연속 구간의 길이가 가변적으로 변할 때 O(2*N)으로 풀도록 도와줌. 슬라이딩 윈도우는 구간의 크기가 고정일때. 둘다 start, end 포인트 사용(슬라이딩 윈도우는 end가 그냥 배열 포인터긴 함.) 하지만 둘다 연속적인 값들을 이용해 풀어나가는 한계가 있음. 기존 배열의 구간합 구하는 코드 배열 크기에서 구간의 길이k만큼의 모든 배열의 합을 순회하며 계산. import sys def max_sub_array(arr, k): maxsum = -sys.maxsize - 1 arraysize = len(arr) for i in range(arraysize - k + 1): current_sum = 0 for j in range(i, i + k): current_sum += arr[j] max..

LCA(lowest common ancestor)최소 공통 조상 모든 노드에 대한 깊이(depth)를 계산합니다. LCA를 찾을 두 노드를 확인합니다. depth가 동일하도록 거슬러 올라갑니다. 이후 부모가 같아질때까지 반복적으로 두 노드의 depth를 낮춥니다. 모든 LCA(a,b)연산에 대해 2번의 과정을 반복합니다. 느린 탐색 import sys sys.setrecursion(int(1e5)) # 각 노드의 depth를 찾아 기록하기 위한 dfs def find_depth(cur_node, depth): check[cur_node] = True depth[cur_node] = depth for next_node in graph[x]: if not check[next_node]: parent[next..

배열 회전 알고리즘. 노가다 회전 def rotate(key, N): def getNewValue(i, j, x, y): key[j , N-i-1] = key[i ,j] if (i == x and j == y): return getNewValue(N-j-1, i, x, y) for i in range(0, int(N/2)): for j in range(i, N-i-1): print(i,j ) tmp = key[i,j] getNewValue(N-1-j, i, i, j) key[j, N-1-i] = tmp ZIP을 사용한 깔끔한 회전 def zip_rotate(original): rotated = np.array(list(zip(*original[::-1]))) return rotated numpy를 이용해..

펜윅 트리(바이너리 인덱스 트리) 시간복잡도 O(MlogN) 구간합, 값 업데이트O(logN) 그림1. 세그먼트 트리 그림2. 펜윅 트리 Fenwick Tree를 구현하려면 어떤 수 X를 이진수로 나타냈을 때 마지막 1의 위치를 알아야 합니다. 마지막 1이 나타내는 값을 L[i]라고 표기하면 L[3]은 11(2)로 1, L(10)은 1010(2)로 2 가 됩니다. 수 N개를 A[1] ~ A[N] 이라고 했을 때, Tree[i]는 A[i] 부터 앞으로 L[i] 개의 합이 저장되어 있습니다. 아래 그림은 각각의 i에 대해서, L[i]를 나타낸 표입니다. 아래 초록 네모는 i부터 앞으로 L[i]개가 나타내는 구간입니다. L[i] = i & -i가 됩니다. 그 이유는 아래와 같습니다. -num = ~num + ..

백준님의 블로그내용으로 공부한 것을 정리한 포스팅입니다. 세그먼트 트리.(Segment Tree) Intro 구간 l,r 이 주어졋을 때 A[l]~A[r]까지의 합 i 번재 수를 v로 바꾸기 A[i] = v 수행해야 하는 연산은 최대 M번. 1번연산하는데 O(N) 2번연산 O(1) 총 시간복잡고 O(MN) 2번 연산이 없다고 가정해봅시다. 수를 바꾸는 경우가 없기 때문에 합도 변하지 않습니다. 따라서 앞에서부터 차례대로 합을 구해놓는 방식으로 문제를 풀 수 있습니다. S[i] = A[1]+...+A[i] i~j까지 합은 S[j]-S[i-1] S[0] = A[0] for i in range(N): S[i] = S[i-1] + A[i] 여기서 2번연산을 하려면 수가 바뀔때마다 S를 변경해줘야 합니다. 가장 ..