전체 글 (645) 썸네일형 리스트형 이분 매칭 알고리즘 ( JAVA),열혈강호1,2,3 문제 이분 매칭 알고리즘이란 용량이 1인 이분 그래프에서 최대로 매칭 할수 있는 수를 구하는 알고리즘이다. 기본적으로 DFS알고리즘을 사용한다. 알고리즘 매커니즘 기본 적으로 1~N 노드 까지 DFS 탐색을한다. 이때 각각의 노드마다 Dfs탐색을 한다. 1. 현재 here 노드에서 연결된 there 노드가 방문하지않았으면 there은 here과 이어젔다고 표시한후 true를 반환 2. 만약 there이 누군가와 연결되었다면 there과 연결한 간선을 다시 Dfs탐색하여 다른것과 매칭 할수 있는지 탐색 만약 할수 있다면 here과 there을 이어준다. 그리고 true를 반환한다. 3. 위에 1, 2 번으로 이을수 없다면 false를 반환한다. 4. 1 2 3 을 1~N 번 노드 까지 반복한다. 그때마다 Dfs.. Web 태그들 공부 파일 include 방법 root 경로 저장하기 a 태그 예시 var= "act" value="logout" 와 같은 효과 로그아웃 ssafy_id 라는 쿠키를 불러오고 값이 null 이 아닐경우 ne 는 != 와 같고 eq 는 == 과 같다. 널이 아닌경우에는 saveid 쿠키에 저장된 id를 지정하고 idck 를 checked="checked" 로 지정해 항상 check되도록 유지해준다. html 내에서 함수를 지정할때 form 태그를 이용해서 form 안의 많은 정보들을 한번에 action에 다가 보낼수 있다. hidden을 이용해서 어떠한 정보를 보이지 않게 숨겨서 보낼 수 있다. 버튼 태그를 누루면 onclick 을 이용해서 script 의 함수들을 호출한다. sumbit을 사용하면 actoin.. JSTL JSTL 사용하기 import 해주고 prefic="c" 로 고정해준다 보통 c로 사용하고 꼭 c일 필요는 없다. 변수지원 set : JSP에서 사용될 변수를 설정한다. remove : 설정한 변수를 제거한다. 흐름제어 if : 조건에 따라 내부 코드를 수행한다. choose : 다중 조건을 처리할 때 사용한다. forEach : 컬렉션이나 Map의 각 항목을 처리할 때 사용한다. forTokens : 구분자로 분리된 각각의 토큰을 처리할 때 사용한다. URL 처리 import : URL을 사용하여 다른 자원의 결과를 삽입한다. redirect : 지정한 경로로 리다이렉트 한다. url : URL을 재작성 한다. 기타 태그 cathch : 익셉션 처리에 사용된다. out : JspWriter에 내용을 알.. web공부 pageContext - 현재 페이지의 프로세싱과 상응하는 PageContext instance. page Scope - pageScope page scope에 저장된 객체를 추출해서 출력할 때 사용. requestScope- request scope에 저장된 객체를 추출해서 출력할 때 사용. sessionScope - session scope에 저장된 객체를 추출해서 출력할 때 사용 applicationScope - application scope에 저장된 객체를 추출해서 출력할 때 사용 param - ServleRequest.getParameter(String)을 통해 요청 정보를 추출할 때 사용 paramValues - ServletRequest.getParameterValues(String)을 통.. 포드-폴커슨 인접리스트 구현하기 JAVA 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 package 개인공부; import java.util.ArrayList; import 개인공부.포드폴커슨_인접리스트.Edge; public class 포드폴커슨_인접리스트 { static class Edge { int target, capacity, flow; // 역방향 정보를 넣을 곳 Edge reverse; public Edge(int target, int capacity, int flow) { super(); this.target .. 네트워크 유량 ( network flow) / 포드 - 풀커슨 알고리즘 JAVA network flow는 실세계에서 적용이 가능한 유명한 알고리즘이다. network flow를 이해하기 위해서는 먼저 몇가지 용어 정리가 필요하다. A -> B 로가는 네트워크에 대해서 최대 x라는 트래픽으로 보낼 수 있다면 capactiy(a,b) = x 가된다. 즉 a->b로 보낼 수 있는 최대 용량은 x라는 뜻이다. 만약 a->b에서 실제 y라는 트래픽이 발생한다면 flow(a,b) = y 가된다. 즉 a->b로가는 유량은 y라고 한다. 여기서 몇가지 속성을 알아보자 1. 용량 제한 속성 flow(u,v) 0 을 만족하는 u v 간선을 경로라고 생각하고 BFS 너비우선 탐색으로 경로를 탐색한다. 3. 만약 경로가 없으면 알고리즘은 종료한다. 4. 만약 경로가 존재한다면 경로에서 가장작은 flow .. 백준 : 1507 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다. 도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다. 강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로 www.acmicpc.net 문제에 주어진 값들이 플로이드 와샬을 거친값이라는 것을 안다면 접근이 쉬워진다. 만약 주어진값이 와샬이 아니라면 최소의 간선으로 최소.. 백준 solved 플레달성. 코딩테스트를 위해서 온라인 저지를 시작하지 4개월차가 다되간다. 문제를 풀면서 모르는것 투성이였지만 등급이 올라가니 문제푸는 맛도 쏠쏠하다. 앞으로도 열심히 공부해야겠다. 이전 1 ··· 61 62 63 64 65 66 67 ··· 81 다음
