문제 풀이

#1. 문제https://school.programmers.co.kr/learn/courses/30/lessons/12927  #2. 풀이 1. 우선순위 큐 [자료구조]#7_우선순위 큐[자료구조]#7_우선순위 큐 우선순위 큐 자료구조에 대해 알아보겠습니다. Overview 개념 구현 참고 #0. 개념 1. 우선순위 큐 정의 : 우선순위 큐(Priority Queue)는 원소들이 우선순위에 따라 정렬된 연결webddevys.tistory.com우선순위 큐는 각 항목에 우선순위를 부여하고, 우선순위가 가장 높은 항목부터 차례대로 제거되는 자료구조입니다. 일반적으로, 우선순위 큐는 힙 자료구조로 구현되며, 우선순위 기준에 따라서 최소 힙 혹은 최대 힙을 구성합니다. 따라서, 우선순위 큐는 삽입/삭제/탐색 작업..

#1. 문제https://school.programmers.co.kr/learn/courses/30/lessons/12979  #2. 풀이 1. 마지막 최대 범위 기억하고, 커버하지 못한 영역에 대한 처리!먼저, 현재 기지국이 커버 가능한 범위의 최소 값과 최대 값을 찾습니다.이전 기지국이 커버한 최대 값과 현재 기지국 범위의 최소 값을 비교하고, 아직 커버하지 못한 영역이 존재한다면 " (uncoveredLength + 2*w) / (2*w + 1)" 만큼 기지국을 증설해 줍니다. 그리고, 마지막 커버한 최대 값을 현재 기지국 범위의 최대 값으로 업데이트해줍니다.모든 작업을 마치고, 마지막 기지국 이후 커버하지 못하고 남은 영역에 대한 추가적인 처리 이후, 증설할 기지국 개수를 반환해 줍니다.  #3...

#1. 문제https://school.programmers.co.kr/learn/courses/30/lessons/42884  #2. 풀이 1. 우선순위 큐 [자료구조]#7_우선순위 큐[자료구조]#7_우선순위 큐 우선순위 큐 자료구조에 대해 알아보겠습니다. Overview 개념 구현 참고 #0. 개념 1. 우선순위 큐 정의 : 우선순위 큐(Priority Queue)는 원소들이 우선순위에 따라 정렬된 연결webddevys.tistory.com우선순위 큐는 각 항목에 우선순위를 부여하고, 우선순위가 가장 높은 항목이 먼저 제거되는 특징을 갖습니다. 일반적으로, 우선순위 큐는 힙 자료구조를 통해 구현되며, 내부적으로 반 정렬된 상태를 유지하는 것이 특징입니다. 2. 진출 시점을 기준으로 최소 힙을 구성하고,..

#1. 문제https://www.acmicpc.net/problem/3190  #2. 풀이 1. deque [Basic C++] #68_deque[Basic C++] #68_deque C++의 STL에서 제공하는 deque 컨테이너에 대해 알아보겠습니다. Overview 개념 선언 멤버 함수 예제 #0. 개념 1. 덱? [자료 구조]#0_선형 자료구조 [자료 구조] #0_선형 자료구조 선형 자webddevys.tistory.comC++의 STL에서 제공하는 deque 컨테이너는 양방향 자료구조로 구현되어 컨테이너의 양쪽 끝에서 삽입/삭제 연산을 모두 활용할 수 있는 특징이 있습니다.  2. map [Basic C++] #38_map, 연관 컨테이너#1. 개념 1. map [정의] : C++의 STL에서 ..

#1. 문제https://www.acmicpc.net/problem/1149  #2. 풀이 1. DP [알고리즘]#5_동적 계획법[알고리즘]#5_동적 계획법 동적 계획 알고리즘에 대해 알아보겠습니다. Overview 개념 예제 #0. 개념 1. 동적 계획법(Dynamic Programming) 동적 계획법은 최적화 문제를 해결하는 데 사용되는 알고리즘 디webddevys.tistory.com동적 프로그래밍은 문제에 주어진 입력 크기에 따라 중복되는 하위 문제를 재귀적으로 해결하고, 이 결과 값들을 기억하는 것으로 중복 계산을 피해 최적화를 수행하고 효율적으로 최적해를 찾아냅니다.  2. 현재 문제에 대한 세 가지 경우!먼저, 현재 집에 대하여 3가지 경우에 대한 최소 비용을 각각 기억해 줍니다. 이를 위..

#1. 문제https://www.acmicpc.net/problem/11779  #2. 풀이 1. 최단 경로 알고리즘 [알고리즘]#2_길 찾기 알고리즘#1. 개념 1. 길 찾기 알고리즘[정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구webddevys.tistory.com길 찾기 알고리즘은 가중치 그래프 내 출발점에서 도착점 사이의 경로 중 가중치의 합이 최소가 되는 경로를 찾는 아알고리즘입니다. 대표적인 최단 경로 알고리즘으로 다익스트라, 벨만-포드, 그리고 플로이드-워셜 알고리즘 등이 있습니다. 2. 다익스트라 [알고리즘]#2_길 찾기 알고리즘#1. 개념 1. 길 찾기 알고리즘[정의] : 길 찾..

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

#1. 문제https://www.acmicpc.net/problem/1219  #2. 풀이 1. 벨만-포드 알고리즘 [알고리즘]#2_길 찾기 알고리즘#1. 개념 1. 길 찾기 알고리즘[정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구webddevys.tistory.com벨만-포드 알고리즘은 음수 가중치를 포함하는 그래프에서 '단일-출발' 혹은 '단일-쌍' 최단 경로를 구하는 알고리즘입니다. 일반적으로, 벨만-포드 알고리즘은 간선 목록 순회 N-1번 + 순환 여부 검사 N번으로 구현됩니다. 벨만-포드 알고리즘의 시간 복잡도는 O(|E| x |V|)으로 상수 시간입니다.  2. 최단 경로가 아니라, 최..

#1. 문제https://www.acmicpc.net/problem/2512  #2. 풀이 1. 이분 탐색 [알고리즘]#1_이분 탐색(Binary Search)#0. 개념 1. 이분 탐색? [정의] : 이분 탐색은 정렬된 배열에서 특정 값을 찾기위해 사용되는 탐색 알고리즘입니다. [동작 방식] 1. 먼저, 배열의 왼쪽 경계와 오른쪽 경계를 설정합니다. 2. 중간 값webddevys.tistory.com이분 탐색은 주어진 정렬된 배열에서 특정 값을 찾기 위해 활용하는 탐색 알고리즘입니다. 주어진 배열에서 왼쪽 경계와 오른쪽 경계를 설정하고, 이 중간 값을 찾고자 하는 값과 비교하며 왼쪽 경계 혹은 오른쪽 경계를 수정하며 최종적으로 중간 값이 찾고자 하는 값과 같을 때까지 이 작업을 반복합니다.  2. 요청..

#1. 문제https://www.acmicpc.net/problem/1613  #2. 풀이 1. 플로이드-워셜 알고리즘 [알고리즘]#2_길 찾기 알고리즘#1. 개념 1. 길 찾기 알고리즘[정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구webddevys.tistory.com플로이드-워셜 알고리즘은 음수 가중치를 포함한 그래프에서 '전체-쌍' 최단 경로를 찾는 알고리즘입니다. 특히, 주어진 문제에서 '경유 정점' 혹은 전체-쌍과 그래프 순환 여부에 대해서 언급할 경우, 플로이드-워셜 알고리즘 활용 가능성이 높아집니다.  3. 전체-쌍 관계? 플로이드-워셜! 그래프 구성 시 두 정점 사이의 선행 관계를..