ℹ️ 목차그래프 이론│├── 1. 그래프에 대해서│ ├── 1.1 그래프의 정의│ └── 1.2 핵심 용어│├── 2. 그래프의 표현 방법│ ├── 2.1 인접 행렬 (Adjacency Matrix)│ └── 2.2 인접 리스트 (Adjacency List)│├── 3. 그래프의 종류│ ├── 3.1 방향 그래프 (Directed Graph)│ ├── 3.2 무방향 그래프 (Undirected Graph)│ ├── 3.3 가중치 그래프 (Weighted Graph)│ ├── 3.4 연결 그래프 (Connected Graph)│ ├── 3.5 비순환 그래프 (Acyclic Graph)│ │ └── DAG (Directed Acyclic Graph)│ ├── 3.6..

알고리즘에서 ‘그래프 이론’은 꽤나 큰 파이를 차지하고 있다. 이번에는 이러한 그래프 이론은 무엇인지, 조금 깊게 파헤쳐보고 정리해보려한다.ℹ️ 목차그래프 이론│├── 1. 그래프에 대해서│ ├── 1.1 그래프의 정의│ └── 1.2 핵심 용어│├── 2. 그래프의 표현 방법│ ├── 2.1 인접 행렬 (Adjacency Matrix)│ └── 2.2 인접 리스트 (Adjacency List)│├── 3. 그래프의 종류│ ├── 3.1 방향 그래프 (Directed Graph)│ ├── 3.2 무방향 그래프 (Undirected Graph)│ ├── 3.3 가중치 그래프 (Weighted Graph)│ ├── 3.4 연결 그래프 (Connected Graph)│ ├── ..

Intro어떤 정점으로부터 모든 정점들로의 최단 경로를 구하는 문제는 최단 경로 알고리즘을 적용해서 정해를 구할 수 있다.이 때 사용되는 최단 경로 알고리즘으로는 아래와 같다.다익스트라(Dijkstra) 알고리즘벨만-포드(Bellman-Ford) 알고리즘플로이드-워셜(Floyd-Warshall) 알고리즘아래 표는 최단 경로 알고리즘 3가지의 각 차이점에 대해 참고할 수 있도록 생성형 AI를 통해 생성한 자료구분다익스트라(Dijkstra)벨만-포드(Bellman-Ford)플로이드-워셜(Floyd-Warshall)목적단일 출발점에서 다른 모든 정점까지의 최단 거리단일 출발점에서 다른 모든 정점까지의 최단 거리모든 정점 쌍 간 최단 거리음수 가중치❌ 불가능 (음수 간선 있으면 오동작)✅ 가능✅ 가능음수 사이클..

문제https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이정석적인 구간합 풀이 (투포인터) 접근법문제를 조금 읽어보면 알 수 있듯, 특정 합(k)을 만족하는 구간을 구하는 문제로 구간합을 구하는 알고리즘을 적용해서 풀 수 있다.처음에 떠올린 방법은 투포인터를 활용해서 구간합 조건을 검색하는 방식이였고, 두번째는 누적합이다.만약 '비내림차순'이 아니라 정렬이 되어 있다는 가정이라면 이분탐색을 활용해도 풀 수 있다. 우선 해당 문제의 조건은 간단하다. 만족하는 구간합이 여러 CASE일 경우 아래 조건에 따..