문제 풀이/BOJ 문제 풀이

#1. 문제 https://www.acmicpc.net/problem/10844   #2. 풀이 1. DP [알고리즘]#5_동적 계획법[알고리즘]#5_동적 계획법 동적 계획 알고리즘에 대해 알아보겠습니다. Overview 개념 예제 #0. 개념 1. 동적 계획법(Dynamic Programming) 동적 계획법은 최적화 문제를 해결하는 데 사용되는 알고리즘 디webddevys.tistory.comDP(Dynamic Programming)은 주어진 입력 크기에 따라서 하위 문제를 재귀적으로 해결하는 동시에, 그 결과 값을 기억함으로써 중복 계산을 방지하는 최적화 기법입니다.  2. DP는 점화식을 먼저 세우자!dp [i][j] = dp [i-1][j-1] + dp [i-1][j+1], if j!= 9 &&..

#1. 문제 https://www.acmicpc.net/problem/14503   #2. 풀이 1. BFS [자료구조]#6_그래프#0. 개념 1. 그래프?[정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와webddevys.tistory.comBFS는 그래프의 모든 정점을 탐색하는 방법 중 하나로, 현재 정점과 인접한 정점들을 우선적으로 탐색하는 방법입니다. 일반적으로, BFS는 큐 자료구조를 활용합니다. 2. 방향 설정만 조심해 주는 미로 찾기 유형!먼저, dy와 dx를 인덱스에 맞춰 북, 동, 남, 그리고 서쪽으로 값을 설정해 줍니다.BFS 구현 시, 큐 자료구조에 { 현재 방향, {현재..

#1. 문제 https://www.acmicpc.net/problem/1854   #2. 풀이 1. 다익스트라 알고리즘 [알고리즘]#2_길 찾기 알고리즘#1. 개념 1. 길 찾기 알고리즘[정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구webddevys.tistory.com다익스트라 알고리즘은 단일-출발 최단 경로를 찾기 위해 활용되며, 가중치 그래프에서 특정 정점을 시작으로 다른 모든 정점을 연결하는 경로 중 최소 가중치를 갖는 경로들을 찾는데 활용됩니다. 일반적으로, 다익스트라 알고리즘은 우선순위 큐와 최단 경로 목록을 활용합니다. 2. 풀이기존의 다익스트라 알고리즘과 달리 출발 정점으로부터 최..

#1. 문제 https://www.acmicpc.net/problem/11812   #2. 풀이 1. 완전 이진트리 [자료구조]#5_트리[자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다.  Overview 개념이진트리순회이진 탐색 트리균형 이진트리AVL 트리레드-블랙 트리Map, Set힙 #0. 개념1. 트리? [정의] : 트리는 1:n 관계의webddevys.tistory.com완전 이진트리는 이진트리의 한 종류로, 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있으며, 노드의 삽입 순서는 왼쪽에서 오른쪽 순서입니다. 2. LCA(Least Common Acestor) [BOJ알고리즘, C++]#11437_LCA#1. 문제 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1..

#1. 문제 https://www.acmicpc.net/problem/1976   #2. 풀이 1. BFS [자료구조]#6_그래프#0. 개념 1. 그래프?[정의] : 그래프는 노드와 간선들의 집합으로 이루어진 비 선형 자료구조입니다. 그래프의 노드들은 간선을 통해 연결되어 일종의 네트워크를 형성합니다. 그래프는 노드와webddevys.tistory.comBFS는 그래프의 모든 정점을 탐색하는 방법 중 하나로, 인접한 정점들을 우선 탐색하는 방법입니다. 일반적으로, BFS는 큐 자료구조를 활용하여 구현됩니다. 2. 시작 정점을 기준으로 BFS 수행, 그리고 방문 여부 체크!먼저, 주어진 경로의 시작 정점으로부터 BFS를 수행합니다. 이때, 방문한 정점들에 대하여 방문 여부를 체크해 줍니다.주의할 점으로 "..

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

#1. 문제 https://www.acmicpc.net/problem/2644   #2. 풀이 1. BFS 최단 경로 [알고리즘]#2_길 찾기 알고리즘#1. 개념 1. 길 찾기 알고리즘[정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구webddevys.tistory.comBFS는 그래프의 모든 정점을 탐색하는 방법 중 하나로, 현재 정점의 인접한 정점들을 우선 탐색하는 방법입니다. 일반적으로, BFS는 큐 자료구조를 활용하여 구현합니다.최단 경로 알고리즘은 가중치 그래프에서 두 정점 사이의 경로들 중 가중치의 합이 최소가 되는 경로를 찾는 알고리즘입니다. 이때, 음수 가중치를 갖는 간선이 없고, 모..

#1. 문제https://www.acmicpc.net/problem/14426  #2. 풀이 1. Trie 검색 트리 [자료구조]#8_Trie 검색 트리#1. 개념 트라이(Trie)는 검색 트리의 일종으로, 주로 문자열 검색에 사용되는 자료구조입니다. 트라이 검색 트리의 각 노드는 문자열의 특정 문자를 나타내며, 자식 노드에 대한 링크(배열 혹은webddevys.tistory.com#include #include using namespace std;// 트라이 노드 정의struct TrieNode { unordered_map children; // 자식 노드를 저장하기 위한 맵 bool isEnd; // 단어의 끝을 표시하는 플래그 TrieNode() : isEnd(false) {} //..

#1. 문제 https://www.acmicpc.net/problem/2630   #2. 풀이 1. 분할-정복 알고리즘 [알고리즘]#4_분할-정복 알고리즘[알고리즘]#4_분할-정복 알고리즘 분할-정복 알고리즘에 대해 알아보겠습니다. Overview 개념 예제 #0. 개념 1. 분할 정복 알고리즘 분할 정복 알고리즘은 먼저 전체 문제를 원래 문제와 유사하지만webddevys.tistory.com분할-정복 알고리즘은 하나의 문제를 여러 하위 부분 문제들로 분할하여, 재귀적으로 이를 해결하고 그 결과 값들을 병합하여 최적해를 찾아내는 최적화 기법 중 하나입니다. 2. 4개로 분할, 그리고 재귀 호출먼저, 병합(탐색 종료) 조건을 설정합니다. 종료 조건은 색종이 크기가 1이 되거나, 현재 크기의 색종이 칸들이 ..

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