Study
-
템플릿 메서드 패턴: Segment TreeStudy/Java 2023. 10. 13. 01:41
책 Effective Java의 아이템 20에서 '템플릿 메서드 패턴'을 간단하게 소개하는 부분이 있다. 인터페이스로 타입을 정의하고, 추상 클래스에 다른 하위 클래스에서 공통적으로 정의될 메서드를 모아서 하위 클래스의 골격으로 사용하는 것이다. 글로만 봤을 때는 이 패턴이 왜 좋은지 크게 와닿지 않아서 최근에 알고리즘 문제(BOJ10868, BOJ2042)를 풀기 위해 공부했던 Segment Tree에 이 패턴을 적용해서 만들어 볼 수 있을 것 같아서 구현해보았다. 먼저 인터페이스에 들어갈 메서드가 어떤 것이 있을 지 생각해봤다. public interface SegmentTree { Object[] getTree(); void update(int idx, Object diff); Obj..
-
equals() 메서드의 유효성 단위 테스트Study/Java 2023. 9. 23. 11:15
오늘(9월 22일) 책 Effective Java에서는 equals() 메서드에 관한 부분을 읽었다. 한 번 읽고는 잘 이해가 되지 않는 부분들이 있어서 같은 내용을 두 세번씩은 더 읽었던 것 같다. 아이템 제목은 '아이템 10. equals는 일반 규약을 지켜 재정의하라'였다. 내용에서는 equals() 메서드를 만들 때 지켜야하는 몇 가지 규칙들에 대해 자세히 설명한다. 그 규칙들은 equivalance class(동치류)의 정의로부터 오는 것들인데, 그것들의 단위 테스트를 작성해서 실행해보라는 굵은 글씨를 그냥 지나치기가 좀 그래서, 테스트 코드를 연습할 겸 간단하게 만들어보았다. 단위 테스트를 실행할 클래스는 오늘 풀었던 BOJ 알고리즘 문제 2887번: 행성 터널에서 만들었던 클래스를 사용했다...
-
Kruskal's algorithm : 최소 신장 트리(MST, Minimum Spanning Tree) 찾기Study/Algorithm 2023. 8. 31. 16:30
BOJ 문제 최소 스패닝 트리(1197), 도시 분할 계획(1647), 네트워크 연결(1922) 등의 문제들을 풀기 위해 Kruskal Algorithm을 공부했다. 1. 알고리즘 최소 신장 트리(MST, Minimum Spanning Tree)는 가중치(weight)가 있는 간선(edge)들을 갖고 있는 그래프에서, 그래프의 모든 정점(vertex)들을 포함한 트리(tree)이면서, 그 트리가 가진 모든 간선의 가중치의 합이 가장 작게 되는 그래프를 말한다. 예를 들면, 아래의 그래프 G에서 모든 정점을 포함한 트리는 가운데의 그래프에서 빨간 간선들로 이루어진 그래프이고, 그러한 트리는 여러 개가 있을 수 있다.(모든 정점을 포함한 트리를 spanning tree라고 한다.) 하지만, 간선의 가중치의 ..