코딩성장스토리

오랜만에 문제를 풀다가 헷갈리는 부분들이 있어서 정리를 해본다.. 최소 스패팅 트리 모든 노드에서 가중치 합이 가장 작은 트리를 만드는 것 크루스칼 vs 프림 크루스칼 알고리즘 간선의 길이가 짧은 것 부터 시작해서 사이클이 생기지 않게 간선을 추가하는 방식 프림 알고리즘 한 시작 노드를 정한 후에 노드에 연결된 간선 중 최소 값을 선택하여 확장해나가는 방식 크루스칼 알고리즘 구현 // 유니온 파인트도 사이클 체크 int findparent(int x){ if(x==findparent(parent[x])){ return x; }else{ return parent[x]=findparent(parent[x]); } } void uni(int x,int y){ x=findparent(x); y=findparen..

유니온 파인드 두 노드가 같은 그래프에 있는지 찾는 방법 그래프 알고리즘의 일종으로서 상호 배타적 집합, Disjoint-set Find -노드 x 가 어느 집합에 포함되어 있는지 찾는 연산 Union-노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산 parent[i]는 i의 부모가 무엇인지 나타내는 것, parent[i] =i 는 i가 루트 노드임을 나타냄(부모가 본인이므로) find함수 구현 int find(int x){ if (x==parent[x]){ return x; } else { return find[parent[x]]; } } 루트를 찾아 반환 하지만 이 함수의 문제점은 한쪽방향으로 치우칠 수 있다.(트리의 장점 소실) 이를 고치기 위해 오른쪽노드를 모두 루트노드에 연결하게 구..

1.나머지 연산 (a+b)%c=((a%c)+(b%c))%c (a*b)%c=((a%c)*(b%c))%c (a-b)%c=((a%c)-(b%c)+c)%c → 뺼셈의 경우 음수가 될 수 있기에 +c를 해줘야한다. 나누기 연산은 불가능 증명) a=q1c+r1 a+b=(q1+q2)c+(r1+r2) → (a+b)%c =(r1+r2)%c b=q2c+r2 a%c=r1 b%c=r2 →a%c+b%c =r1+r2 이고 여기서 c를 나누면 (r1+r2)%c 이다 2.최대공약수(GCD) 유클리드 호제법 a를 b로 나눈 나머지를 r일떄 GCD(a,b)=GCD(b,r) 이다 재귀함수를 이용한 유클리드 호제법 int gcd(int a,int b){ if(b==0){ return 0; }else{ return gcd(b,a%b); } ..