와드의 블로그

1. 다익스트라 알고리즘이란?다익스트라 알고리즘은 다이나믹 프로그래밍(DP)과 그리디(Greedy) 알고리즘을 바탕으로 하는 최단 경로 탐색 알고리즘입니다. 특정한 하나의 정점(시작점)에서 그래프 내의 다른 모든 정점까지의 최단 거리를 구하는 '단일 출발점 최단 경로(Single-source Shortest Path)' 문제를 해결하는 데 사용됩니다.핵심 원리는 "현재까지 알고 있는 최단 경로를 바탕으로, 아직 방문하지 않은 노드 중 가장 거리가 짧은 노드를 선택해 인접한 노드들의 최단 거리를 계속해서 갱신해 나가는 것"입니다. 한 번 최단 거리가 확정된 노드는 다시 처리하지 않기 때문에 매 단계마다 탐색 범위가 줄어듭니다.2. 알고리즘의 한계점음수 가중치(Negative Weight) 처리 불가: 다익..

문제방향 그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하는 문제입니다. 모든 간선의 가중치는 10 이하의 자연수입니다.입력: 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어집니다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 둘째 줄에는 시작 정점의 번호 K가 주어집니다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 주어집니다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 의미입니다.출력: 첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 시작점 K에서 i번 정점으로 가는 최단 경로의 경로값을 출력합니다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력합니다.링크: h..

문제비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 연속된 부분 수열을 찾는 문제입니다.부분 수열의 합은 k입니다.합이 k인 부분 수열이 여러 개인 경우 길이가 가장 짧은 수열을 찾습니다.길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.입력: 오름차순으로 정렬된 정수 배열 sequence (길이 5 이상 1,000,000 이하), 부분 수열의 합 k출력: 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 담은 배열링크: https://school.programmers.co.kr/learn/courses/30/lessons/178870풀이: 투 포인터를 활용한 부분 합 탐색배열의 길이가 최대 1,000,000이므로 이중 반복문으로 모든 구간의 ..