본문 바로가기

전체 글191

[백준][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.
[최소 힙] c++ 구현 및 설명 이미지 출처:https://namu.wiki/w/%ED%9E%99%20%ED%8A%B8%EB%A6%AC 힙의 정의 우선 순위 큐를 이해하기 위해서는 힙이라는 것을 알아야 한다. 완전 이진트리의 일종으로 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안되었다. 힙의 특징키 값의 대소관계는 오로지 부모 노드와 자식노드 간에만 성립하여 형제 사이에는 대소 관계가 정해지지 않는다. (예를 들어 9와 14사이에는 우선순위가 있지만 14와 18사이에는 우선순위가 존재하지 않는다.) 힙의 시간 복잡도는 O(logn)이다. 힙의 종류최대 힙(Max Heap): (완전 이진 트리) + (부모 노드 > 자식 노드)최소 힙(Min Heap): (완전 이진 트리) + (부모 노드 < 자식 노드) 이미지 출처:http.. 2024. 2. 14.
[백준][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

티스토리툴바