Algorithm50 플로이드 워셜 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. 우주신과의 교감(BJ_G3_1774) 1. 문제 링크 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 2. 나의 코드 메모리: 43928KB 시간: 760ms 코드 길이: 3556B 시간 복잡도 : O(N^2) >> 조합 생성 시 설명 - 각각의 노드를 입력 받은 후 조합 알고리즘을 사용하여 각 노드들의 거리를 계산해서 edgeList에 넣어주기 - 리스트 정렬 - 미리 연결된 코드는 union처리 해주기 - 크루스칼 알고리즘을 사용하여 최소 연결 거리 .. 2024. 3. 26. 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 ··· 3 4 5 6 7 8 9 ··· 13 다음
