jmmm_25

1743번 음식물 피하기 문제는 DFS 알고리즘을 통해 인접한 가장 큰 음식물의 크기를 찾으면 된다.dfs를 이용하여 재귀 함수를 호출할 때 마다 cnt를 +1 해주면 된다. 이 문제같은 경우에는 (2,2) 좌표에서 DFS를 호출하여 상하좌우를 다 들어가본 후, 결과 값인 4를 리턴한다. # : TRASH , : EMPTY # . . . . # # . # # . . 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #define TRASH 1#define EMPTY 0#define MIN_INF (-98776321) using namespace std;int N, M, K;int map[10..

이 문제는 전에 풀었던 1012번 문제의 기본 개념이라고 보면 될 것 같다.말 그대로 연결 요소의 갯수를 구하면 되는 문제이다.DFS의 기본 개념만 알면 풀 수 있는 간단한 문제이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #include using namespace std; vector adj(1001);vector isVisited(1001);int N, M, ret; void dfs(int v) { isVisited[v] = true; for (int i=0; i N >> M; for (int i=0; i> u >> v; adj[u].push_b..

1012번 유기농 배추 문제는 배추 밭에 배추가 심어져 있는 모든 곳을 다 DFS로 탐색함으로써 답을 찾아낼 수 있다.dfs는 모든 노드들이 연결되어 있는 경우도 있지만, 그렇지 않은 경우도 있다.위의 문제 같은 경우에는 후자이다. 그래프 용어 중에 Component가 있다. Component 하나 안에 속한 정점들은 서로 모두 이어져 있으며, 다른 Component끼리는 이어져 있지 않다.따라서, 배추 밭의 Component의 갯수를 찾으면 된다. map[i][j] == true 인 곳이 배추가 심어져있는 곳이므로, 이 경우에만 dfs 탐색을 시작한다.dx, dy 배열을 이용하여 dfs 탐색을 시작한 해당 위치의 상하좌우를 돌아보며 재귀형식으로 dfs를 탐색한다.한 구역의 dfs 탐색이 끝났으면, 결과..

예시로 Lunch Box 문제 - 도시락 데우기 문제가 있음. 도시락1, 도시락2가 존재할 때, 데우는 시간은 C1, C2가 걸리고, 먹는 시간은 E1, E2 ( E1 >= E2)가 걸린다. 2번을 먼저 데운 후에, 1번을 데워 먹을 때 걸리는 시간—> C2 + C1 + max(E1, E2 - C1)2번 도시락을 먼저 데워서 먹게 되면 C1이 데워지는 시간 동안은 먹는 시간이 포함이 안되므로 E2 - C1이 된다.왜냐하면 C1이 데워지는 시간 보다 E2가 더 작다면, 데워지는 동안 E2는 끝나기 때문이다. 그래서 max 값은 E1이 된다. (E1 >= E2) 1번을 먼저 데운 후에, 2번을 데워 먹을 때 걸리는 시간.—> C1 + C2 + max(E2, E1 - C2) 2번을 데우는 시간에, E1의 먹는..

동전 0 문제는 그리디 알고리즘을 이용하여 해결한다.입력에 (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 이러한 조건이 있기 때문에 그리디 알고리즘이 성립한다. A1 = 1, A2는 A1의 배수, A3는 A2의 배수로 Aj의 값이 증가하기 때문이다.동전 0 문제는 어려운 문제는 아닌데, for 문의 초기값을 잘못 설정해주어, 런타임 에러가 발생하여 고생 좀 했다. 따라서, 매 순간 가장 큰 동전의 값을 이용하여 가장 큰 이익만을 찾으면 된다. 소스는 아래와 같다. 12345678910111213141516171819202122232425262728293031323334353637383940 #include using namespace std; int N,..

1234567891011121314151617181920212223242526272829#include int data[]={1,2,3,4};int flag[]={0,0,0,0}; void powerset(int n,int depth){ if(n==depth){ int i; printf("{"); for(i=0;i