공부3 Union-find 알고리즘 Union-find란? 서로소 집합 (Disjoint-set : 서로소 또는 상호배타 집합, 서로 중복 포함된 원소가 없는 집합) 을 표현할 때 사용하는 알고리즘 서로소 집합 연산 Make-Set(x) : x를 유일한 원소로 하는 집합 만드는 연산 Find-Set(x) : x의 대표자 (집합에 속한 하나의 특정 멤버) 값을 반환하는 연산 Union(x, y) : x집합을 y집합에 합치는 연산 트리 표현 - 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자 static void makeSet() { // 크기가 1인 단위집합을 만든다. for (int i=1;i 2021. 3. 21. Dynamic Programming(동적계획법) 알고리즘 Dynamic Programming (동적계획법) 이란? 동적계획법은 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법 입니다. 핵심기술은 memoization 으로 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술입니다. 구현 접근 방식은 기본적으로 분할 정복 알고리즘과 비슷합니다. 동적 계획법 역시 주어진 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산값을 이용해 원래 문제의 답을 산출합니다. 분할정복과의 차이점은 메모이제이션 기술의 사용 여부에 있습니다. 구현 방식은 top-down, bottom-u.. 2021. 3. 19. BitSet BitSet이라는 클래스를 새롭게 알게되어 간단하게 정리를 해봤습니다. BitSet이란? Bit로 이루어진 Vector로 boolean 배열처럼 사용 가능합니다. boolean 배열과 다른 점은 boolean은 1byte지만 bit는 1bit이기 때문에 한 값당 7bit를 줄일 수 있습니다. 관련 메서드 Set 해당 비트 true Get 해당 비트 값 가져옴 Flip 뒤집기 GetRange 복사 예제 - Set & Get public static void main(String[] args) { BitSet bs = new BitSet(); // Set & Get System.out.println("Set & Get\n"); System.out.println("10 값 : "+bs.get(10)); bs... 2021. 3. 7. 이전 1 다음
