jmmm_25

문제에서 주어진 조건처럼 미로 중에 '0'인 곳은 지나갈 수 없고, '1'인 곳만 지나갈 수 있다.그러므로 (1,1) 부터 (N,M) 인 (4,6)까지 BFS 탐색을 하면 된다. BFS 개념만 알고 있다면 단순한 문제이다.소스는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include#includeusing namespace std; struct Info{ int x; int y; int cnt;}; int N, M;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};char map[10..

7568번 덩치 문제는 조건만 잘 이해하면 되는 문제이다.A (x, y) 와 B (p,q)의 덩치를 비교하는데 있어, 조건식은 x > p && y > q 이면 A가 B보다 덩치가 크다고 할 수 있다. 우선 순서대로 (몸무게, 키)를 번호로 지정할 수 있게 벡터에 저장시킨다. 여기서 구조체의 개념이 들어간다.그 후에, i번째 (몸무게, 키)를 나머지 i번 째를 제외한 나머지(몸무게, 키) 와 비교를 한다.만약 비교하였을 때, i 번째 (몸무게, 키)의 덩치가 작다면 미리 만들어 놓은 ranked[i]의 값을 +1 해준다. ranked[i]++ 는 나보다 덩치가 큰 사람이 늘어난다는 것이다. 그 후에, 문제의 조건에서 "만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다." ..

6603번 로또 문제는 부분 집합을 구할 수만 있다면 쉽게 해결할 수 있다.더 간단한 방법이 있겠지만, 문제를 풀 때 vector에 부분 집합을 넣은 후, 사이즈가 6이 되는 것만 출력하게끔 했다.다음에 다른 사람들은 어떻게 문제를 풀었는지, 조금 더 나은 방법이 있는지 확인 해야겠다.문제의 출력과 순서가 동일하게 나와야 맞았습니다가 뜨는 것 같다.같이 푼 친구는 flag 없이 비트 연산으로 부분집합을 구해서 풀었는데, 순서만 나와 다르게 나왔다.순서 때문에 틀린 것인지, 아니면 잘못푼 것인진 잘 모르겠다. 소스는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#i..

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..