본문 바로가기
반응형

알고리즘211

[알고리즘] c++ cpp 가장 긴 증가하는 부분 수열 3 포인트 1.가장 긴 증가하는 부분 수열 2하고 똑같은 알고리즘이며 값의 범위만 다르기 때문에 long long 을 사용하였습니다. 2. int 의 범위 –2,147,483,648 ~ 2,147,483,647 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 2020/10/28 - [분류 전체보기] - [알고리즘] c++ cpp 가장 긴 증가하는 부분 수열 2 #include #include #include using namespace std; int main() { int n; long long temp; int cnt=0; vector vc; // vc.push_back(-987654321); //음수 값을 넣어준다. cin >> n; for (int i = 0; i < n; i++) { cin.. 2020. 10. 28.
[알고리즘] c++ cpp 가장 긴 증가하는 부분 수열 2 포인트 1. 이분 탐색을 사용하여 시간 복잡도 O(nlogn) 으로 만들어준다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. #include #include #include using namespace std; int main() { int n, temp, cnt = 0; vector vc; // vc.push_back(-987654321); //음수 값을 넣어준다. cin >> n; for (int i = 0; i > temp; if(vc.empty()) { vc.push_back (temp); cnt+=1; continue; } if (temp > vc.back()) { vc.push_back(temp); cnt+=1; } else { auto it = lo.. 2020. 10. 28.
[알고리즘] c++ cpp 단지번호붙이기 포인트 1. bfs 에서 각 영역에 대하여 번호를 붙이는 방법을 보여준다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. #include #include #include #include #include using namespace std; int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; int n; int map[26][26]; bool visited[26][26]; vector vc; void bfs(int a, int b) { queue q; q.push({a, b}); visited[a][b] = 1; int count = 1; while (!q.empty()) { int x, y; tie(x, y) = q.front(); q.pop(); fo.. 2020. 10. 28.
[알고리즘] 스탠다드 LCS - 최장 공통 부분 수열 최장 공통 부분 수열 문제는 다이나믹으로 해결을 할 수 있습니다. 이 문제는 편집거리 문제와 동일하게 해결을 할 수 있습니다. #include #include #include using namespace std; string str1, str2; int lcs[1001][1001]; int main() { string s1, s2; cin >> s1 >> s2; // LCS 알고리즘을 위해 앞에 '0'을 붙여준다. str1 = '0' + s1; str2 = '0' + s2; for (int i = 0; i < str1.size(); i++) { for (int j = 0; j < str2.size(); j++) { if (i == 0 || j == 0) { lcs[i][j] = 0; continue; }.. 2020. 10. 28.
반응형

티스토리툴바