전체보기141 [BOJ] 7579 앱 DP 문제인데, 정말 진땀 뺀 문제이다. 단순히 메모리의 크기를 index로 잡기엔 값이 너무 커서, cost를 인덱스로 잡아서 풀었다. 배열에 저장되는 값은 해당 cost로 얻을 수 있는 최대 Memory 이득이다. 포인트는 이부분이다. 순방향이 아니라 역방향으로 진행해야 메모리가 중복해서 사용되는 것을 방지할 수 있다. #include #include #include #include using namespace std; int N, M, temp; int c[101]; int m[101]; int dp[10001]; int main(){ scanf("%d %d", &N, &M); for(int i = 0 ; i < N ; i++){ scanf("%d", &m[i]); } for(int i = 0 ; .. 2020. 4. 16. [BOJ] 11562 백양로 브레이크 이 문제는, 주어진 두 지점에 대해서 '최소 몇번 역방향 다리를 새로 놓아야 접근할 수 있는지' 에 대해 묻는 문제이다. 뒤집어서 생각하는 것이 관건이다. 길이 없는 경우 거리를 무한대, 양방향 길이 있는 경우 거리를 0, 단방향만 있는 경우는 길이 없는 방향에 대해 1 값을 부여한다. 그 후, Floyd-Warshall 알고리즘을 적용하면, 모든 Path에 대해 최단거리로 이동하기 위해 설치해야 할 다리의 갯수가 나온다. #include #include using namespace std; const int INF = 1 2020. 4. 14. [2] Floyd-Warshall 알고리즘 플로이드 워셜 알고리즘은 그래프에서 "All-pair-shortest-path" - 정점들의 모든 쌍의 최단 경로의 길이를 구하는 알고리즘이다. 그래프 알고리즘 중 가장 단순한 알고리즘이라고 생각된다. Brute-Force랑 거의 같다고 볼 수 있기 때문이다. 알고리즘도 단순하다. pseudo-code를 보자. 다음과 같이 Floyd-Warshall은 for문 3개로 돌아간다. 의미를 해석하자면 i에서 j로 가는 길의 거리를 생각했을 때, i에서 j로 바로 가는게 빠른지 -> (d_ij) 아니면 k를 경유하여 가는게 빠른지를 비교해서 (d_ik + d_kj) 더 작은 길의 값이 지정이 되는 것이다. (min) 저장되는 그래프 D의 dij는 곧 i에서 j로 가는 최단 거리가 지정이 될 것이다. 2020. 4. 12. [BOJ] 2473 세 용액 3-SUM 알고리즘을 이용하여 문제를 풀 되, 정확한 조합이 아닌 가장 가까운 답을 찾는 것이 목표이다. 고로 합산한 결과 값 중 현재 최소인 조합의 결과를 저장해야 한다. #include #include #include #include using namespace std; int a, b, c; long long N, temp, best = LLONG_MAX; vector val; int main(){ cin >> N; for (int i = 0 ; i > temp; val.push_back(temp); } sort(val.begin(), val.end()); for(int first = 0 ; first < val.size() - 2; first++){ int secon.. 2020. 4. 11. 이전 1 ··· 26 27 28 29 30 31 32 ··· 36 다음
