서론 오늘도 문제 풀다 번아웃이 왔다. 4시간 동안 풀었다... 4일 차 대체 경로 문제 : 요약이 힘들어 사진으로 대체 가장 짧은 거리를 찾는것임으로 BFS를 이용하여서, 하나의 길이 만들어진다면 종료되도록 구성하였다. 단순한 BFS를 구현하면 Timeout이 발생함으로 distace 배열을 통하여 거리를 저장하여 계산을 구현하였다. ◆코드 전문◆ #include #include #include using namespace std; int node, edge, start, endNode; int bfs(int day,vector &edgeList) { if (day == start || day == endNode) { return -1; } vector distance(node + 1, -1); vec..
서론 진짜 순수 문제 풀이 시간만 5시간은 걸렸다. 이렇게 어렵게 풀 문제였나 생각이 들어서 마음이 심란했던 하루다. 2일 차 통신망 분석 문제 : 그래프에서 연결된 것들의 집합 중 가장 밀도가 높은 컴포넌트의 정보를 구하자. 간선을 2차원 배열 edge에 받아 저장해 주었다. 빠른 시간 복잡도를 위해서 각 노드(i)에서 갈수 있는 노드(j)를 저장해 주었다. 연결된 것들의 집합을 DFS를 통하여 구하고(밀도를 구하기 위해 간선의 갯수도 구하고), realComponent에 저장해주었다. 출력 조건을 맞추기 위해서 realComponent배열 앞에 밀도와 (컴퓨터의 수 * -1) 마지막으로 (컴포넌트에서 가장 작은 수* -1) 를 넣어주고 내림차순으로 정렬하여 realComponent[0]에 있는 값을 ..
서론 DFS로 풀다가 Runtime Error... BFS로 풀다가 Timeout.... 으악 살려줘~ 2일 차 발전기 문제 : 상하좌우로 "연결된 집" 집단의 개수를 구하여라 문제 설명을 비약적으로 짧게 만들었으나 문제를 푸는 데에 문제는 없다... 처음엔 DFS를 통해서 풀었으나 1000 * 1000과 같은 경우에 Runtime Error(재귀 한도 초과로 추측)가 발생하여 BFS로 짜주었다. 오늘도 맞왜틀? Timeout을 중점으로 글을 쓴다. ◆코드 전문◆ #include #include using namespace std; int N, answer = 0; int map[1100][1100]; int dx[4]{1, -1, 0, 0}; int dy[4]{0, 0, 1, -1}; queue que..
서론 새로운 한 주의 시작이다. DP 배낭 문제를 생각하며 푸니 금방 풀었지만... Runtime Error가 발생하여 골머리를 앓았다. DP적인 부분은 다른 블로그에서 많이 이야기할 테니, 내가 겪은 맞는데 왜 틀리지를 위주로 설명하도록 하겠다. 바로 확인해보자. 1일 차 통증(2) 문제 요약 : 통증 N과 치료제 A(x만큼 회복), B(y만큼 회복)가 무제한으로 주어질 때, 최소한의 치료제를 써서 통증을 0으로 만들 아이템의 최소 사용 개수를 출력하라. 0으로 맞추지 못할 때는 -1을 출력하여라. 0으로 맞추지 못할때는 -1을 출력하여라.라는 구문 덕에 자연스럽게 DP를 통해서 구현하게 되었다. 원리는 A, B를 하나 더 쓰기 전 스트레스 상태에서 0이 될 수 있다면, 최소 값을 구하였다. dp[i]..
