알고리즘 (28) 썸네일형 리스트형 Plane Sweeping Plane Sweeping 곂친 부분이 있기때문에 단순한 공식을 넓이를 구하기 쉽지 않다. 각 직사각형은 4개의 꼭짓점을 가진다. 따라서 n개의 직사각형이라면, 최대 2n개의 x좌표와 2n개의 y좌표가 사용된다. Union - Find 알고리즘 (Java ) Union - Find 대표적 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있습니다 상호 배타적 집합이라고도 합니다 여러 노드가 존재할때, 두 개의 노드를 선택해서 현재 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘입니다 Find와 Union이라는 두가지 연산으로 이루어져 있습니다 예제 연결되지 않을 경우, 자신 자신을 가르키도록 합니다 부모를 합칠 경우에는, 더 작은쪽 값으로 합칩니다 이것을 합침 과정이라고 합니다 1과 3은 부모가 다르기 때문에 '1과 3이 연결되었는지' 파악하기에 힘이 듭니다 이때, 재귀함수가 사용됩니다 public static int[] parent = new int[1000001]; public void find_union_algorithm() { for (int .. [Java] 비트(Shift) 연산자 사용법 & 예제 비트 연산자는 데이터를 비트 단위로 연산합니다. 그러므로 0과 1로 표현이 가능한 정수 타입이나 정수형으로 캐스팅이 가능한 자료형만 비트 연산이 가능합니다. 비트 연산자는 기능에 따라 비트 이동연산자, 비트 논리연산자로 구분합니다. 비트 이동 연산자(, >>>) 연산식 설명 x > y 정수 x의 각 비트를 y만큼 오른쪽으로 이동시킵니다. (빈자리는 정수 a의 최상위 부호비트와 같은 값으로 채워집니다. x >>> y 정수 x의 각 비트를 y만큼 오른쪽으로 이동시킵니다. (빈자리는 0으로 채워집니다.) 비트 이동 연산자는 정수 데이터의 비트를 왼쪽 또는 오른쪽으로 이동시키는 연산을 합니다. 2 3 -16 >> 3 16 >> 3 은 16을 32비트로 분해한다음 오른쪽으로 3비트를 이동시키는 연산입니다. 비트를.. LRU Cache Algorithm Cache 알고리즘 중에 가장 유명한 알고리즘 중 하나로 LRU 알고리즘 이라는 것이 있다. LRU 알고리즘이란 Least Recently Used Algorithm 의 약자로, 캐시에서 메모리를 다루기 위해 사용되는 알고리즘이다. 캐시가 사용하는 리소스의 양은 제한되어 있고, 캐시는 제한된 리소스 내에서 데이터를 빠르게 저장하고 접근할 수 있어야 한다. 이를 위해 LRU 알고리즘은 메모리 상에서 가장 최근에 사용된 적이 없는 캐시의 메모리부터 대체하며 새로운 데이터로 갱신시켜준다. 알고리즘의 주요 동작은 다음과 같다. 가장 최근에 사용된 항목은 리스트의 맨 앞에 위치하고 가장 최근에 사용되지않은 항목 순서대로 리스트에서 제거된다. LRU 알고리즘의 구현은 위의 그림에서도 볼 수 있듯이 Linked Li.. Priority Queue(우선순위 큐) 최근 알고리즘 문제를 한개씩 풀다보면 풀다보면 자주 최대 힙, 최소 힙을 구현하여 사용해야 되는 경우가 생깁니다. (예를 들면 위상정렬, 최대값 뽑아내기 등) 자바에서는 현재 PriorityQueue를 이용하여 최대 힙, 최소 힙을 간단하게 사용할 수 있도록 제공해주고 있습니다. 다음은 최대 힙, 최소 힙에 대한 간단한 예시입니다. public void init() throws IOException{ PriorityQueue minHeap = new PriorityQueue(); System.out.println("최소 힙"); runHeapTest(minHeap); PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder()); System.. Binary Search Tree(이진 탐색 트리) 이진 탐색 트리란 정렬된 이진트리로써 다음과 같은 속성을 가지고 있습니다. 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가있는 노드 만 포함됩니다 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가있는 노드 만 포함됩니다. 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리 여야합니다. 중복된 키를 허용하지 않습니다. 검색/삽입 시간복잡도 위에서 검색/삽입 연산을 살펴보시면 아시겠지만, 모든 원소를 탐색하지 않는것이 특징입니다. 최악의 경우는 트리의 높이 만큼 탐색하는 경우라 볼 수 있겠습니다. 따라서 높이가 H 인경우의 검색/삽입의 시간 복잡도는 O(H) 입니다. 하지만, 시간복잡도는 원소의 개수로 표기할 때, 조금 더 좋은 표현이라 할 수 있습니다. H 를 원소의 개수 N 으로 표현해볼 수 없을까요.. 프로그래머스 - 뉴스 클러스터링 public int solution(String str1, String str2) { List multiSet1 = new ArrayList(); List multiSet2 = new ArrayList(); List intersection = new ArrayList(); List union = new ArrayList(); str1 = str1.toUpperCase(); str2 = str2.toUpperCase(); for (int i = 0; i < str1.length() - 1; i++) { char a = str1.charAt(i); char b = str1.charAt(i+1); if (Character.isLetter(a) && Character.isLetter(b)) { multiSet1.. LinkedList vs ArrayList ArrayList vs LinkedList 차이 List 인터페이스의 구현체는 뭐가 있을까요? Stack, Vector, ArrayList, LinkedList가 있습니다. 이 중에서도 대표적인 클래스인 ArrayList, LinkedList 차이에 대해 정리해보겠습니다. ArrayList란? ArrayList는 중복을 허용하고 순서를 유지하며 인덱스로 원소들을 관리한다는 점에서 배열과 상당히 유사합니다. 배열은 크기가 지정되면 고정되지만 ArrayList는 클래스이기 때문에 배열을 추가, 삭제 할 수 있는 메소드들도 존재합니다. 하지만 추가했을 때 배열이 동적으로 늘어나는 것이 아니라 용량이 꽉 찼을 경우 더 큰 용량의 배열을 만들어 옮기는 작업을 하게 됩니다. 내부 코드를 보면서 ArrayList에 .. 이전 1 2 3 4 다음
