문제 https://www.acmicpc.net/problem/1506 문제해설 모든 도시를 경찰서의 통제하에 두려고 한다. 도시끼리 이동할 수 있다면 한 군데에만 경찰서를 세우면 된다. 경찰서를 짓는 비용은 도시마다 다르며 조건을 만족하여 모든 도시를 경찰의 통제하에 두는 최소 비용을 구하면 된다. 문제풀이 SCC를 이용하여 한 SCC에 속해...

문제 https://www.acmicpc.net/problem/14675 문제해설 트리가 주어지고 트리의 정점과 간선에 대해서 단절점인지 단절선인지 판별하는 문제이다. 문제풀이 이 문제는 사실 단절점과 단절선을 구할 필요가 없다. 왜냐하면 트리는 리프 노드를 빼고는 전부 단절점이 되고 트리의 모든 간선들은 다 단절선이기 때문이다. 그래서 단절...

No converter found for return value of type 오류의 전문은 Resolved [org.springframework.http.converter.HttpMessageNotWritableException: No converter found for return value of type: class com.teamkph.kph....

문제 https://www.acmicpc.net/problem/2152 문제해설 길어서 링크 참조 문제풀이 백준 ATM 문제와 유사한 문제다. ATM 문제에서 시작과 도착지점을 정해주고 비용 대신 노드의 개수로 바꾸면 풀린다. 참고로 ATM 문제의 풀이는 이 곳에서 볼 수 있다. ATM 문제 풀이에서 자세히 설명했듯이 SCC를 구해 SCC로 ...

문제 https://www.acmicpc.net/problem/4013 문제해설 길어서 링크 참조 문제풀이 이 문제는 SCC와 위상정렬 BFS가 섞여있는 문제이다. 보통 SCC가 심화되면 위상정렬과 엮이게 된다. 왜냐하면 SCC들을 묶어서 그래프를 새로 만들게 되면 그 그래프는 사이클이 없는 방향 그래프가 되기 때문이다. 이 문제를 풀기 위해...

SCC? Strong Connected Component 방향 그래프에서 어떤 그룹 X에 있는 임의의 두 정점 A,B에 대해서  항상 A->B로 가는 경로가 존재한다면 그 그룹을 SCC라 칭한다. 글로만 봐서는 무슨 소린지 잘 모르겠다 위의 그림을 보자 예를 들어 1과 3을 잡아보면 1에서 3으로 가는 경로가 존재하고 3에서 1로 가는 경...

단절선을 설명하기 전에 단절점에 대해 모른다면 이 글 을 먼저 읽어야 한다. 단절선이란? 단절선이란 단절점과 유사하다. 어느 한 선을 제거했을 때 그래프가 여러개로 나누어지는 선을 단절선이라 한다. 단절선 어떻게 찾을까? 단절점과 굉장히 비슷한 것에서 알 수 있듯이 찾는 방법도 거의 같다. 다만 다른 점이 3가지가 있다. 부모 정점은...

단절점이란? 단절점이란 굉장히 단순한 개념이다. 어떤 한 정점를 지운다고 가정했을 때 그래프가 여러개로 나뉜다면 단절점이다. 다른 말로는 그 정점이 없이는 모든 정점들을 한번에 방문할 수 없는 것이다. 단절점 어떻게 찾을까? 우선 단절점에 대해 이야기하기 전에 DST라는 것을 알아보자. DST는 DFS Spanning Tree로 DFS의 방문...

MockMvc란? MockMvc는 어플리케이션을 서버에 배포하지 않고도 스프링 MVC의 테스트를 진행할 수 있게 도와주는 클래스이다. POST 테스트 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 @Autowired private MockMvc mockMvc; @Auto...

스프링 테스트 오류 스프링 테스트를 실행하면 시간이 엄청 걸리고 결국 Test events were not received라는 오류가 나는 경우가 있다. 테스트를 인식을 못한 것인데 테스트 어노테이션 @Test를 잘 썼는데도 그렇다면 이 경우에는 인텔리제이의 설정 문제이다. 해결 방법 인텔리제이 설정을 열어 Build, Execution...