#동적 계획법(DP)이란? DP의 두 가지 핵심 특성중복되는 부분 문제(Overlapping Subproblems):동적 계획법은 문제를 풀 때 동일한 부분 문제가 여러 번 반복됩니다. 예를 들어, 피보나치 수열에서 F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)를 구할 때, F(n−1)F(n-1)F(n−1)과 F(n−2)F(n-2)F(n−2)을 재귀적으로 구하게 됩니다. 하지만 F(n−2)F(n-2)F(n−2)는 F(n−1)F(n-1)F(n−1)을 계산할 때도 다시 구하게 됩니다. 이처럼 중복된 계산이 자주 발생하므로, 이를 메모이제이션 또는 테이블 저장을 통해 중복 계산을 방지합니다.최적 부분 구조(Optimal Substructure):최적 ..
알고리즘
LIS#include #include #include using namespace std;int LIS(const vector& arr) { if (arr.empty()) return 0; vector lis; for (int i = 0; i arr = {10, 22, 9, 33, 21, 50, 41, 60, 80}; cout LCS#include #include #include using namespace std;int LCS(const string& X, const string& Y) { int m = X.size(); int k = Y.size(); vector> lcs(m + 1, vector(k + 1, 0)); for (int i = 1; i
#include #include #include // std::min 사용using namespace std; // std 네임스페이스를 전역적으로 사용const int INF = 1e9; // 무한대를 의미하는 큰 값void floydWarshall(vector>& dist, int V) { // 모든 정점 쌍 (i, j)에 대해 i에서 j로의 최단 경로 계산 for (int k = 0; k > V; // 거리 행렬 초기화 vector> dist(V, vector(V)); cout > dist[i][j]; } } // 플로이드-워셜 알고리즘 수행 floydWarshall(dist, V); // 결과 출력 cout
https://www.acmicpc.net/problem/2960#include #include #include #include #include using namespace std;bool check[1000001];int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; int count = -1; for (int i = 2; i
1) substr 함수substr 함수는 문자열의 특정 부분을 잘라내는 데 사용됩니다.기본 사용법cpp #include #include using namespace std;int main() { string s = "0123456789"; string subs1 = s.substr(2, 5); // subs1 = "23456" cout 시작 위치와 길이를 지정하여 문자열을 자릅니다.시작 위치만 지정하면 해당 위치부터 끝까지 문자열을 자릅니다.아무 것도 지정하지 않으면 문자열 전체를 복사합니다.find 함수와 함께 사용하기#include #include using namespace std;int main() { string s = "0123456789"; string subs1 ..
#include #include #include using namespace std;vector makePI(const string& pattern) { int m = pattern.size(); vector PI(m, 0); int k = 0; for (int i = 1; i 0 && pattern[k] != pattern[i]) k = PI[k - 1]; if (pattern[k] == pattern[i]) k++; PI[i] = k; } return PI;}void KMP(const string& text, const string& pattern) { int n = text.size(); i..
#정렬속도 비교 알고리즘최선 수행시간평균 수행시간최악 수행시간Run-time(정수 60,000개, 단위sec)삽입 정렬O(n)O(n2)O(n2)7.438선택 정렬O(n2)O(n2)O(n2)10.842버블 정렬O(n2)O(n2)O(n2)22.894카운팅 정렬O(n2)O(n+k)O(n+k).Shell 정렬O(n)O(n1.5)O(n2)0.056퀵 정렬O(n log n)O(n log n)O(n2)0.014병합 정렬O(n log n)O(n log n)O(n log n)0.026힙정렬O(n log n)O(n log n)O(n log n)0.034 #머지소트#include #include // 함수 선언std::vector merge_sort(const std::vector& Data);std::vector merg..
https://www.acmicpc.net/problem/10951 cin.eof() 를 사용 주요 사항입력 시도 후에 확인 가능: cin.eof()는 입력 시도가 실패한 후에만 의미가 있습니다. 즉, cin >> variable과 같은 입력 시도가 먼저 이루어져야 합니다. 만약 입력 시도가 실패하고 그 이유가 파일의 끝에 도달했기 때문이라면, 그때 cin.eof()는 참이 됩니다.eof 플래그: cin.eof()가 참이라는 것은 스트림이 파일의 끝에 도달했음을 의미합니다. 하지만 파일 끝에 도달했다고 해서 바로 cin.eof()가 참이 되지는 않습니다. 먼저 입력 시도가 이루어져야 하고, 그 시도가 파일 끝에 도달했음을 감지해야 합니다. #include #include using namespace s..
#include #include #include using namespace std;int main(){ for (int T = 1; T > V >> E; vector> graph(V + 1); vector indegree(V + 1, 0); for (int i = 1; i > u >> v; graph[u].push_back(v); indegree[v]++; } queue q; cout
#include #include #include #include using namespace std;int main() { int n, m; cin >> n >> m; vector> graph[11]; for (int i = 0; i > u >> v >> w; graph[u].push_back({ v, w }); graph[v].push_back({ u, w }); } vector min_cost(n + 1, INT_MAX); priority_queue, vector>, greater>> pq; min_cost[1] = 0; pq.push({ 0, 1 }); // 비용 ,노드 while (!pq.empty()) { ..
