전체 글

싱글턴(singleton)이란 인스턴스를 오직 하나만 생성할 수 있는 클래스를 말한다. 싱글턴의 전형적인 예로는 함수와 같은 무상태 객체나 설계상 유일해야 하는 시스템 컴포넌트를 들 수 있다. 그런데 클래스를 싱글턴으로 만들면 이를 사용하는 클라이언트를 테스트하기가 어려워질 수 있다. 타입을 인스턴스로 정의한 다음 그 인터페이스를 구현해서 만든 싱글턴이 아니라면 싱글턴 인스턴스를 가짜(Mock) 구현으로 대체할 수 없기 때문이다. 싱글턴을 만드는 방식은 보통 둘 중 하나다. 일단 두 방식 모두 생성자는 private으로 감춰두고, 유일한 인스턴스에 접근할 수 있는 수단으로 public static 멤버를 하나 마련해둔다. public static final 필드 방식의 싱글턴 public class El..

IP 인터넷 프로토콜의 역할 지정한 IP 주소(IP Address)에 데이터 전달 네트워크의 노드들은 고유한 IP를 부여받는다 패킷(Packet)이라는 통신 단위로 데이터 전달 IPv4란? TCP/IP에서 활용하는 네트워크 주소체계이다. 네트워크 주소를 총 32 비트로 표현하기 때문에 약 43억 개의 주소를 나타낼 수 있다. IPv4 주소는 이미 모두 소진되었다. 이를 대체할 IPv6가 있다. IPv4 패킷(데이터그램) 구조 20~60 바이트의 크기를 가진 헤더(Header)와 그 뒤에 데이터(Data, Payload)가 담긴다. 헤더에는 라우팅과 데이터그램 전달을 위한 정보가 담기고 데이터에는 전달하고자 하는 정보가 담긴다. IPv4 헤더 구조 VER : 인터넷 프로토콜 버전을 의미한다. HLEN : ..

힙 정렬을 공부하기 전에 힙(Heap)이 무엇인지 알아야 한다. 그리고 힙을 알기 전에는 이진트리(Binary Tree)에 대해서 알고 있을 필요가 있다. 이진 트리는 모든 노드의 자식 노드가 2개 이하인 노드이다. 이진트리로 완전 이진트리를 구성할 수 있는데 별 다른 것은 아니고 이진트리의 노드가 중간에 비어있지 않고 빽빽이 가득 찬 구조를 완전 이진트리라고 한다. 즉 아래도 완전 이진트리라고 할 수 있다. 이제 힙을 알아보자. 힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리이다. 힙에는 최대 힙과 최소 힙이 존재하는데 최대 힙은 부모 노드가 자식 노드보다 큰 힙이라고 할 수 있고 최소 힙은 그 반대이다. 그런데 힙 구조 안에서 특정 노드 때문에 최대 힙 구조가 붕괴..

컴퓨터 프로그래밍에서 로버트 마틴이 2000년대 초반에 명명한 객체 지향 프로그래밍 및 설계의 다섯 가지 기본 원칙이다. 프로그래머가 시간이 지나도 유지 보수와 확장이 쉬운 시스템을 만들고자 할 때 이 원칙들을 함께 적용할 수 있다. - 이 원칙들은 애자일 소프트웨어 개발과 적응적 소프트웨어 개발의 전반적 전략의 일부가 된다. 두문자 약어 개념 S SRP 단일 책임 원칙(Single responsibility principle) O OCP 개방-폐쇄 원칙(Open/closed principle) L LSP 리스코프 치환 원칙(Liskov substitution principle) I ISP 인터페이스 분리 원칙(Interface segregation principle) D DIP 의존관계 역전 원칙(De..

위상 정렬(Topology Sort)는 순서가 정해져 있는 작업들의 수행 순서를 정해주기 위한 알고리즘이다. 예를 들어서 숫자가 하나의 작업이라고 했을 때, 다음과 같이 작업의 순서가 정해져 있다고 가정하자. 1 -> 3 -> 4 3 -> 2 그럼 (1 -> 3 -> 4 -> 2) 또는 (1 -> 3 -> 2 -> 4) 순서로 작업을 수행해야 함을 알 수 있다. 이렇게 정해진 순서를 고려해서 작업의 수행 순서를 결정해주는 알고리즘을 위상 정렬이라고 한다. 주의할 점은 위상 정렬은 DAG(Directed Acyclic Graph) 에만 적용이 가능하다. 위상 정렬이 "작업의 순서를 고려한다"는 점을 생각해보면 당연한 것이다. 사이클이 존재하는 것은 출발 지점이 따로 없다는 것이고 순서도 없다는 의미가 된다..

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 최소 비용 신장 트리를 만들기 위한 대표 알고리즘이라고 할 수 있다. 흔히 여러 개의 도시를 최소한의 비용으로 도로를 설치하고자 할 때 실제로 사용되는 알고리즘이라고 한다. 최소 비용 신장 트리란? [Minimum Spanning Tree] 우선 신장 트리란(Spanning Tree) 그래프의 최소 연결 부분 그래프이다. 특징으로는 모든 정점을 포함해야 한다는 것과 가장 적은 간선 개수로 모든 정점을 연결해야 한다는 특징이 있다. 최소 비용 신장 트리란 신장 트리의 특징을 포함하며, 간선의 가중치를 고려해서 최소한의 비용으로 신장 트리를 구성해야한다는 특징을 가지고 있다. 따라서 구성된 그래프의 간선의 합이 최소여야..

다익스트라는 간선에 가중치가 있을 때 출발 정점에서 도착 정점까지의 최단 거리를 구하는 알고리즘이다. 플루이드 와샬도 최단 거리를 구한다는 점은 동일하다. 하지만 플루이드 와샬은 모든 정점에서 모든 정점까지의 최단 거리를 구한다는 점에서 차이가 있다. 또한 다익스트라는 가장 적은 비용의 간선을 선택하지만 플루이드 와샬은 거쳐가는 정점을 정해서 비용을 비교하고 갱신한다. 그림으로 알고리즘의 진행 과정을 살펴보자. 먼저 다음과 같이 그래프에 대해서 인접 행렬을 초기화한다. 이제 1을 거치지 않는 경로와 1을 거쳐가는 경로의 비용을 비교해서 인접 행렬을 갱신해준다. 다음으로 2를 거치지 않는 경로와 2를 거쳐가는 경로의 비용을 비교해서 갱신한다. 다음으로 3 다음으로 4 다음으로 5 최종 모습 이제 소스 코드..

정적 팩터리와 생성자는 선택적 매개변수가 많을 때 적절히 대응하기 어렵다는 제약이 있다. 점층적 생성자 패턴 (telescoping constructor pattern) public class NutritionFacts { private final int servingSize; private final int servings; ... public NutritionFacts(int servingSize, int servings) { this(servingSize, servings, 0); } public NutritionFacts(int servingSize, int servings, int calories) { this(servingSize, servings, calories, 0); } ... } 점층..

Union find - 합집합을 찾는 대표적인 그래프 알고리즘이다. 합집합 여부를 판별할 수 있기 때문에 서로소 집합 여부도 판별할 수 있어 서로소 집합(Disjoint-set) 알고리즘이라고도 한다. Union find는 여러 개의 노드가 있을 때 두 노드를 선택해서, 현재 같은 그래프(집합)에 속하는지를 판별하는 알고리즘이다. 현재 같은 그래프에 속하는지 여부는 부모를 통해서 알 수 있는데 부모가 같다면 같은 그래프(집합)에 속한다고 볼 수 있는 것이다. 그럼 각 노드 별로 부모를 어떻게 설정하고 비교할 수 있는지 확인해보자. 먼저 아래와 같이 노드가 있다고 하자. 처음에는 모든 노드가 자기 자신을 부모로 설정한다. 그리고 다음과 같이 1과 2가 Union(합침)되면 2의 부모가 1로 변하게 된다. ..