게임 개발 낙서장

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

모든 노드를 최소비용으로 방문하는 알고리즘으로, 간선을 정렬하는 방식 #include #include #include #include using namespace std; int unf[10001]; struct Edge{ int v1; int v2; int val; Edge(int a, int b, int c){ v1 = a; v2 = b; val = c; } bool operator

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..

#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인 경우 그 ..

#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..

최소, 최단거리는 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 =..

#include int map[21][21]; int N,M; int cnt = 0; int ch[30]; // 이게 없으면 cycle생김 //방문한 노드 체크를 해야함 void DFS(int v){ int i; if(v == N) { cnt++; }else{ for(i = 1; i

#include int data[10], tmp[10]; void divide(int lt, int rt){ int mid; int p1, p2, p3; if(lt < rt) { //나누기 mid = (lt+rt)/2; divide(lt, mid); divide(mid+1,rt); //합치기 p1 = lt; p2 = mid+1; p3 = lt; while(p1

#include #include using namespace std; int a[11]; int N,tot = 0; bool flag = false; void DFS(int L, int sum){//L이 곧 인덱스를 가리킴 if(sum > (tot/2)) return;// 이전 으로 if(flag == true) return; // 스택프레임 모조리 삭제 if(L == N+1){ if(sum == (tot-sum)) flag = true; } else{ DFS(L+1, sum+a[L]); DFS(L+1, sum); } } int main() { int i,tmp; scanf("%d",&N); for(i = 1; i

DFS는 일반적으로 모든 경우의 수를 일일히 확인해서 최상의 경우를 찾는 경우에서 쓰인다 #include int n, ch[11]; void DFS(int L){ int i; if(L==n+1){ for(i = 1; i