분류 전체보기 834

DP

다이나믹 프로그래밍(Dynamic Programming) DP, 동적 계획법 Overlapping Subproblem 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다 문제를 작은 문제로 쪼갤 수 있다 Optimal Substructure 문제의 정답을 작은 문제의 정답에서 구할 수 있다 두 번 이상 반복 계산되는 부분 문제들의 답을 미리 저장함으로써 속도의 향상을 꾀하는 알고리즘 설계 기법 기본 전략은 문제를 작은 부분 문제로 나누는 것에서 부터 시작한다 작은 부분 문제를 해결한 결과로 큰 문제를 해결할 수 있다 특징은 중복되는 부분 문제들이 있다는 것 적용 방법 문제를 더 작은 부분 문제로 나눈다 중복되는 작은 부분 문제는 한 번만 계산해서 그 결과를 저장 중복되는 작은 부분 문제들은 여러 번 계산하..

algorithm/DP 2019.11.16

BOJ-12865

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net 일반적인 배낭 문제로 1차원 DP로 풀이가 가능했다. D[무게] = {최대Value} 입력받은 V, W 값을 기준으로 각 무게별 Item을 추가했을때 최대 가치를 구하도록 했음. 코드 import java.io.BufferedReader; import java.io.FileInpu..

algorithm/DP 2019.11.15

OpenFaaS 설치하기

https://github.com/openfaas/faas openfaas/faas OpenFaaS - Serverless Functions Made Simple. Contribute to openfaas/faas development by creating an account on GitHub. github.com OpenFaaS는 쿠버네티스 클러스터에 도커 컨테이너의 기능을 구현하는 서버리스 모델이다. 이러한 쿠버네티스 클러스터를 배치하면, 더 이상 서비스 업체 종속에 대해서는 아무런 걱정도 할 필요가 없을 것이다. 물론 쿠버네티스의 클러스터의 자동 확장 없이는 비용 절감 효과를 얻지 못하겠지만, 새로운 프로그래밍 패러다임을 사용하면서 배치의 유연성을 확보할 수는 있을 것이다. 1. 설치하기. 1) P..

OpenSource 2019.11.05

Boj 13418

https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1≤N≤1,000)과 도로의 개수 M(1≤M≤n*(n-1)/2) 이 주어진다. 입력의 두 번째 줄부터 M+1개의 줄에는 A, B(1≤ A,B ≤ N), C 가 주어진다. 이는 A와 B 건물에 연결된 도로가 있다는 뜻이며, C는 0(오르막길) 또는 1(내리막길)의 값을 가진다. 같은 경로 상에 2개 이상의 도로가 주어지는 경우는 없으며, 입 www.acmicpc.net 문제를 이해하는데 한참 걸렸다. 그냥 MST(크루스칼)로 푸는 문제인데.. 단 예외 조건이 있다, 오르막이 0, 내리막이 1로 ..

algorithm/그래프 2019.10.17

boj-11266 단절점

절단점(cut vertex): 어떤 무향 그래프의 절단점이란 이 점과 인접한 간선들을 모두 지웠을 때 해당 컴포넌트가 2개 이상으로 나뉘어지는 정점을 말한다. 위 그래프에서 1, 3, 5 정점이 각각 절단점이다. 각 지점 별로 탐색하면서, 자식의 depth가 자신의 depth보다 크거나 같다면 단절점이다. root의 경우 child node가 2이상이면 단절점이다. DFS static int dfs(int here, int d, boolean root) { D[here] = d; int ret = D[here]; int child = 0; for (int there: VT[here]) { if(D[there]==0) { child++; int df = dfs(there, d+1, false); if(!r..

algorithm/그래프 2019.10.07

Algosopt-FireTruck

https://algospot.com/judge/problem/read/FIRETRUCKS algospot.com :: FIRETRUCKS 소방차 문제 정보 문제 한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기 위해 가능한 한 빠르게 소방차를 파견해야 합니다. 서울 시내에는 m개의 소방서가 있습니다. 화재 장소에서 가장 가까운 소방서에서 소방차를 보낸다고 할 때, 각 화재 장소에 소방차가 도달하기까지 걸리는 시간의 합을 계산하는 프로그램을 작성하세요. 각 소방서에는 소방차가 충분 algospot.com 다익스트라의 다른 시각을 볼수 있는 문제로, 기본 사상인 : 한 점에서 시작하여, 여러점의..

algorithm/그래프 2019.09.23