Algorithm/Study13 플로이드 워셜 1. 코드 예제 package com.problem.BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BJ_11404 { static int n, m; static int[][] map; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; n = Integer.pars.. 2024. 3. 29. 최장 증가 부분 수열 (LIS) 1. 문제 - {3, 2, 6, 4, 5, 1} 다음과 같은 배열에서 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분은? (ex. 2, 4, 5) - 부분집합 사용 시 시간복잡도 : O(2 ^ N) - 참고 : https://chanhuiseok.github.io/posts/algo-49/ 알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘 컴퓨터/IT/알고리즘 정리 블로그 chanhuiseok.github.io - 참고 : https://source-sc.tistory.com/14 [1][LIS : 최장증가수열 알고리즘] - DP 를 이용한 알고리즘 (Longest Increasing Subsequence Algorithm) LIS Algorithm LIS 알고리즘 (Longest Increa.. 2024. 3. 27. Knapsack 1. 0-1 Knapsack 유형 - 배낭에 물건을 통째로 담아야 하는 문제 - 물건을 쪼갤 수 없는 경우 - 참고 : https://howudong.tistory.com/106 배낭 문제(KnapSack Problem) 그림으로 쉽게 이해하기 배낭 알고리즘이란? 배낭 문제(Knapsack)는 n개의 물건과 배낭 있을 때, 각 물건에는 가치와 무게가 존재한다. 또한 각 물건은 1개씩만 있다. 배낭에는 담을 수 있는 최대 용량이 존재한다. 이러한 howudong.tistory.com 2. Fractional Knapsack - 물건을 부분적으로 담는 것이 허용되는 문제 - 물건을 쪼갤 수 있는 경우 3. 배낭 문제 해결 (물건, 물건의 무게, 물건의 가치, 배낭의 용량) - 점화식 - 코드 예제 impor.. 2024. 3. 26. 그래프 1. 그래프의 종류 - 정점 중심으로 해결 : 인접 행렬, 인접 리스트 >> 최소 신장트리 : 프림, 최단 경로 : 다익스트라 - 간선 중심으로 해결 : 간선 리스트 >> 최소 신장 트리 : 크루스칼, 최단 경로 : 벨만포드 ※ 선형 자료구조(1 : 1), 비선형 자료구조(1 : N or N : N) 2. 그래프 - 정점 : 그래프의 구성요소로 하나의 연결점 - 간선 : 두 정점을 연결하는 선 - 차수 : 정점에 연결된 간선의 수 (인접 정점의 수) - 트리도 그래프이다. - 종류 3. 인접 행렬 - V x V 정방 행렬 - 행 번호와 열 번호는 그래프의 정점에 대응 - 두 정점이 인접되어 있으면 1, 그렇지 않으면 0으로 표현 - 보통 2차원 배열로 생성 - 메모리 초과 위험 4. 인접 리스트 - Ar.. 2024. 2. 15. 이전 1 2 3 4 다음
