전체 글 127

[C++] Prim MST 알고리즘(Greedy, priority queue활용) - 원더랜드

prim과 kruskal 둘 다 MST라서 구하고자하는 것은 같다. 하지만, kruskal : 간선 정렬, Union & Find 활용 prim : 인접리스트, priority queue활용 #include #include #include #include using namespace std; int ch[30]; struct Edge{ int e; int val; Edge(int a, int b){ e = a; val = b; } bool operator ref.val; } }; int main() { priority_queue Q; vector map[30]; //인접리스트 int i,n,m,a,b,c,res=0; scanf("%d %d",&n,&m); for(i = 1; i

[C++] Union&Find 자료구조 - 친구인가?

Union & Find는 서로소를 찾아내는 자료구조이다. #include using namespace std; int unf[1001];//1차원 배열의 트리형태 int Find(int v){ //v라는 학생의 집합번호를 리턴하는 역할 //결국 연결된 집합의 학생들은 루트번호학생의 번호가 집합번호가 되어 리턴함. if(v==unf[v]) return v; else return unf[v] = Find(unf[v]);//재귀적으로 루트의 집합번호를 찾아간다. } void Union(int a, int b){ a = Find(a); b = Find(b); if(a!=b) unf[a] = b;//서로 다른 집합에 있다. unf[1] = 2 : 1-2 연결 } int main() { int n,m,a,b; ci..

[C++] 이항계수(메모이제이션)

#include int dy[21][21]; //1. 0으로 초기화 돼있었는데 int DFS(int n, int r){ if(dy[n][r] > 0) return dy[n][r];//3. 곧바로 리턴한다(이미 구했다고 생각하고) if(n==r || r == 0) return 1; else return dy[n][r] = DFS(n-1,r-1)+DFS(n-1,r); //2. 값이 들어갔다면 //nCr = n-1Cr-1 + n-1Cr } int main() { int n,r; scanf("%d %d",&n,&r); printf("%d\n",DFS(n,r)); return 0; } 이항계수는 nCr = n-1Cr-1 + n-1Cr 이라는 공식이 성립된다. 그리고 nCr ( n== r)이거나 nC0인 경우 그 ..

[C++] priority_queue(힙 응용) - 최대 수입 스케쥴

#include #include #include #include using namespace std; struct Loc{ int money; int date; public: Loc(int money, int date){ this->money = money; this->date = date; } bool operatorref.date; } }; int main() { int N,M,D,i,datemax=-2147000000,sum=0; priority_queue pQ; vector vec; scanf("%d",&N); for(i=0; i datemax) datemax = D; } sort(vec.begin(), vec.end());//날짜로 정렬 완료 while(datemax != 0){ for(auto..

[C++] BFS - 송아지 찾기

최소, 최단거리는 BFS가 유리하다 #include #include #include #include #define MAX 10001 using namespace std; int main() { // 인접 리스트 안쓰고 푸는 방법임 int S,E; queue Q; scanf("%d %d",&S,&E); int dx[3] = {-1, 1, 5};//여러모로 굉장히 유용함 int ch[MAX] ={0}; //distance를 가짐 int x,i; int pos; ch[S] = 1; Q.push(S); while (!Q.empty()) { x = Q.front(); Q.pop(); for(i = 0; i < 3; i++){ pos = x + dx[i]; if(pos 10000) continue; if(pos =..