jmmm_25

1389번 케빈 베이컨의 6단계 법칙 문제는 백준의 알고리즘 분류상 DFS로 분류 되어 있지만, 나 같은 경우에는 BFS가 더 쉬울 것 같아서BFS로 문제를 해결하였다. 1번부터 5번 노드를 생성한 후, 인접 리스트를 생성한다.문제의 설명은 위의 문제에서 이미 자세하게 설명이 되어있기 때문에 생략해도 될 것 같다. 1번 노드부터 5번 노드까지의 케빈 베이컨의 수를 구하면 된다.그 후, sort를 통해서 번호가 가장 작은 사람을 출력하면 된다. 소스는 아래와 같다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include#include#in..

이번 문제는 큐와 우선 순위 큐를 잘 활용한다면 쉽게 풀 수 있는 문제이다.우선 순위 큐에 중요도가 내림차순으로 들어간다. 큐에는 각 프린터의 번호와 중요도가 pair로 들어가게 된다.따라서, 큐에 들어 있는 프린터의 중요도가 우선 순위 큐의 중요도와 같지 않으면 큐에서 pop을 한 뒤, 다시 push 해주어 뒤로 보낸다.소스는 아래와 같다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #define TRY_NUMBER 2 using namespace std; int n, m, order; int main(int argc, const char * argv[]) { int t..

이 문제는 완전 탐색으로 해결한다.여기서 한수란, 양의 정수 X의 자리수가 등차수열을 이루는 것이다.예를 들어, 123 이라는 숫자는 등차 +1인 한수이다.321 이라는 숫자는 등차 -1인 한수이다. 그런데 한 가지 알아야할 것은 1부터 99의 수인 한자리, 두자리의 수는 모두 한 수이다.또한 세자리 수에서는 111, 222, 333, 444, ... 의 3개의 숫자가 중복되는 숫자 또한 한수이다.왜냐하면 등차가 +- 0인 등차 수열이기 때문이다. 나 같은 경우에는 처음에 number라는 배열을 생성시킨 후, 그 세자리 수의 각 자리의 값들을 배열에 저장시켰다.그리고 등차 수열의 경우에는 무조건 + 또는 - 등차를 가지고 있기 때문에 각 자리의 숫자가 증가하거나, 감소하거나 둘 중 하나일 것이다.예를 들..

처음에 이 문제를 풀었을 때 시간 초과가 났었다.아무래도 n이 100000이기 때문이었던 것 같다. 그래서 고치다가 포기를 했었다.그 후, 구글링을 하다가 다른 사람들의 풀이를 봤었다. DFS의 사이클을 찾는 방법은 내가 생각한 방식과는 달랐었다.isVisited 배열 외에 isFinished라는 배열을 하나 더 만들어주면 해결된다. 예제에서 4번 vertex의 경우를 살펴보자.4 -> 7 -> 6 -> 4 -> 7 -> 6 -> 4 ...처럼 4 -> 7 -> 6 이 사이클이 생긴다. 이 경우에는 텀 프로젝트의 조가 이루어진다.여기서 사이클을 어떻게 찾아내냐가 중요한데, isFinished 배열이 그 역할을 한다. 4번 방문 O -> 7번 방문 O-> 6번 방문 O -> 4번 방문여기서 6번 정점이 다..

2468번 안전 영역 문제는 BFS 또는 DFS로 해결되는 문제이다.나는 DFS를 공부하고 있으므로 DFS로 풀었다. 여기서 입력 조건에서 높이는 1 이상 100 이하의 정수이다. 라는 말이 있다. 그래서 높이 h를 1부터 시작하게끔 for 문을 돌렸는데,비가 안오는 경우도 있기 때문에 높이가 0일 때도 체크를 해주어야 한다.그래서 처음에 틀렸었다. 80% 다 되가서 틀렸길래 고민을 하다가, 질문을 검색하여 해결할 수 있었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include #include #define MAX_HEIGHT 100..

DFS로 해결가능한 문제이다.인접행렬로 모든 정점을 DFS 탐색하는 것은 처음이여서 많은 시행착오가 있었다.다음부터는 정점 DFS일 때에는 인접 리스트로 푸는 것이 나을 것 같다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include using namespace std; int N;int map[101][101];bool isVisited[101][101];int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int flag = 0; void dfs(int ret_x, int ret_y, int sta..

적록색약이 아닌 사람이 봤을 때의 구역의 갯수는 일반적으로 알고 있는 DFS 탐색을 하여 구하면 된다. 적록색약일 경우의 구역의 갯수는 R과 G를 동일한 색상으로 파악해야하기 때문에 DFS 탐색 전에 데이터를 약간 변형시켜주었다. 나 같은 경우에는 이중 for문으로 map의 'G'를 'R'로 변경해주어 DFS 탐색을 하였다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include #include #include using namespace std; int N;char map[101][101];bool isVisite..

이 문제 같은 경우에는 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] =..