계수정렬(counting sort)를 이용한 기수 별로 비교없이 수행하는 정렬 알고리즘. 비교연산을 하지 않아서 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블만한 메모리가 더 필요하다. 가장 작은 자리수부터 비교하는 방법을 LSD(Least-Significant-Digit)라고 하고. 가장 큰 자리수부터 비교하는 방법은 MSD(Most-Significant-Digit)라고 한다. LSD예시 lists=[127, 564, 3218, 89, 524, 6, 72, 103, 1216] 먼저 1의 자리 비교 각각 1의자리는 7 4 8 9 4 6 2 3 6 이므로 [72], [103], [564, 524], [6, 1216], [127], [3218], [89] 이다. 동일한 방법으로 10의자리를 기준으로 ..

유클리드 호제법을 이용해서 최대공약수 구해본다 파이썬코드 x와 y의 최대공약수 구하는 함수. 이 함수를 이용해서 최소공배수도 간단하게 구할 수 있다. # 최대공약수 def gcd(x,y): while y: x,y=y,x%y return x # 최소공배수 def lcm(x,y): res=(x*y)//gcd(x,y) return res

이분 매칭 - 왼쪽 노드가 오른쪽 노드를 효과적(최대 매칭)으로 선택하는 방법 #include #include #define MAX 101 using namespace std; vector a[MAX]; int d[MAX]; bool c[MAX]; int n = 3; int m; // 매칭에 성공한 경우 True, 실패한 경우 False bool dfs(int x) { // 연결된 모든 노드에 대해 들어갈 수 있는지 시도 for (int i = 0; i < a[x].size(); i++) { int t = a[x][i]; // 이미 처리한 노드는 더 이상 볼 필요 없음 if (c[t]) continue; c[t] = true; // 비어있거나 점유 노드에 더 들어갈 공간이 있는 경우 if (d[t] ==..

- 피보나치 수 F(0) = 0, F(1) = 1 일 때, F(n) = F(n-1) + F(n-2) 피사노 주기: 피보나치 수를 어떤 수 K로 나눈 나머지는 항상 주기를 가지게 되는데 이를 피사노 주기라 한다. 주기의 길이가 P이면, N번째 피보나치 수를 M으로 나눈 나머지는 (N%P)번째 피보나치 수를 M으로 나눈 나머지와 같다. 피사노주기 파이썬 코드 import sys MOD=1000000 PERIOD=int(15*(MOD/10)) def fib_pisano(n): temp=[0]*(PERIOD+1) temp[0]=0 temp[1]=1 for i in range(2,PERIOD): temp[i]=temp[i-1]+temp[i-2] temp[i]%=MOD return temp[n%PERIOD] n=i..

1부터 6까지 흘려보낼수 있는 최대 유량 구하기 #include #include #include #define MAX 100 #define INF 100000000 using namespace std; int n = 6, result; int c[MAX][MAX], f[MAX][MAX], d[MAX]; vector a[MAX]; void maxFlow(int start, int end) { while (1) { fill(d, d + MAX, -1); queueq; q.push(start); while (!q.empty()) { int x = q.front(); q.pop(); for (int i = 0; i < a[x].size(); i++) { int y = a[x][i]; // 방문 하지 않은 노드 ..

# strongly connected component def scc(g,v): finished=[False]*(v+1) label=[0] # 누적 라벨 : 노드를 한번 방문 할때마다 1씩 증가 labels=[0]*(v+1) # 고유 라벨 저장 ans,s=[],[] def _scc(u): label[0]+=1 parent=labels[u]=label[0] s.append(u) for v in g[u]: if not labels[v]: parent=min(parent,_scc(v)) elif not finished[v]: # 방문 했었으나 scc처리가 아직 안된 노드 = 사이클 parent=min(parent,labels[v]) if parent==labels[u]: # 자기 자신이 사이클 중 가장 먼저 ..