본문 바로가기

코딩테스트4

[백준 11266] C++ 단절점 DFS 문제https://www.acmicpc.net/problem/11266 풀이int dfs(int now, bool isRoot){ visited[now] = ++cnt; int ret = visited[now]; int child = 0; for (const int& next : graph[now]) { if (parent[now] == next) continue; if (visited[next]) { ret = min(ret, visited[next]); continue; } child++; parent[next] = now; int low = dfs(next, false); ret = min(ret, low); if (!isRoot && low >= visited[now]) .. 2025. 5. 7.
C++ 그래프의 사이클 노드 찾기 사이클 노드 찾기https://k99812.tistory.com/147 [백준 11400] C++ 단절선 DFS문제https://www.acmicpc.net/problem/11400 풀이int dfs(int start){ visited[start] = ++cnt; int ret = visited[start]; for (const int& next : graph[start]) { if (parent[start] == next) continue; if (visited[next]) { ret = min(ret, visited[next]); continuek99812.tistory.com 위의 문제의 코드를 바탕으로 코드가 진행된다 vector visited, parent, inStack;int dfs(int .. 2025. 5. 7.
[백준 11400] C++ 단절선 DFS 문제https://www.acmicpc.net/problem/11400 풀이int dfs(int start){ visited[start] = ++cnt; int ret = visited[start]; for (const int& next : graph[start]) { if (parent[start] == next) continue; if (visited[next]) { ret = min(ret, visited[next]); continue; } parent[next] = start; int low = dfs(next); ret = min(ret, low); if (low > visited[start]) { bridge.push_back({ min(start, next), .. 2025. 5. 7.
[백준 11053] C++ 가장 긴 증가하는 부분 수열 LIS https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net LIS(Longestr Increase Sequence) 알고리즘을 구현하는 문제 LIS란? n개의 수열중에서 각 원소가 이전 원소들 보다 큰 수열이다 LIS 구현C++에선 lower_bound로 구현할 수 있다. lower_bound는?범위 안의 원소들 중, x와 같은 숫자 or 같은 숫자가 없으면 x보다 큰 숫자의 이터.. 2024. 3. 4.

티스토리툴바