jmmm_25

이 문제 같은 경우에는 DFS 또는 BFS로 쉽게 풀리는 문제지만, 좌표를 이상하게 줘서 고생좀 한 문제이다.2차원 배열에 직사각형을 잘 넣을 수만 있다면 DFS의 횟수와 Component의 갯수를 출력하면 되는 문제이기에 단순하다. 2차원 배열에 직사각형을 넣지를 못해서 구글링을 했다.단순하게 생각하면 배열에 집어넣는 것도 간단한 것 같다.좌표가 이렇게 주어지고 map을 만들어본 적이 없어서 당황했지만, 이런 스킬도 알아놓으면 편할 것 같다. for (int i=0; i> x1 >> y1 >> x2 >> y2; for (int x = y2-1; x>=y1; x--) { for (int y = x2-1; y>=x1; y--) { map[x][y] = 1; } } } 이 외에 나머지는 지금까지 풀었던 문제..

2331번 반복수열 문제는 1차원적으로 단순하게 풀었다.N을 입력받고 일의 자리부터 각각 P 제곱을 하여 더하게끔 하고, 나온 결과 값을 벡터에 저장시켰다.그리고 마지막에 중복되는 값이 나오게 된다면, 벡터에 저장되어 있는 값들을 중복된 값 이전까지의 갯수를 출력하면 문제를 해결할 수 있다. 문제의 조건에서 1 > P; v.push_back(N); while (!isCheck[N]) { int ret = 0; isCheck[N] = true; for (int i=N; i>0; i/=10) { ret += pow(i % 10, P); } v.push_back(ret); N = ret; } for (int i=0; i

2667번 단지 번호 붙이기 문제는 DFS를 통해 완전 탐색으로 해결할 수 있는 문제이다.출력에 2가지가 출력이 되어야한다. 1. 연결 요소의 갯수2. 인접한 집의 갯수 2번에서 인접한 집의 갯수를 출력할 때, 오름차순으로 출력을 하라는 조건이 중요하다.이 조건을 깜박하고 제출하였더니 틀렸다고 나와 고생좀 했다. 앞에서 푼 문제들과 비슷한 유형이기에 쉽게 풀 수 있었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include #include using namespace std; int N, component;int dx[4] =..

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 탐색이 끝났으면, 결과..

이 문제는 단순한 DFS와 BFS 구현이다.각 자료구조에 대한 개념만 알고 있다면 충분히 풀 수 있는 문제이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include #include #include #include #define TRUE 1#define FALSE 0 using namespace std;int N, M, V;int graph[1001][1001];int isVisited[1001];queue q; void bfs(int V) { int u = 0; q.push(V); isVisited[V] = TRUE; wh..

예시로 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의 먹는..

캠핑 문제는 그리디 알고리즘으로 해결 가능하다.답을 구하는 소스는 너무나도 간단하나, 조건 하나를 빠뜨려서 계속 틀렸던 문제이다. 조건을 잘 확인하고 푸는 습관을 가지는 것이 중요한 것 같다.나 같은 경우에는 1 < L < V < P 조건도 무시하고 문제를 풀었다.조건을 추가한 뒤에도 또 틀렸다고 나왔다.또 한 가지 문제는 V % P 의 값이 L보다 작아야한다는 것을 간과했다.이 조건을 추가한 뒤 제출하였더니 정답이었다. 문제는 단순하나 조건을 조금 더 생각해봐야 할 문제. 123456789101112131415161718192021222324252627282930#include using namespace std; int l, p, v;int main(int argc, const char * argv[..

동전 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,..