Algorithm16 [Programmers] 합승 택시 요금 (최단거리) 플로이드-워셜(Floyd-Warshall) import java.util.*; class Solution { int[][] dist; public int solution(int n, int s, int a, int b, int[][] fares) { dist = new int[n+1][n+1]; // 초기 거리 초기화 for(int i = 1; i 2022. 9. 23. [Algorithm] 그래프 탐색(Graph Search) 그래프 탐색 : 하나의 시작점 Node에서 연결된 Node들을 모두 찾는 것 1. 깊이 우선 탐색 (DFS, Depth First Search) 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 (1) DFS의 이해 정점(Vertex) 5에서 시작 정점 4 방문 => loop (5 이미 방문, 1 정점 방문 (재귀)) 정점 1 방문 => loop (4 이미 방문, 2 정점 방문 (재귀)) 정점 2 방문 => loop (5 이미 방문, 1 이미 방문) 정점 1로 돌아간다 => loop (4 이미 방문, 2 이미 방문, 5 이미 방문) 정점 4로 돌아간다. => loop (5 이미 방문, 1 이미 방문) 정점 5로 돌아간다 => loop (4 이미 방문, 2.. 2022. 2. 12. [Algorithm] 그래프(Graph) 1. 그래프(Graph)란? 정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조 (1) 간선(Edge) 종류 무방향 방향 가중치 (2) 정점의 차수(Degree) 정점 x에 연결된 간선의 수 deg(x) := 정점 x의 차수(degree) (3) 차수의 성질 모든 정점의 차수의 합 = 간선의 개수의 2배 2. 그래프(Graph)를 저장하는 방법 (1) 인접 행렬 (Adjacency Matrix) int[][] adj = int new[V][V] O(V^2) 만큼의 공간 필요 A에서 B로 이동 가능? 가중치 얼마? => O(1) 정점 A에서 갈 수 있는 정점들은? => O(V) ex) V=10만, E=50만 => V^2 = 100억 = 10GB (2) 인접 리스트 (Adjacency List) A.. 2022. 2. 12. [Algorithm] 투 포인터 (Two Pointers) 1. 두 포인터(Two Pointers) 화살표 두 개에 의미를 부여해서 탐색 범위를 압축하는 방법 2. 투 포인터 두 가지 경우 (1) 1차원 배열 위에 2개의 포인터를 만드는 경우 2개의 포인터가 모두 왼쪽에서 시작해서 같은 방향으로 이동 2개의 포인터가 양 끝에서 서로를 향해 이동 (2) 관찰을 통해서 문제에 등장하는 변수 2개의 값을 두 포인터로 표현하는 경우 2. TIP 1차원 배열에서의 "연속 부분 수열" or "순서를 지키며 차례대로" 곱의 최소, ..에 가까운 수 => 이런 단어가 등장하면 Two Pointers 접근을 시도해 볼 가치가 있다. 3. (Example) BOJ 1806 - 부분합 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상 되는 것 중, 가장 짧은 것의 길이를 구.. 2022. 2. 8. [BOJ] 2805번: 나무 자르기 (매개 변수 탐색) 1. 문제 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net (1) 정답의 최대치 정답의 범위: 0 ~ 10억 (Integer type) 잘린 나무의 길이 합 long 타입 사용해야 한다.) 2. 접근 (1) 키워드 체크하기 적어도 M미터의 나무를 집에 가져가기 위해서 절다기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오 (2) 매개 변수 만들어 보기 정답을 "매개 변수(Parameter)"로 만들고 Yes/No 문제(결정 문제)로 바꿔 보기 모든 값에 대.. 2022. 1. 26. [Algorithm] 매개 변수 탐색 (Parametric Search) 1. 매개 변수 탐색 (Parametric Search) 최적화 문제를 결정 문제로 바꾸어 푸는 것이다. 정답을 파라미터로 만들고 결정문제로 바꾸어 푼다 => 이분 탐색의 아이디어 배열이 0과 1만 존재하며 오름차순 인건 보장되지만, 전체 배열은 모른다. 특정 인덱스의 값을 O(T)에 계산 가능할 때, 여기서 0과 1의 경계를 찾아야 한다면? Up-Down 게임 A가 1~1000 사이의 어떤 자연수를 선택 B는 A 한테 "생각한 숫자가 X 이상이야? 라는 질문 A는 맞으면 1, 아니면 0 이라고 대답 최소 횟수로 질문하려면? 하나씩 탐색 : 1000번 탐색, T(탐색시간) => O(T * 1000) 이분 탐색 : log1000 탐색, T(탐색시간) => O(T * log1000) = O(T * 10) *.. 2022. 1. 26. 이전 1 2 3 다음 반응형
