컴퓨터 - ACM ICPC
16/08/10 11:40(년/월/일 시:분)
graph
v=vertex정점
e=edge간선
인접행렬은 완전그래프일때나 쓰고,
아니면 시간복잡도, 공간복잡도 너무 커서 안쓴다. O(V^2)
linked list, cpp는 vector사용
시간복잡도 O(V+E)
dfs
vector edge[100001];
int is_gone[100001];
void dfs(int w){
int i;
is_gone[w]=1;
for(i=0;i
if(is_gone[edge[w][i]]) continue;
dfs(edge[w][i]);
}
}
* 최단경로 알고리듬 - 다익스트라
플로이드(dp를 이용)와 시간복잡도는 비슷한데 더 간단함
모든 v의 거리를 무한대로 설정하고,
시작점의 거리를 0으로 설정한다.
시작점에서 출발해서 가능한 다음 점들을 찾고,
각 간선의 weight들을 더해서 각 점들에 거리를 저장한다.
그 다음은, 가능한 다음 점들 중에서 가장 거리가 짧은 쪽으로 이동.
그래서 다음 점들을 찾아서 반복.
이렇게 끝까지 가면 됨
이때, 다음 점을 찾을때 for문을 돌면 O(V^2)이 되므로
min힙에 넣어놓고 써야 O(VlogE)로 줄어듬
struct xy{
int x,y;
bool operator<(const xy &a)const{
if(a.x
return 0;
}
}
priority_queueque;
또는
priority_queue>que;
* 최단경로 알고리듬 - 벨만 포드
다익스트라는 음수 간선을 처리 못함. 음수 사이클도 못잡아냄. 이건 가능.
시작점부터 간선을 1개 쓴 답, 2개 쓴 답.... i번째까지 찾기
O(VE)
* 최소신장트리 알고리듬(MST) - 크루스칼
간단함. 간선을 비용 순으로 정렬 후, 작은 순으로 그래프에 간선을 추가.
주의) 이전에 추가한 간선들과 사이클이 생기면 안됨.
사이클 체크를 어떡하나?
1) DFS로 찾기: 시작점에서 모든 경우를 따져봐서, 시작점으로 돌아오는지 확인 : 느림
2) union & find : 각각 그룹한 다음, 간선 이어진 것들을 union 시킴
#include
#include
#include
using namespace std;
struct xyz{
int x,y,z
}edge[400001];
bool sort_z(xyz a,xyz b){
if(a.z
else return 0;
}
int P[100001];
int find(int x){
int now=x;
while(1){
if(now==P[now]) break;
now
int main(){
int n,m;
int i;
scanf("%d%d',&n,&m);
for(i=0;i
BFS
#include
#include
using namespace std;
char M[1501][1501];
int X[4]={1,-1,0,0};
int Y[4]={0,0,1,-1};
int is_gone[1501][1501];
dequequex;
dequequey;
int main(){
int w,h;
int i,j;
int sx,sy,ex,ey;
int nowx,nowy;
scanf("%d%d",&w,&h);
for(i=0;i
for(j=0;j
scanf(" %c",&M[i][j]);
if(M[i][j]=='S')
{
sx=i;
sy=j;
}
if(M[i][j]=='E'){
ex=i;
ey=j;
}
}
}
quex.push_back(sx);
quey.push_back(sy);
is_gone[sx][sy]=1;
while(!quex.empty()){
nowx=quex.front();
nowy=quey.front();
quex.pop_front();
quey.pop_front();
for(i=0;i<4;i++){
if(nowx+X[i]<0||nowy+Y[i]<0||nowx+X[i]>=h||nowy+Y[i]>=w)
continue;
if(M[nowx+X[i]][nowy+Y[i]]=='X')
continue;
if(is_gone[nowx+X[i]][nowy+Y[i]])
continue;
is_gone[nowx+X[i]][nowy+Y[i]]=is_gone[nowx][nowy]+1;
quex.push_back(nowx+X[i]);
quey.push_back(nowy+Y[i]);
}
}
printf("%d",is_gone[ex][ey]==0?-1:is_gone[ex][ey]);
return 0;
}
DFS
#include
#include
using namespace std;
vectoredge[10000];
int cnt[10000];
bool is_gone[10000];
void dfs(int w){
int i;
is_gone[w]=1;
cnt[w]++;
for(i=0;i
if(is_gone[edge[w][i]])
continue;
dfs(edge[w][i]);
}
}
int main(){
int n,m,k;
int i;
int s,e;
scanf("%d%d",&n,&m,&k);
for(i=0;i
scanf("%d%d",&s,&e);
edge[s].push_back(e);
}
for(i=0;i
int x;
scanf("%d",&x);
for(j=1;j<=n;j++){
is_gone[j]=0;
}
dfs(x);
}
int ans=0;
for(i=1;i<=n;i++){
if(cnt[i]==k)
ans+=1;
}
return 0;
}
Kruskal
#include
#include
#include
using namespace std;
struct xyz{
int x,y,z;
}edge[400001];
bool sort_z(xyz a,xyz b){
if(a.z
return 1;
return 0;
}
int P[100001];
int C[100001];
int find(int x){
int now,ix;
int ret;
now=x;
while(1){
if(now==P[now])
break;
now=P[now];
}
ret=now;
now=x;
while(1){
if(now==P[now])
break;
ix=now;
now=P[now];
P[ix]=ret;
}
return ret;
}
int main(){
int n,m;
int i;
int s,e;
int ans;
scanf("%d%d",&n,&m);
for(i=0;i
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
}
sort(a,a+m,sort_z);
for(i=1;i<=n;i++){
P[i]=i;
C[i]=1;
}
for(i=0;i
s=find(a[i].x);
e=find(a[i].y);
if(s==e)
continue;
if(C[s]>C[e]){
P[e]=s;
C[s]+=C[e];
}
else{
P[s]=e;
C[e]+=C[s];
}
ans+=a[i].z;
}
printf("%d",ans);
return 0;
}
Priority Queue (Heap)
#include
#include
using namespace std;
struct xy{
int x,y;
bool operator <(const xy a)const{
if(a.x
return 1;
return 0;
}
}
//priority_queueque;
priority_queue>que;
int main(){
return 0;
}
그래프가 입력으로 주어지고, 거리를 묻는 문제. 단순합니다.
어떤 정점을 잡아서, DFS를 돌려서 각 정점마다의 거리를 저장.
트리 문제에서는 DFS를 써도 된다.
그럼 언제 DFS를 쓰면 안되나? 최단경로 구할때 쓰면 안됨.
cow party
N개의 vertex가 있고, 단방향 그래프가 주어지는데
모든 정점에 갔다가 와야 되는데 최단 경로를 구해야 함.
시작점이 x라고 하면
x에서부터 모든 정점에 최단 경로를 구하고,
그 다음 정점들에 대해 또 최단 경로를 구하면.... 다익스트라 최악의 경우 O(V^3) (priority queue 쓰면 VElogV)
다익스트라를 2N번 돌려야 함
어떻게 경우의 수를 줄이나?
일단 처음 x에서는 모든 정점을 가보는 건 맞는데 (이렇게 다익스트라를 1번 돌리고)
그 다음에, 간선의 시작점,끝점을 뒤집은 그래프를 또 하나 만들어서 다익스트라를 1번 돌리고
그렇게 되면 파티장에서 모든 정점에 대해 최단경로를 구할 수 있다.
갈때) ......
올때) ......
이 2개를 더하면 왕복 최단경로가 나온다.
다익스트라 2번만 돌려서 가능.
벨만 포드 알고리듬.
V-1 간선 이용한 최단거리 이걸 저장해놨다가
V 간선 이용한 최단거리 이거랑 비교해서, 값이 다른 것이 음수 사이클이 있는 것
그래프 사이클 끊기
중복은 없는데, 2개씩 교환해서 정렬하는데 최소 비용
비용=두 숫자의 합
먼저 정렬을 한다.
1 2 3 4 5 인덱스
3 1 2 8 7 (정렬전)
1 2 3 7 8 (정렬후)
그래프를 어떻게 보냐?
N개의 vertex에 대해 정렬전->정렬후로 간선 그림 (단, 자기로 가는 것은 안그림. 2->2 이런거)
1->3
2->1
3->2
4->5
5->4
이 그래프에 사이클이 모두 없어질때까지
자기 자신을 가리키도록 그래프 간선들을 서로 교환함
그럼 그래프 사이클 없앨때, 어느 것부터 교환해야 하나?
정렬전 값이 작은 것부터 바꿔야 최소가 나옴.
이걸 사이클 크기만큼 반복하면 너무 오래 걸림.
근데 생각해보면 이걸 다 안 돌아도 됨.
사이클 내를 정렬하는 최소비용=1. 사이클내 (전체 합 + 최소값 * (사이클 크기-2))
2. 만약 사이클 밖에 더 작은 값이 있을 경우, 이를 이용하여 더 비용이 적게 바꿀 수 있다.
사이클내 전체 합 + 최소값 + 배열 내 최소값*(사이클 크기+1) <--원래 자리로 돌려놔야 하니까
=min(1,2)
이러면 사이클을 안 풀어도 비용을 알 수 있음.
사이클이 어디 있는지 찾으면 됨.
LCA
트리의 공통 조상 찾는거
DP를 활용
d[i][j]=i의 위로 2^j의 부모
=d[d[i][j-1]][j-1]
1
4 3
2 5
1. 트리 구성, 깊이 메모
2. 1~n 순회 (LCA)
배열
바로 위 2번째 위
1 1 1
2 4 1
3 1 1
4 1 1
5 3 1
LCA 구하기
1. 높이 맞춰주기 (X,Y)
아까 메모해놨던 깊이를 참조
깊은 쪽을 얕은 쪽에 맞춘다.
어떻게 깊이를 얕게 만드나?
부모와 자식을 바꿈
배열을 보면
X
Y
정의
P[i][j]=ㅓ의 2^j번째 부모
P[X]
P[Y]
예를 들어
P[2]={4,1}
P[5]={3,1}
여기서 부모가 같아지는 시점을 이분탐색으로 찾는다.
for k=10..0
if P[x][k]<>P[y][k]
x=P[x][k]
y=P[y][k]
else
한칸 위로 올라가면 부모를 찾으면 됨
이렇게 찾은 x,y에 대해 LCA를 구하면 됨
이렇게 공통 부모를 찾으면, 부모의 깊이를 이용하여
x와 부모의 깊이차 + y와 부모의 깊이차 = x와 y의 깊이차
조금 더 어렵게 내면, 간선의 weight를 줄 수 있음.
1차원 dp를 쓰면 풀린다.
d[i]=i번째 날 출생한 아메바 마리 수
d[0]=1
d[x]= k=x-b ~ x-a, sum(d[k]) (%1000)
근데 문제는, 출생한 마리 수가 아니라 살아있는 마리 수임.
ans= k=N-d ~ N, sum(d[k])
근데 문제는, 이 sum을 naive하게 계산하면 느림.
prefix sum을 이용하면 빨라짐.
P[k]= i=0~k, sum[k]
이렇게 하면, d[]를 하나씩 채워나갈 때마다 P[]로 채워나갈 수 있음
d->....
P->....
그럼
d[x] = P[x-a] - P[x-b-1]
이렇게 x-b ~ x-a 구간의 합을 루프 안 돌고 한번에 구할 수 있다.
예를 들면
a=2
b=4 N=6
d=6
0 1 2 3 4 5 6
d 1 0 1 1 1 2 2
P 1 1 2 3 4 6 8
이 문제는 아이디어가 어렵지, 코딩은 쉽다.
[이전 목록]
[1][2][3][4][5][6][7][8]
[다음 목록]
|
|