코린이의 기록

이번 포스팅은 인접 행렬과 visted을 통한 BFS Algorithm을 구현해본다. BFS는 DFS와 함께 공부 되는것이 좋으니 아래 DFS도 참고하도록 한다. 아래 DFS에서는 인접행렬에 대한 내용도 다룬다. BFS와 내용이 중복되니 이번 포스팅에서는 생략한다.http://soye0n.tistory.com/13?category=764669 Keywords- Vertex = Edge : 정점, 꼭 (0,1,2,3,4,5,6,7)를 의미한다. - 인접 행렬 : 그래프 이론에서, 인접행렬 (Adjacency Matrix)은 그래프에서 어느 꼭짓점(Vertex)들이 어느 변으로 연결되어 있는지를 나타내는 정사각형 행렬이다. - Visited : 어느 꼭짓점을(Vertex)방문 했는가에 대한 여부, flag같..

1. 알고리즘DP문제2. 전체 소스#include #include using namespace std; int main() { int arr[1001] = { 0, }; int num; int max; cin >> num; vector v(num); for (int i = 0; i > v[i]; } for (int i = 1; i arr[3] = 6 Case 1과 Case2, Case3 중에서 더 큰 값을 배열에 저장한다. arr[3] = 6 arr[4] = arr[0] + v[3]; arr[4] = arr[1] + v[2]; arr[4] = arr[2] + v[1]; arr[4] = arr[3] + v[0]; 4) 붕어빵 4개를 팔았을 때 Case 1 : 1개를 팔았을 때 + 3개를 더 팔면 된다 =>..

1. 알고리즘DP문제2. 전체 소스#include #include using namespace std; int main() { int arr[12] = { 0, }; int num; cin >> num; vector v(num); for (int i = 0; i > v[i]; } arr[0] = 1; for (int i = 1; i = 0) { arr[i] += arr[i - 1]; } if (i - 2 >= 0) { arr[i] += arr[i - 2]; } if (i - 3 >= 0) { arr[i] += arr[i - 3]; } } for (int i = 0; i

1. 알고리즘DP문제로, 2*n은 이전 타일 붙여 나아 가면서 개수를 구할 수 있는 방식이다. 즉 큰 것을 구하기 위해 작은 단위부터 더해 나아가는 방식.. 2. 전체 소스2*n 타일은 2*n-1 번째의타일에서 2*1의 타일을 붙이는 값 더하기 2*n-1번째의 타일에서 2*2와 2*1 타일을 붙이는 값을 더해서 구할 수 있다. arr를 선언하여 각 n번째 타일의 채운 가짓수를 저장한다.#include using namespace std; int arr[1001]; int main() { int n; cin >> n; arr[0] = 1; // n = 1일때 타일을 붙일 수 있는 개수 arr[1] = 3; // n = 2일때 타일을 붙일 수 있는 개수 for (int i = 2; i

1. 알고리즘- DP문제 - 이 문제는 BFS 알고리즘으로 풀 수 있는 문제이다. 즉, Queue를 사용하여 문제를 푼다.2. 전체 소스#include #include using namespace std; const int MAX = 1000000; int check[MAX+1]; int dist[MAX+1]; int main(){ int n; cin >> n; queue q; q.push(n); check[n] = true; dist[n] = 0; while(!q.empty()){ int now = q.front(); q.pop(); if(now == 1) break; if(now%3 == 0 && check[now/3] == false){ q.push(now/3); check[now/3] = true..

1. 알고리즘이 문제는 BFS 알고리즘으로 풀 수 있는 문제이다. 즉, Queue를 사용하여 문제를 푼다.2. 전체 소스#include #include using namespace std; //1697 const int MAX = 200000; int check[MAX+1]; // 탐색 시 해당 값을 이미 방문했는지의 여부를 확인하기위해 사용되는 배열 int dist[MAX+1]; // 트리의 깊이를 구하기 위하여 사용되는 배열 (몇번만에 찾는지 확인하기위함) int main() { int subin, sis; cin >> subin >> sis; queue q; q.push(subin); // 초기 값을 Queue에 넣어준다. check[subin] = 1; // 초기 값은 무조건 방문 여부를 true..

1. 알고리즘이 문제는 다음순열(Next permutation)을 이용하여 풀 수있는 문제이다. 2. 전체 소스#include #include #include using namespace std; int main() { vector arr; int num = 0; int result = 0; int min = 0; int cnt = 0; // minimum값을 처음 값으로 초기화 하기위해 사용된다. cnt가 0이면 처음 계산된 값을 min 값으로 초기화 해준다. int flag = 0; // 순열의 길을 더해가다가 다음 길로 갈 수 없는 길(행렬값이 0일 경우)이 나올 경우 이 flag를 true로 바꿔준다. cin >> num; arr.assign(num, vector(num)); vector road..

1. 알아두어야 할것이 문제는 다음순열(Next permutation)을 이용하여 풀 수있는 문제이다. 2. 전체 소스#include #include #include using namespace std; int gMax=0; int main(){ int num; int result; int sub; cin >> num; vector v(num); for(int i=0; i> v[i]; } // 우선 오름차순으로 정렬시켜준다 (selection sort를 사용하였다.) for(int i=0; i