[ 문제 ] [ 구현 ] 다익스트라 알고리즘을 어떻게 활용할 것인지에 대해 먼저 설계하고 풀기 시작하는 것이 좋다. 다익스트라 알고리즘은 어떠한 한 점으로부터 다른 모든 점들까지의 최단거리를 구해주기 때문에 A->B의 경로 상에 있는 점인지 확인하려면 A,B 를 기준점으로 다익스트라 알고리즘을 각각 돌리고 그로부터 구해진 어떠한 한점 i까지의 최단거리를 더했을때 (dist_a[i] + dist_b[i]) 이것이 a와 b사이의 최단거리 dist_a[b](dist_b[a])과 같은지 확인하면 된다. 주의사항은 간선간의 거리가 10^9이고 주어진 점들의 개수가 2*10^5이므로 초기 INF값을 충분히 크게 해줘야 하며, 데이터를 담을 벡터 배열의 자료형을 long long으로 해줘야 한다. [ 코드 ] #in..
[ 문제 ] [ 구현 ] 플로이드 워셜을 통해서 자기 자신으로 돌아오는 사이클을 구할 수 있는 점을 이용하면 쉽게 풀 수 있다. [ 코드 ] #include #include #define INF 987654321 using namespace std; int graph[401][401]; int v, e; void floyd() { for (int k = 1; k > e; for (int i = 1; i a >> b >> c; graph[a][b] = c; } floyd(); int ans = INF; for (int i = 1; i
[ 문제 ] [ 구현 ] dp[cnt][total] : cnt번째까지의 추를 통해 total의 무게를 만들 수 있는가를 기록하는 배열 solve(cnt + 1, abs(total - w[cnt])); solve(cnt + 1, total); solve(cnt + 1, total + w[cnt]); 와 같이 재귀적으로 해당 추를 통해 무게를 더할지, 뺄지, 사용하지 않을지를 반영해주며 배열에 기록해나간다. 종료조건은 cnt>n으로 설정해주고, 이미 이전에 방문한 적이 있는 cnt와 total의 경우에 도달한 경우 곧바로 탈출하여 중복으로 탐색하는 것을 막아주어야만 시간 초과가 나지 않는다. [ 코드 ] #include #include using namespace std; int n; int dp[31][1..
[ 문제 ] [ 구현 ] 분할정복 + 해 구성하기 느낌으로 풀었다 핵심 아이디어는 주어진 n을 2등분해 나가면서 절반은 A로 나머지 절반은 B로 바꿔주는 것이다. 이러한 분할정복 방식을 통한다면 2^7은 128이므로 n= ed || depth == 7) return; int mid = (st + ed) / 2; for (int i = st; i n; dq(0, n - 1, 0); for (int i = 0; i < print_cnt; i++) { for (int j = 0; j < n; j++) { if (arr[i][j] == '\0') { arr[i][j] = 'A'; } cout
[ 문제 ] [ 구현 ] dfs+dp(메모이제이션)을 통해 풀 수 있다. 단순히 bfs/dfs를 돌리면 시간초과가 나는 이유는 한정된 점에 대해 돌리는 것이 아니라 모든 블록을 출발점으로 잡아서 한번씩 확인해봐야 하기 때문에 최악의 경우 O(N^4)이 나오기 때문이다. 우선 처음 출발하는 블록의 경우에 대해 방문한 블록 개수 1로 초기화 해주고 이미 방문한 블록이라면 dp배열에 저장해놓은 값을 바로 리턴 아니라면 if (forest[nx][ny] > forest[x][y]) { dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1);} 을 통해 다음 블록이 더 많은 대나무를 가지고 있는지 확인하고 기존까지의 최대 블록 이동개수와 다음 블록을 통해 끝까지 나아갔을 때의 블록 이동개수를 ..
[ 문제 ] [ 구현 ] 해 구성하기 형식의 특이한 문제이다. 100만 이하의 숫자를 개수가 2000 이하인 순열내의 연속된 수들의 합으로 모두 커버할 수 있어야 하는데, 직관적으로 생각해서 1을 연속으로 999개 놓고 1000을 연속으로 1000개 놓으면 해결된다. [ 코드 ] #include using namespace std; int main() { cout
[ 문제 ] [ 구현 ] 음의 간선이 존재하는 최단거리 그래프 문제이므로 벨만-포드 알고리즘을 이용해야 한다. 이때 벨만-포드 알고리즘의 핵심적인 부분을 간단하게 요약해보면 초기에 출발점을 0, 나머지 모든 정점들을 INF로 설정하고 정점의 개수가 N개 일때 N-1번만 루프를 돌아주면 dist배열에 저장된 거리가 최단거리인데 거리를 갱신할 때의 조건을 잘 이해하는 것이 핵심이다. if(dist[j] != INF && dist[next] > dist[j] + cost) { dist[next] = dist[j] + cost; } 우선 dist[j] !=INF가 의미하는 것은 출발점으로부터 현재 접근이 가능한 상태인 정점인 경우를 의미하고 이 조건이 없으면 출발점에서 절대 갈 수 없는 정점을 통해서도 거리의 ..
[ 문제 ] [ 구현 ] 이분 그래프라면 연결된 간선의 양 끝점이 다른 색깔로 색칠될 수 있어야 한다라는 성질을 이용하면 쉽게 풀 수 있는 문제였다. 주어진 간선정보를 벡터에 채워넣어 그래프를 만들어 두고 그 그래프를 bfs로 탐색하면서 방문하지 않은 모든 점들에 대해 현재 점과는 다른 색으로 값을 채워넣어주는 식으로 구현하였다. 이렇게 구현한 bfs를 돌리고나면 결과적으로 간선이 연결된 모든 점들에 대해 어느 색깔이 칠해진 상태로 bfs 탐색이 마무리 될 것이고, 따라서 이후에는 전체 그래프를 탐색하면서 간선상의 두 점의 색이 다른지 아닌지 확인해주면 된다. 두 점의 색이 같은 경우 이분 그래프가 아니므로 바로 탈출이 가능하다. [ 코드 ] #include #include #include using n..
