본문 바로가기

Algorithm/Data Structure

Algorithm/Data Structure 2018. 8. 4. [KOI] 1999년 중등부 1번 촌수계산 https://www.acmicpc.net/problem/2644 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include using namespace std;#define MAX_N 100 int N, M, start, finish;bool adj_matrix[MAX_N+1][MAX_N+1]; //MAX_N이 100이므로 인접행렬로 해결 가능 int solve() { queue q; vector visited(N+1, false); vector dist(N+1, -1); q.push(start); visited[start] = true; dist[start] = 0..
Algorithm/Data Structure 2018. 8. 3. [BOJ]1260 DFS와 BFS DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)의 구현 문제이다.단순 구현 문제이지만 대회를 준비하는 시점에서 MAX_N의 값이 클 때를 대비해 adjacency matrix(인접 행렬)이 아닌 adjacency list(인접 리스트)로 구현하였다. 두 탐색법 모두 구현방법은 비슷하지만 DFS는 탐색을 시작한 노드에서 이어진 제일 깊은 노드까지 탐색하다 보니 재귀적으로 구현하는 점이 다르다고 볼 수 있겠다. https://www.acmicpc.net/problem/1260 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869..
Algorithm/Data Structure 2018. 7. 31. KOI(한국정보올림피아드) 2000년 중등부 1번 장난감조립 https://www.acmicpc.net/problem/2637 #include #define MAX_N 100 using namespace std; int N, M; int a[MAX_N+1][MAX_N+1]; //인접 행렬 형태 int n[MAX_N+1]; //n[i] = 완제품 N을 만들기 위해 필요한 부품 i의 개수 bool not_leaf[MAX_N+1] = {false}; //not_leaf[i] = i가 기본부품이면 false, 아니면 true void solve(int i, int v) { n[i] += v; for(int j=1; j 0) // 부품 i가 j를 필요로 하면 solve(j,v*a[i][j]); } } int main() { scanf("%d %d", &N, &M); for..

티스토리툴바