Archive for the ‘algo’ Category

선형 (binary, lbound, ubound)

2016/07/31

= binary
* (s+e)/2, A[]
start=0,end=6, match=7
binary(start,end,match){
while(e-s>=0){
m = (e+s)/2
if(A[m]==match){ return m+1; }
if(A[m]<match){ s = m+1; }
else{ e = m-1; }
}
}

= lower bound

start=0,end=e+1
lbound(start,end,match){
while(e-s>=0){
m = (s+e)/2
if(A[m]<match){ s = m+1 }
else{ e= m }
}
return e+1
}

= upper bound
start=0, end=e+1,match=7
ubound(start,end,match){
while(e-s>=0){
m = (e+s)/2
if(A[m]>match){ e = m }
else{ s = m+1}
}
return e+1
}

Advertisements

dfs 두더쥐

2016/07/31

graph[N][N], K, N
visited [N]

dfs(k){
for(i=1;i<=N;i++){
n = graph[k][i]
if(!visited[n] && n!=0 ){
visited[n] = true
dfs(n)
}
}
return
}

두더쥐
dfs_rat(a,b,c){
A[a][b] =c
if(safe(a+1,b) && A[a=1][b]==1) dfs_rat(a+1,b,c)
if(safe(a-1,b) && A[a-1][b]==1) dfs_rat(a-1,b,c)
if(safe(a,b+1) && A[a][b+1]==1) dfs_rat(a,b+1,c)
if(safe(a,b-1) && A[a][b-1]==1) dfs_rat(a,b-1,c)
}
boolean safe(a,b){
return a>=0 && a<N && b>=0 && b<N
}
for(i=0;i<N;i++){
for(j=0;j<N;j++){
if(A[i][j]==1){
cnt++;
dfs(i,j,cnt+1)
}

 

https://www.digitalculture.or.kr/koi/StudyOnline.do#

순열 perm

2016/07/30

배열수 N
순열로 조합할개수 K
시작 위치 depth=0

순열
1. 단계가 조합수에 다다르면,
1.2 출력후 리턴
2. 단계부터 배열수까지 방문
2.1 단계,방문점 배열값 변경
2.2 재귀호출 : 단계 증가
2.3 단계, 방문점 배열값 원복

perm(data,depth,N,K){
if (depth>=K){
print (data,K)
return
}
for (i=depth;i <N;i++){
swap (data, depth,i)
perm (data,depth+1,N,K)
swap (data,depth,i)
}
}

[study] 다익스트라 dijkstra

2016/07/28

다익스트라()
graph[][] : 0값이면 간선 없음.
V : 총 노드수
src : 시작 노드번호

1) init:
각 노드에 대한 시작 src 부터의 거리 ( 초기값 MAX/2) : dist[V]
노드 방문여부 (false) : visited[V]
시작노드 거리값 (0) : dist[src] = 0

2) loop : V-1 ( 시작src 는 제외하므로 dist=0)

2-1)가장 가까운 거리에 있는 node (이미 방문한 노드는 제외) : minimal dist[i] && !visited[i] -> idx = i

2-2) 그 노드를 방문처리함

2-3) 모든 거리에 대해 더 가까워지는 거리를 찾아 (이미 방문한 노드 제외, 간선이 있는 경우만) : dist[i] > dist[idx]+graph[idx][i]
값 대체

#########################################
int graph[][]

void dikstra(int src){
int V=9;//count
boolean visited[V]; // false
int dist[V]; Arrays.fill(dist,Max/2) : Max/2

dist[src]=0

for(0:V-1){
// get min node
distance=Max/2, nodeidx : -1
for(i:V){ if(!visited[i]&&distance>dist[i]){ distance=dist[i]; nodeidx = i } }

visited[nodeidx]=true

for(i:V){ if( !visited[i] && graph[idx][i]!=0 && dist[i]> dist[idx]+graph[idx][i]){ dist[i] = dist[idx]+graph[idx][i]}
}

Backtracking

2016/07/22

https://www.cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html