![]()
#1. 문제https://www.acmicpc.net/problem/4256 #2. 풀이 1. 트리의 순회 [자료구조]#5_트리[자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다. Overview 개념이진트리순회이진 탐색 트리균형 이진트리AVL 트리레드-블랙 트리Map, Set힙 #0. 개념1. 트리? [정의] : 트리는 1:n 관계의webddevys.tistory.com트리 자료구조는 세 가지 순회 방법을 갖습니다. 모두 현재 노드를 기준으로 (1) 전위 순회(루트->왼쪽->오른쪽), (2) 중위 순회(왼쪽->루트->오른쪽), 그리고 (3) 후위 순회(왼쪽->오른쪽->루트)가 있습니다. 대부분의 경우, 주어진 트리 자료구조의 두 가지 순회 내용을 알려주고, 다른 하나의 순회 내용을 구하는 문제..
![]()
#1. 문제https://www.acmicpc.net/problem/2579 #2. 풀이 1. DP [알고리즘]#5_동적 계획법[알고리즘]#5_동적 계획법 동적 계획 알고리즘에 대해 알아보겠습니다. Overview 개념 예제 #0. 개념 1. 동적 계획법(Dynamic Programming) 동적 계획법은 최적화 문제를 해결하는 데 사용되는 알고리즘 디webddevys.tistory.comDP는 입력 크기에 따라 중복되는 하위 문제들을 재귀적으로 해결하고, 결과 값을 기억함으로써 중복 계산을 방지하는 최적화 기법입니다. 대표적으로, 트리 자료구조에서 주로 활용되며 DFS 구현과 함께 활용되기도 합니다.2. 패턴을 파악하고, 점화식을 먼저 세우자점화식: dp[i][1] = max(dp..
![]()
#1. 문제https://www.acmicpc.net/problem/15900 #2. 풀이 1. 트리 [자료구조]#5_트리[자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다. Overview 개념이진트리순회이진 탐색 트리균형 이진트리AVL 트리레드-블랙 트리Map, Set힙 #0. 개념1. 트리? [정의] : 트리는 1:n 관계의webddevys.tistory.com트리 자료구조는 1:N 관계의 계층 구조를 갖는 그래프의 한 종류입니다. 트리 자료구조의 노드 간 연결 관계는 간선을 통해 나타내며, 순환 구조를 형성하지 않아 계층 구조가 형성됩니다. 2. DFS [자료구조]#6_그래프#0. 개념 1. 그래프?[정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 ..
![]()
#1. 문제https://www.acmicpc.net/problem/13511 #2. 풀이 1. 트리 [자료구조]#5_트리[자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다. Overview 개념이진트리순회이진 탐색 트리균형 이진트리AVL 트리레드-블랙 트리Map, Set힙 #0. 개념1. 트리? [정의] : 트리는 1:n 관계의webddevys.tistory.com트리 자료구조는 1:N 관계의 계층 구조를 갖는 그래프의 한 종류입니다. 트리 자료구조의 각 노드 간 연결 관계는 간선으로 나타내며, 순환 구조를 갖지 않기 때문에 "계층 구조"를 형성합니다. 트리 자료구조의 노드 개수가 N개라면, 간선의 개수는 N-1개입니다. 2. LCA [알고리즘]#7_LCA(Least Common Ancest..
![]()
#1. 문제https://www.acmicpc.net/problem/1058 #2. 풀이 1. 플로이드-워셜 [알고리즘]#2_길 찾기 알고리즘#1. 개념 1. 길 찾기 알고리즘[정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입..webddevys.tistory.com플로이드-워셜 알고리즘은 음수 가중치를 포함하는 그래프 자료구조에서 "전체-쌍" 최단 경로를 구하는 길 찾기 알고리즘입니다. 플로이드-워셜 알고리즘은 "음수 가중치", "사이클 여부", 그리고 "경유 정점 혹은 경유 정점을 통한 새로운 경로" 개념에 적용하기에 적절한 알고리즘입니다. 플로이드-워셜 알고리즘의 최악 시간 복잡도는 O(n³)입니다. 2. 최단 경로를 찾고, 두 정점 쌍에 대하여..
![]()
#1. 문제https://www.acmicpc.net/problem/2213 #2. 풀이 1. 트리https://webddevys.tistory.com/287 [자료구조]#5_트리[자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다. Overview 개념 이진트리 순회 이진 탐색 트리 균형 이진트리 AVL 트리 레드-블랙 트리 Map, Set 힙 #0. 개념 1. 트리? [정의] : 트리는 1:n 관계의webddevys.tistory.com트리는 그래프의 한 종류로, 1:N 관계의 계층 구조를 갖는 비 선형 자료구조입니다. 트리는 노드와 노드 간 연결 관계를 표현하는 간선으로 이루어져 있습니다. 트리 자료구조의 노드 개수가 N개라면, 간선의 개수는 N-1개로, 순환 구조를 갖지 않습니다. 2. DP..
![]()
#1. 문제https://www.acmicpc.net/problem/1949 #2. 풀이 1. 트리https://webddevys.tistory.com/287 [자료구조]#5_트리[자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다. Overview 개념 이진트리 순회 이진 탐색 트리 균형 이진트리 AVL 트리 레드-블랙 트리 Map, Set 힙 #0. 개념 1. 트리? [정의] : 트리는 1:n 관계의webddevys.tistory.com트리 자료구조는 그래프의 한 종류로, 1:N 관계의 계층구조를 갖는 비 선형 자료구조입니다. 만약, 트리 노드의 개수가 N이라면, 간선의 개수는 N-1이며, 비순환 구조입니다. 2. DPhttps://webddevys.tistory.com/311 [알고리즘]#5..
![]()
#1. 문제https://www.acmicpc.net/problem/10159 #2. 풀이 1. 플로이드-워셜https://webddevys.tistory.com/298 [알고리즘]#2_길 찾기 알고리즘#1. 개념 1. 길 찾기 알고리즘[정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입..webddevys.tistory.com플로이드-워셜 알고리즘은 '음수 가중치'를 포함하는 가중치 그래프의 "전체-쌍 최단 경로"를 구하는 알고리즘입니다. 특히, 경유 정점(간접적으로 연결된 서로 다른 정점) 개념이 강조되는 문제에서 플로이드-워셜 알고리즘이 유용합니다. 일반적으로, 플로이드-워셜 알고리즘은 총 3개의 for문을 통해 시작 정점과 도착 정점의 최단 경..
![]()
#1. 문제https://www.acmicpc.net/problem/15654 #2. 풀이 1. 백트래킹 [알고리즘]#6_백 트래킹[알고리즘]#6_백 트래킹 백 트래킹 알고리즘에 대해 알아보겠습니다. Overview 개념 예제 #0. 개념 1. 백 트래킹 백 트래킹 알고리즘은 문제 해결을 위해 여러 후보 해결책들을 점진적으로 탐색하며,webddevys.tistory.com백트래킹 알고리즘은 문제 해결을 위해 여러 후보책들을 점진적으로 탐색하는 알고리즘입니다. 백트래킹 알고리즘은 현재 경로가 해결책으로 이어질 수 없다고 판단되면 이전 단계로 돌아가 다른 후보 경로에 대한 탐색을 진행합니다. 일반적으로, 백트래킹 알고리즘은 재귀 호출을 활용한 DFS를 통해 구현합니다. 2. 순열 백트래킹 유형, 순서가 중..
![]()
#1. 문제https://www.acmicpc.net/problem/1182 #2. 풀이 1. 백트래킹 [알고리즘]#6_백 트래킹[알고리즘]#6_백 트래킹 백 트래킹 알고리즘에 대해 알아보겠습니다. Overview 개념 예제 #0. 개념 1. 백 트래킹 백 트래킹 알고리즘은 문제 해결을 위해 여러 후보 해결책들을 점진적으로 탐색하며,webddevys.tistory.com백트래킹 알고리즘은 문제 해결을 위해 여러 후보를 점진적으로 탐색해 나가는 방법입니다. 백트래킹 알고리즘은 현재 후보 경로가 해결책으로 이어질 수 없다고 판단되면, 이전 레벨로 돌아가 다른 후보 해결책들을 탐색합니다. 백트래킹 알고리즘은 일반적으로 재귀 호출을 활용한 DFS를 통해 구현합니다. 2. '조합' 유형의 백트래킹, 다만, '반..
