Algorithm/자료구조 for Algorithm
-
[Java]SetAlgorithm/자료구조 for Algorithm 2022. 3. 22. 00:52
Set Set은 내부 데이터를 중복해서 저장할 수 없고, 저장된 객체에 순서가 없다. 따라서 Set은 List와 같이 인덱스를 사용하여 원소에 바로 접근할 수 없다. HashSet Java는 내부적으로 Set 인터페이스를 따로 정의해 두었다. 이곳에 다양한 Set 구현체를 활용하여 코드를 작성할 수 있는데, HashSet은 기본적인 Set의 특성을 그대로 반영한 클래스이다. Set set = new HashSet(); set.add(5); set.add(5); set.add(1); set.add(1); set.add(3); System.out.println(set); 다음과 같이 중복된 자료를 저장하더라도 중복되지 않게 저장되는 것을 확인할 수 있다. TreeSet Set은 TreeSet을 사용하여 내부..
-
[Java]우선순위큐(PriorityQueue)Algorithm/자료구조 for Algorithm 2022. 3. 22. 00:16
우선순위큐(PriorityQueue) 스택은 후입선출, 큐는 선입선출을 특징을 가졌다. 이와 달리 우선순위큐는 사용자가 지정한 우선순위에 의거하여 원소를 꺼내는 특징이 있다. 기본적인 사용 Java에서는 PrioryQueue 클래스를 이미 내부적으로 포함하고 있다. 이는 기본적으로 오름차순으로 수를 꺼낼 수 있도록 구현되어 있다. PriorityQueue pq = new PriorityQueue(); pq.offer(5); pq.offer(3); pq.offer(9); pq.offer(1); while(!pq.isEmpty()) { System.out.println(pq.poll()); } 정렬기준 정하기(사용자 정의) PriorityQueue의 생성하는 단계에서 Comparator 인터페이스를 재정의한..
-
[Java]서로소 집합(Disjoint Set)(Union-Find)(Merge-Find Set)Algorithm/자료구조 for Algorithm 2021. 4. 15. 11:08
*서로소 집합(Disjoint Set) -> 서로소 집합 자료구조는 상호 배타적으로 이루어진 집합(서로소 집합 : 공통 원소가 없는 두 집합)을 효율적으로 표현하기 위해 만들어진 자료구조이다. -> 서로소 집합은 서로 다른 두 개의 집합을 병합하는 연산(Union)(Merge)과 집합의 원소가 어떤 집합에 속해 있는지 판단하는 연산(Find)을 기반으로 구현되기 때문에, Union-Find 혹은 Merge-Find Set이라고도 불린다. -> 서로소 집합을 구현하는 방법은 연결 리스트를 이용하는 방법과, 트리를 이용하는 방법이 있는데, 이 글에서는 트리를 이용하는 방법에 대해서만 다룬다. *서로소 집합의 단순 구현(트리) -> 서로소 집합은 기본적으로 총 3가지 연산(MakeSet, Find, Union..
-
[Java]덱(Deque)Algorithm/자료구조 for Algorithm 2021. 2. 18. 22:08
*덱(Deque) -> 덱이란 큐와 스택의 특성을 동시에 가질 수 있는 자료구조이다. -> 두 가지 특성을 동시에 활용할 수 있기 때문에 더 다양하게 활용될 수 있다. *Java의 덱 -> 덱 자료 구조는 기본적으로 Queue의 구조를 채용하고 있다. 따라서 일반 큐의 연산인 poll() 메서드와 offer() 메서드는 동일하게 사용할 수 있다. -> 덱 자료 구조는 양 방향을 모두 head로 볼 수 있다. 따라서, 배열의 관점에서 인덱스가 0인 부분의 head는 일반 큐 메서드 이름에 Fisrt를 추가하여 구분하고, 마지막 인덱스 부분의 head는 Last를 추가하여 구분한다. -> peek() 메서드도 마찬가지이다. 좌측 부분의 head를 확인하고 싶다면 peek() 메서드 혹은 peekFirst()..
-
[Java]해시맵(HashMap)Algorithm/자료구조 for Algorithm 2021. 2. 13. 18:46
*Java Collections : 맵(Map) 인터페이스 ->모든 데이터를 '키(Key)'와 '값(Value)'의 '한 쌍(Pair)의 형태'로 연관지어 저장한다. ->키(Key)는 중복을 허용하지 않고, 값(Value)은 중복을 허용한다. ->순서는 중요하지 않다 : 순서가 없다. *해시맵(HashMap) 클래스 ->맵 인터페이스를 구현한 자바의 대표적인 Collections 클래스. ->해시(Hash)를 사용하기 때문에 검색이 빠르다(리스트에서 검색하는 속도보다 빠르다). ->키(Key)와 값(Value)을 저장하기 때문에, HashMap의 형태로 선언한다. HashMap hm = new HashMap(); ->기본적으로 삽입은 put, 삭제는 remove, 조회는 여러가지 방법으로 할 수 있다. ..
-
[Java]큐(Queue)Algorithm/자료구조 for Algorithm 2020. 9. 25. 21:22
*큐(Queue) ->큐란 선입선출(FIFO : First In First Out)의 특성을 가진 자료구조이다. ->쉽게 말해 먼저 들어간 것이 먼저 나온다. 정거장에 들어오는 지하철이나, 놀이공원에 줄 서 있는 사람들을 생각하면 이해하기 쉽다. *Java의 큐 ->큐 입력 연산은 일반적으로 offer() 메서드, 출력 연산은 poll() 메서드를 이용한다(add()와 remove()도 있지만, 이 메서드들은 Exception을 발생시키는 특징이 있다). head에 있는 원소(다음으로 나올 차례인 것)를 확인하는 연산은 peek()메서드를 이용한다. ->자바의 Queue관련 API를 살펴보면 인터페이스로 구현되어 있기 때문에, 큐 인터페이스를 상속하여 구현해놓은 LinkedList클래스를 이용하여 객체를..
-
[Java]스택(Stack)Algorithm/자료구조 for Algorithm 2020. 9. 25. 21:22
*스택(Stack) ->스택이란 후입선출(LIFO : Last In First Out)의 특성을 가진 자료구조이다. ->쉽게 말해 나중에 들어간 것이 먼저 나온다. 마트의 진열대에 물건을 놓거나, 상자에 물건을 넣은 뒤 꺼내는 것을 예시로 생각해보면 이해하기 쉽다. *Java의 스택 ->자바의 Stack관련 API를 살펴보면 스택 입력 연산은 push(), 출력 연산은 pop()메서드를 이용하며, top에 있는 원소(제일 마지막에 넣은 것)를 확인하는 연산은 peek()메서드를 이용한다. 언급한 연산 이외에 스택이 비어있는지 확인하는 empty() 메서드, 스택안에 어떤 아이템이 있는지 확인하는 search()메서드가 있다. ->스택은 java.util.Vector 클래스를 상속하기 때문에 여러 다양한 ..