분류 전체보기45 [BOJ] [JAVA] 1753번 최단경로 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 그래프의 시작 지점에서 각 정점으로 갈 수 있는 최단 거리를 계산하는 문제다. 다익스트라 알고리즘을 활용해서 해결할 수 있다. 처음에는 인접 행렬을 이용해보려 했지만, V 2024. 2. 15. [알고리즘] [14] 그래프 1. 그래프 아이템 (사물 또는 추상적 개념)들 사이의 연결 관계를 표현한 것 정점 (Vertex) : 그래프의 구성 요소로 하나의 연결점 간선 (Edge) : 두 정점을 연결하는 선 차수 (Degree) : 정점에 연결된 간선의 수 그래프는 정점과 간선의 집합으로 구성된 자료구조 선형 자료구조나 트리 자료구조로 표현하기 어려운 N 대 N 관계의 원소들을 표현하기 용이하다. 그래프 유형 무향 그래프(Undirected Graph) : 최대 간선의 개수는 V*(V - 1) / 2이다. 유향 그래프 (Directed Graph) 가중치 그래프 (Weighted Graph) 사이클 없는 방향 그래프 (DAG, Directed Acyclic Graph) 완전 그래프 : 정점들에 대해 가능한 모든 간선을 가지는 .. 2024. 2. 15. [알고리즘] [13] 분할정복 백트래킹 1. 분할 정복 기법 분할 (Devide), 정복 (Conquer), 통합 (Combine)의 설계 전략을 가진다. 병합 정렬, 퀵 정렬이 분할 정복 정렬 방식이다. Top-down approach >> 크기가 작은 부분 문제로 정의(분할)한 후 부분문제의 해를 구한다(정복). >> 필요하다면 부분 문제의 해를 결합하여 전체 문제의 해를 구한다. 거듭 제곱 C^n에서 n이 짝수인 경우와 홀수인 경우에 대해 각각 분할하여 계산한다. // a의 n 제곱을 1000000으로 나눈 나머지 계산 함수 // 반복문을 이용한 방법 static long pow(long a, int n) { long result = 1; while (n > 0) { if (n % 2 == 1) { result *= a; result %.. 2024. 2. 14. [알고리즘] [12] 탐욕 알고리즘 1. 탐욕 (Greedy) 알고리즘 최적 해를 구하는 근시안적 방법이다. 최적화 문제 (optimization) : 가능한 해들 중 가장 좋은 해를 찾는 문제 여러 경우 중 하나를 택할 때마다 그 순간의 최적을 선택해 나가며 해답을 찾는 방식이다. 지역적으로는 최적이지만 최종 답이 최적이라는 보장은 없다. 2. 배낭 짐싸기 (Knapsack) 최대 무게를 넘지 않으며 가장 큰 값어치를 얻어야 하는 문제 0 -1 Knapsack : 물건을 쪼개지 않고 통째로 담아야 하는 문제 Fractional Knapsack : 물건을 쪼개어 부분적으로 담을 수 있는 문제 0 - 1 Knapsack 완전 검색 가능한 모든 부분집합 중 최대 무게를 넘지 않는 경우에 대해 값어치를 구한다. 크기가 n인 부분집합의 수는 2ª.. 2024. 2. 13. 이전 1 2 3 4 5 6 ··· 12 다음
