본문 바로가기

백준4

[백준 2877] C++ 4와 7 문제https://www.acmicpc.net/problem/2877 풀이while (n > 0){ if (n % 2 == 0) { ret += "7"; } else { ret += "4"; } n = (n - 1) / 2;} n을 % 2를 해 홀수면 4, 짝수면 7을 추가한다 그러면 해당 코드는 아래 그림처럼 동작한다 n = (n - 1) / 2 부모노드의 번호를 구하여 부모노드로 이동한다ex) n = 4 이면 str에 7, 4 순으로 들어가게된다그 이유는 부모 노드부터가 아니라 역순으로 자식에서 부모순으로 탐색한다그래서 reverse를 해줘야 된다 전체 코드#include#include#includeusing namespace std;int n;int main(){ cin >> n; strin.. 2025. 5. 16.
[백준 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.
[백준 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.

티스토리툴바