문제 풀이

#1. 문제https://www.acmicpc.net/problem/13418  #2. 풀이 1. 최소 신장 트리 [자료구조]#6_그래프#0. 개념 1. 그래프?[정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와webddevys.tistory.com신장 트리는 그래프의 모든 정점을 최소한의 간선으로 순환 구조 없이 연결하는 부분 그래프를 의미합니다. 따라서, 최소 신장 트리는 가중치 그래프에서 간선들의 합이 최소가 되는 신장 트리입니다. 최소 신장 트리 알고리즘으로 크루스칼 알고리즘, 프림 알고리즘, 솔린 알고리즘이 있습니다.  2. 크루스칼 알고리즘 [자료구조]#6_그래프#0. 개념 1. ..

#1. 문제https://www.acmicpc.net/problem/5670  #2. 풀이 1. Trie 자료구조 [자료구조]#8_Trie 검색 트리#1. 개념 트라이(Trie)는 검색 트리의 일종으로, 주로 문자열 검색에 사용되는 자료구조입니다. 트라이 검색 트리의 각 노드는 문자열의 특정 문자를 나타내며, 자식 노드에 대한 링크(배열 혹은webddevys.tistory.comTrie 자료구조는 검색 트리의 한 종류로 각 노드는 문자열의 특정 문자를 나타내며, 자식 노드에 대한 링크와 마지막 문자 여부를 갖습니다. 2. 부동 소수점 [BOJ알고리즘, C++]#1008_A/B, C++ 부동 소수점, precision(), fixed[BOJ 알고리즘, C++] #1008_C++ A/B, 부동 소수점, pr..

#1. 문제https://www.acmicpc.net/problem/1735  #2. 풀이 1. 유클리드 호제법https://webddevys.tistory.com/162 [BOJ알고리즘, C++]#2609_최대 공약수와 최소 공배수, 유클리드 호제법[BOJ 알고리즘, C++] #2609_최대 공약수와 최소 공배수, 유클리드 호제법 BOJ 알고리즘 문제 풀이, 2609_최대 공약수와 최소 공배수유클리드 호제법 알고리즘을 통해 두 자연수의 최대 공약수와webddevys.tistory.comint gcd(int a, int b){ int c = a%b; while(c != 0) { a = b; b = c; c = a%b; } return b;}int..

#1. 문제https://www.acmicpc.net/problem/1446  #2. 풀이 1. 다익스트라 [알고리즘]#2_길 찾기 알고리즘#1. 개념 1. 길 찾기 알고리즘[정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구webddevys.tistory.com다익스트라 알고리즘은 '단일-출발' 최단 경로 알고리즘입니다. 시작 정점을 기준으로 다른 모든 정점에 대하여 최단 경로 값을 찾는 알고리즘으로, 일반적으로 우선순위 큐와 BFS를 활용합니다. 2. 유방향 그래프에 대한 다익스트라 알고리즘!먼저, 유방향 그래프를 구성합니다. 지름길 외에도 각 지점마다 '지름길'이 아닌 일반 길에 대한 경로도 추..

#1. 문제https://www.acmicpc.net/problem/15657  #2. 풀이 1. 백트래킹https://webddevys.tistory.com/313 [알고리즘]#6_백 트래킹[알고리즘]#6_백 트래킹 백 트래킹 알고리즘에 대해 알아보겠습니다. Overview 개념 예제 #0. 개념 1. 백 트래킹 백 트래킹 알고리즘은 문제 해결을 위해 여러 후보 해결책들을 점진적으로 탐색하며,webddevys.tistory.com백트래킹 알고리즘은 여러 후보 경로들을 점진적으로 탐색해 나가며, 현재 경로가 해결책으로 이어지지 않는다고 판단되면 이전 레벨로 돌아가 다른 후보 경로들을 탐색하는 알고리즘입니다.  2. 중복 선택 가능한 동시에 '1, 7' == '7, 1' 인 중복 없는 조합 고르기!먼저, ..

#1. 문제https://www.acmicpc.net/problem/1135  #2. 풀이 1. DFShttps://webddevys.tistory.com/291#%232.%20%ED%83%90%EC%83%89-1 [자료구조]#6_그래프#0. 개념 1. 그래프?[정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와webddevys.tistory.comDFS는 그래프의 모든 정점을 탐색하는 방법 중 하나로 시작 노드를 기점으로 더 이상 확장 불가능한 단말 노드에 이르기까지 깊이 우선적으로 탐색하는 방법입니다. 일반적으로,  DFS는 재귀 호출 혹은 스택 자료구조를 활용하여 구현 가능합니다. 2. ..

#1. 문제 https://www.acmicpc.net/problem/14502   #2. 풀이 1. 백트래킹  [알고리즘]#6_백 트래킹[알고리즘]#6_백 트래킹 백 트래킹 알고리즘에 대해 알아보겠습니다. Overview 개념 예제 #0. 개념 1. 백 트래킹 백 트래킹 알고리즘은 문제 해결을 위해 여러 후보 해결책들을 점진적으로 탐색하며,webddevys.tistory.com백트래킹은 문제 해결을 위해 점진적으로 후보 해결책들을 탐색하며, 현재 선택한 경로가 문제 해결로 이어질 수 없다고 판단되면, 이전 단계로 돌아가 다른 후보 경로들에 대한 탐색을 진행합니다.  2. DFS, BFS [자료구조]#6_그래프#0. 개념 1. 그래프?[정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구..

#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. 그래프?[정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 ..