본문 바로가기

백준 문제풀이93

[백준][bfs] 트리의 부모 찾기 11725 c++구현 목차 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 제목 문제 구현 방향 이진 트리가 아니기 때문에 인접리스트를 만들어 bfs탐색을 통해 해결해 보았다. 코드 구현 #include #include #include using namespace std; vectortree[100000]; vectorvisit(100000, false); vectorparent(100000, 0); //부모를 저장할 배열 void bfs(int start) { queue q; q.push(start); visit[start] .. 2024. 2. 19.
[백준][bfs] 1068 트리 c++ 구현 목차  https://www.acmicpc.net/problem/1068 1068번: 트리첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다www.acmicpc.net문제  문제 구현 방향이진 트리가 아니기 때문에 인접리스트를 통해서 문제를 접근하였다.삭제는 bfs를 통해 탐색하여 삭제 노드를 표시하는 방법으로 접근했다.    문제 풀이예시 입력)91 6 4 1 3 3 8 8 -13 0    103  2    345  42   5    61   7    867  (단방향 인접 리스트)       그래프와 인접리스트로 표현한 모습이다.   0    103.. 2024. 2. 19.
[백준][dp] 1912 연속합 c++ 구현 목차 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 문제 구현 방향 다이나믹 프로그래밍의 방법 중 하나인 상향식을 이용해 구현하고자 했다. 다이나믹 프로그래밍의 개념을 모른다면 아래 링크를 참고하면 좋다 https://be-senior-developer.tistory.com/19 [DP] 동적 계획법 알고리즘 c++ 설명 목차 DP(다이나믹 프로그래밍) 메모리를 적절히 사용하여 시간 복잡도를 비약적으로 단축시킬 수 있는 방법이다. 일반적으로 하향식.. 2024. 2. 13.
[백준][dp] 11053 가장 긴 증가하는 부분 수열 c++ 구현 목차 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 문제 문제 구현 방향 다이나믹 프로그래밍의 방법 중 하나인 상향식을 이용해 구현하고자 했다. 다이나믹 프로그래밍의 개념을 모른다면 아래 링크를 참고하면 좋다 https://be-senior-developer.tistory.com/19 [DP] 동적 계획법 알고리즘 c++ 설명 목차 DP(다이나믹 프로그래밍) 메모리.. 2024. 2. 13.
728x90

티스토리툴바