GGym's Practice Notes

BFS를 이용하여 가장 먼 노드를 찾는다. 최단거리 탐색법을 사용하여 계산하면 좀 더 깔끔하게 나오겠지만 BFS를 사용하는 것이 더 쉬워보인다. DFS로 풀어보려다가 계속 시간초과나서 포기했다. #include // Level3_ 가장 먼 노드 [BFS] #include #include #include #include #include using namespace std; bool visit[20001]; int dst[20001]; int solution(int n, vector edge) { int answer = 0; vector graph(n, vector(n, false)); queue q; for(int i=0; i n >> k; for(int i=0; i k; edge[i].push_back(..

이분탐색 문제이다. 심사관이 맡을 수 있는 사람의 수 += 걸리는 추청 시간 / 심사관이 심사하는데 걸리는 시간 이 공식을 알아야지 문제를 풀 수 있다. 사람의 수가 많거나 같다면 최저시간을 저장한 후 추정시간을 늘리고 적다면 추정시간을 줄여본다. #include // Level3_ 입국심사 [이분탐색] #include #include #include using namespace std; long long solution(int n, vector times) { sort(times.begin(), times.end()); long long l=0, r = (long long)(times[times.size()-1]) * n; long long answer = r; while(l> n >> n_t; for..

비교적 쉬운 Level3 문제 DFS나 BFS를 쓰면 간단하게 풀 수 있다. 나는 연습삼아 BFS를 사용했다. #include #include #include using namespace std; bool visit[200]; void bfs(int v, int n, vector computers){ queue q; visit[v] = true; q.push(v); int now; while(!q.empty()){ now = q.front(); q.pop(); for(int i =0; i

규칙을 찾아보면 그냥 피보나치랑 똑같다. DP로 착각할 수 있고 풀 수도 있겠지만 속도차이가 있을까... #include #include #include using namespace std; int solution(int n) { int answer=0; if (n == 1) answer = 1; else if (n == 2) answer = 2; else for(int i=2, j=1, k=2; i

Vector로 되어있는 입력 데이터를 Stack으로 옮긴 후 basket Stack을 이용하여 인형이 제거되는 갯수를 센다. #include // Level1_ 크레인 인형뽑기 게임 [스택] #include #include #include using namespace std; int solution(vector board, vector moves) { int answer = 0; stack doll[board.size()]; stack basket; for(int i = board.size()-1; i>=0; i--){ for(int j =0; j

Stack과 가격을 가격이 적어질 때까지 top과 비교한다. #include // level2_ 주식가격 [스택] #include #include using namespace std; vector solution(vector prices) { vector answer(prices.size()); stack stk; for(int i=0; i prices[i]){ answer[stk.top()] = i - stk.top(); stk.pop(); } else break; } stk.push(i); } } while(!stk.empty()){ answer[stk.top()] = prices.size() - stk.top() - 1; stk.pop(); } return answer; }