JUINTINATION

해시 테이블이란? 해시 함수를 사용하여 입력 키 값으로부터 해시 값을 얻어 그것을 인덱스로 사용하여 효율적인 검색 방식을 제공하는 자료구조 원소가 저장될 자리가 원소의 값에 의해 결정됨 매우 빠른 응답을 요하는 경우에 유용하게 사용됨 ex) 주민 등록 시스템과 같은 호출 번호 관련 검색 해시 함수 해시 함수를 적용하여 입력 키값으로부터 해시 값을 얻었을 때 입력 원소가 해시 테이블에 골고루 저장되어야 한다. 계산이 간단해야 하며 대표적으로 나누기 방법과 곱하기 방법이 있다. 나누기 방법(Division Method) h(x) = x mod m m: 해시 테이블 사이즈, 보통 소수로 지정 곱하기 방법(Multiplication Method) h(x) = (xA mod 1) * m A: 0

서로소 집합(Disjoint Set)이란? 공통 원소가 없는 두 집합, 즉 A∩B=∅을 만족시키는 두 집합 A, B를 서로소 집합이라고 한다. 유니온 파인드(Union-Find)란? 서로소 집합에 대한 연산을 할 때 사용하는 알고리즘이다. 쉬운 이해를 위해 다음의 예시를 보자. https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 위의 문제처럼 초기에 n+1개의 집합 {0}, {1}, {2}, ... , {n}이..

힙이란? 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 다음과 같은 규칙을 갖는 완전이진트리를 기본으로 한 자료구조 A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다. 힙에는 두가지 종류가 있다. 최대 힙: 부모노드의 키 값이 자식노드의 키 값보다 항상 큰 힙 최소 힙: 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙 대부분의 경우는 자식노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 루트 노드에 오게 되는 특징이 있음 이를 응용하여 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다. 힙의 주요 연산 최소 힙을 기준으로 힙의 주요 연산은 다음과 같다. ..

컴퍼지트 패턴이란? 부분-전체의 관계를 갖는 객체들 사이의 관계를 정의하여 클라이언트가 전체와 부분을 구분하지 않고 동일한 인터페이스를 사용할 수 있게 만드는 패턴이다. 다음과 같이 컴퓨터를 모델링했다고 하자. 컴퓨터는 다음과 같이 키보드(Keyboard 클래스), 본체(Body 클래스), 그리고 모니터(Monitor) 클래스로 이루어져있다. class Keyboard { private int price; private int power; public Keyboard(int price, int power) { this.price = price; this.power = power; } public int getPrice() { return price; } public int getPower() { retu..

추상 팩토리 패턴이란? 관련성 있는 여러 종류의 객체를 일관된 방식으로 생성하는 경우에 객체를 생성하는 코드를 캡슐화하여 구체적인 클래스에 의존하지 않고 서로 연관되거나 의존적인 객체들의 조합을 만드는 패턴이다. 다음과 같이 엘레베이터 부품 업체에 대한 설계가 있다고 하자. Motor 클래스의 move 메서드의 구조는 다음과 같다. public void move(Direction direction) { // 1. 이미 이동 중이면 무시한다. // 2. 만약 문이 열려 있으면 문을 닫는다. // 3. 모터를 구동해서 이동시킨다. // 4. 모터의 상태를 이동 중으로 설정한다. } 3번 부분을 제외하면 Hyundai 모터, LG 모터 둘 다 코드가 동일하기 때문에 템플릿 메서드 패턴을 적용할 수 있다. Do..

팩토 메서드 패턴이란? 상황에 따라 객체를 다르게 생성해야 할 때 1개의 클래스가 아닌 코드를 각각의 하위 클래스에서 재정의하게 하여 객체의 생성 코드를 별도의 클래스/메소드로 분리하는 패턴이다. 다음과 같이 엘레베이터 제어 시스템에서 다양한 엘레베이터 스케줄링을 지원한다고 하자. import java.util.ArrayList; import java.util.List; enum Direction { UP, DOWN; } class ElevatorManager { private List controllers; private ThroughputScheduler scheduler; public ElevatorManager(int controllerCount) { controllers = new ArrayLi..