이전에 게시했던 최단 거리문제가 코드가 동일하다. 단지 출력하는 부분의 코드만 살짝 수정해주면된다. 즉, 최소비용문제 또한 다익스트라 알고리즘으로 풀수 있다. 백준-1916번 최소비용 구하기 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091package graph; import java.util.ArrayList;import java.util.Iterator;import java.util.PriorityQueue;import java.util.Sc..

백준-1753번 최단거리 시작정점으로부터 모든 정점까지의 최단거리를 구하는 문제이다. 이 문제는 BFS와 비슷한 다익스트라 알고리즘으로 풀 수 있는 문제이다. 다익스트라 알고리즘은 방향이있는 가중치 그래프에서 어떤 정점에서 다른 정점까지의 최단 거리를 구할 수 있는 알고리즘이다.(음수간선을 포함하는 그래프는 다익스트라 알고리즘으로 풀 수 없다.) 위의 그림과 같은 과정으로 다익스트라 알고리즘이 구동됩니다. ( 코드에서는 방문여부에 관한 check배열은 선언하지 않았음 굳이 없어도 돌아감) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656..

1. 위상정렬위상정렬의 조건위상정렬이 가능하려면 DAG 그래프여야 한다. DAG란 Directed Acyclic Graph의 약자로 방향성이 있고, 사이클이 없는 그래프를 의미한다. 진입차수를 이용한 위상정렬 1.모든 정점의 선행 필요조건 관계를 따라 그래프를 그린다.(방향 그래프 완성)2. 각 정점에 대해 indegree를 센다.(자신으로 들어오는 간선의 개수)3. indegree가 0인 일을 모두 찾아 큐에 넣는다4. 큐에서 정점 하나를 꺼낸다.(위상정렬의 결과 출력을 위해 이때 꺼내진 정점을 출력하면 된다.)5. 방금 꺼낸 정점에 연결된 모든 정점들의 indegree를 1씩 감소시킨다.6. indegree가 감소된 정점들 중 indegree가 0인 정점이 있으면 큐에 넣어준다.7. 큐가 빌 때까지 ..

그래프 DFS(깊이우선탐색) 와 BFS(너비우선탐색) 1. 시작전그래프를 구현하는 방법 중에는 크게 두 가지가 있습니다. 첫번째는 인접행렬을 이용하는 방법이고, 두번째는 인접리스트를 이용하는 방법입니다. 이 두가지 방법중 인접행렬을 이용한 DFS 와 BFS를 구현해보겠습니다. 2.DFS(깊이우선탐색) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182package graph; import java.util.Stack; public class DFS { class Vertex{ pu..

스프링의 오브젝트와 의존관계에 관한 용어 정리 1. 관심사의 분리책임이 다른 코드를 분리해서 두 개의 클래스로 만드는 것.ex) 보통의 DAO 클래스에서 DB커넥션 관련 코드와 DB에서 실제로 수행되는 statement, resultset 등의 코드가 혼재되어있다. 즉, db커넥션관련 책임과 db에서 실제로 수행되는 코드의 책임은 엄연히 다른 책임을 가진다. 이런 코드를 관심사의 분리로써 db커넥션관리 코드를 별도의 class로 분리하여 DAO내에서는 DB커넥션과 관련된 코드자체를 분리해내는 작업(리팩토링)을 한다. 결론적으로 관심이 같은 것은 한 객체 또는 친한 객체로 관심이 다른 것은 가능한 멀리 떨어져 서로 영향을 주지 않게 코드를 분리&확장하는 이론이다. 2. 전략패턴자신의 기능 맥락에서, 필요에..

ajax를 이용한 실시간 아이디 중복 체크 구현 1. 개발 환경 1. Spring 4.3.7 2. tomcat 8.0 3. oracle 2. 프로젝트 구조 3. UserDTO, UserDAO 구현12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152package com.web.nuri.user; public class UserDTO { private String id; private String pw; private String pwConfirm; private String nickName; private int grade; private int isAdmin; public String g..