Set과 Queue -Reboot(1)

학습목표

• Set이 무엇인지
• Queue가 무엇인지
• 왜 Set 을 써야하는지
• 왜 Queue를 써야하는지
• Set은 어디에 쓰이는지
• Queue는 어디에 쓰이는지
• Set의 다른 자료구조와의 차이점은 무엇인지
• Queue의 다른자료구조와의 차이점은 무엇인지
• Set을 구현한 구현체들은 무엇이 있고, 각 차이점은 ?
• Queue를 구현한 구현체들은 무엇이 있고, 각 차이점은?

Set은 무엇일까?

Set은 Collection을 확장한 인터페이스 중 하나이다.

Set은 순서가 없고, 중복을 허용하지 않는다. 어떤 데이터가 있는지만 확인할 때 주로 사용되는 자료구조 이다.

Set은 어디에 사용될까?

Set은 Array나 List와 달리 '순서'가 없다. 그렇기 때문에, 단순히 해당 데이터가 자료구조에 있는지? 없는지? 를 파악하고자 할때 쓰인다.

예를 들어 서버에 1분간 사용자가 요청한 로그가 있다. 이 서버에 붙어서 요청한 IP를 기준으로 사용자의 수가 얼마나 되는지 확인한다고 가정해보자.

1분간 동일한 서버에 요청하는 중복 사용자는 매우 많다. 만약 이 문제를 배열을 활용해 해결 하려 한다면 indexOf()메소드로 해당 객체가 존재하는지 확인 후 add()메소드로 추가하는 작업을 반복해야 할것이다. 하지만 Set을 구현한 객체라면 그냥 데이터를 추가만 해주면 될것이다. 그러면 자동으로 데이터가 중복되지 않고 저장된다. 이때, 각 사용자간의 순서는 중요하지 않다.

어떤 값이 존재하는지, 없는지 여부만 중요할때 Set을 쓰면 되겠다.

Set을 구현한 클래스들을 알아보자

• HashSet : 순서가 전혀 필요없는 데이터를 해시 테이블에 저장한다. Set중에 성능이 가장 좋다.
• TreeSet : 저장된 데이터의 값에 따라 정렬이 된다. red-black트리 타입으로 값이 저장, HashSet보다 약간 느리다.
• LinkedHashSet : 연결된 목록 타입으로 구현된 해시 테이블에 데이터를 저장, 저장된 순서에 따라 값이 정렬 된다. 소개된 3개 중 성능이 제일 나쁘다.

각 클래스들의 대략적인 설명을 확인해보고, 각 클래스들의 특징과 어떻게 구현되어있기에, 저런 특징이 나타나는지 알아보자!

HastSet

• HashSet은 무엇인지
• HashSet은 어디에 쓰이는지?
• 왜? HashSet을 써야하는지?
• HashSet 클래스의 특징, 동작원리

HashSet에 대해 파해쳐 보자

HashSet 클래스의 상속과 인터페이스 구현 관계를 살펴보자.

java.lang.Object
    java.util.AbstractCollection<E>
        java.util.AbstractSet<E>
            java.util.HashSet<E>

implements Set<E>, Cloneable, Serializable

AbstractSet에 구현된 메소드는 Object에서 제공한 equals()와 hashCode()와 이 클래스에서 추가한 removeAll() 뿐이다. Set은 중복을 허용하지 않는 자료구조로, equasl()와 hashCode() 메소드의 구현은 매우 중요하다.

HashSet의 동작 원리

HashSet은 내부적으로 HashMap을 호출해서 구현되어 있다.

// Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
/**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }

/**
     * Adds the specified element to this set if it is not already present.
     * More formally, adds the specified element <tt>e</tt> to this set if
     * this set contains no element <tt>e2</tt> such that
     * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
     * If this set already contains the element, the call leaves the set
     * unchanged and returns <tt>false</tt>.
     *
     * @param e element to be added to this set
     * @return <tt>true</tt> if this set did not already contain the specified
     * element
     */
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

즉, 데이터가 HashSet에 추가되는 방식은, 추가하고자 하는 데이터(매개변수)를'키'로, HashMap에 데이터를 넣기위한 value 값으로 Dummy값인 PRESENT를 저장하는 방식이다. Set의 입장에서는 데이터의 값이지만, HashMap의 입장에서는 '키' 이므로 중복되지 않는것이다.

add()와 마찬가지로 나머지 메소드도 HashMap을 이용해 구현되어있다. (HashSet과 HashMap은 HAS-A 관계에 있다는것!)

TreeSet

• TreeSet은 무엇인지?
• TreeSet은 왜, 어디에 쓰이는지?
• TreeSet과 HashSet의 차이점?!
• TreeSet 클래스의 특징과, 구현원리
  • 이진탐색트리
  • Red-Black Tree

TreeSet을 파해쳐 보자

TreeSet은 JDK1.2부터 제공되고 있으며,HashSet과 마찬가지로 Set을 구현한 클래스다.

HashSet과 달리 TreeSet은

이진탐색트리(BinarySearchTree)

구조로 이루어져 있다. (더 개선된 Red-Black Tree구조로 구현되어있음) 이진탐색트리는 추가와 삭제에는 시간이 조금 더 걸리지만, 정렬, 검색에는 높은 성능을 보여주는 자료구조이다. 그렇기에 HashSet보다 데이터의 추가와 삭제는 더 느리지만, 검색과 정렬에는 유리하다. TreeSet은 데이터를 저장시 이진탐색트리의 형태로 데이터를 저장하기에, 기본적으로 nature ordering을 지원한다.

TreeSet의 상속관계와 구현하고 있는 인터페이스를 살펴보자.

java.lang.Object
    java.util.AbstractCollection<E>
        java.util.AbstractSet<E>
            java.util.TreeSet<E>

All Implemented Interfaces:
Serializable, Cloneable, Iterable<E>, Collection<E>, NavigableSet<E>, Set<E>, SortedSet<E>

상속관계는 HahSet과 동일하나 구현하는 인터페이스에서 차이를 보이고 있다.

NavigableSet, SortedSet을 확인 할 수있다. API에서 어떤 인터페이스인지 잠깐 알아보자.

SortedSet의 Java API를 확인하면 아래와 같은 문구를 찾을 수 있다.

All elements inserted into a sorted set must implement the Comparable interface

즉 SortedMap에 들어가는 원소들은 모두 Comparable 인터페이스를 구현해 비교가 가능한 원소들만이 들어가야 함을 알 수 있다.

NavigableSet의 API를 확인해보자

A SortedSet extended with navigation methods reporting closest matches for given search targets. Methods lower, floor, ceiling, and higher return elements respectively less than, less than or equal, greater than or equal, and greater than a given element, returning null if there is no such element.

SortedSet을 확장한 인터페이스로, 주어진 타겟에 근접한 원소들을 탐색할 수있는 메소드들을 추가적으로 제공하는것을 알 수있다. (이 메소드들을 통해서 이진탐색트리를 구현하는게 아닐까!?)

이진탐색트리(BinarySearchTree)

이진탐색트리란 이진탐색과 연결리시트(LinkedList)를 결합한 자료구조다. 이진탐색의 효율적인 탐색능력을 유지하면서도, 자료의 입력과 삭제를 가능하게끔 구현되었다.

이진탐색(BinarySearch)

이진탐색이란,

정렬된 배열

에서 특정한 값을 찾아내는 알고리즘이다.

배열의 중간에 있는 임의의 값Y를 선택, 찾고자하는 값 X와 비교한다. X가 Y보다 크면 배열의 우측을 대상으로, 작으면 좌측을 대상으로 X를 찾을때 까지 같은 방법으로 계속 탐색한다. (술게임 업다운에 적용된 알고리즘...)

이진탐색이라는 이름이 붙여진 까닭은, 처음 N개 크기의 배열에서 단계가 지날수록 탐색할 배열의 크기가 반으로 줄어들기 때문이다. 즉 N개의 크기배열을 이진탐색을 하면 N,N/2,N/4,N/8...1로 실행될 것이다. 여기서 실행된 탐색의 횟수가 시간복잡도가 될것이고, 그 값을 K라 한다면 K 는 N에대해서 어떻게 나타낼수 있을까?

→ 1에 2를 K번 곱하면 N이 된다.

→ 2^K = N → K = log₂N

→ 즉 시간복잡도는

O(logN)

이 된다.

빅오 표기법 O()

big-O는 알고리즘의 효율성을 나타내는 지표다. bog-O를 이용해 알고리즘이 빨라졌는지, 메모리를 많이 쓰지는 않는지를 판단할 수있다. 시간복잡도와 공간복잡도가 있다.

• 시간복잡도시간복잡도란, bog-O에 대한 시간 개념으로 알고리즘의 수행 시간이 얼마인지를 나타낸다.수행되는 연산이란, 대게 산술, 비교, 대입등을 말한다. 반복문을 기준으로 입력값(N)에 영향을 받는 핵심코드가 어느 부분인지 파악하고 N과 어떤 관계가 있는지 파악하는 관점을 기르는 것이 중요하다. 연산이 많이 있더라도 하나로 취급하여 big-O값을 구할수 도 있습니다.
• 💡
• 수행되는 연산의 수
• 를 가지고 계산, 중요하지 않은 값을은 최대한 무시한다.
• big-O에서 무시되는 값들
  • 상수항 무시O(2N) → O(N)
  • O(N²+2) → O(N²)
  • 영향력 없는 항 무시O(N² + N) → O(N²) (N²이 가장 지배적이기 때문에 그외의 항은 무시한다.)
• 자주사용되는 표기법들O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(2ⁿ) < O(N!) < O(Nⁿ)입력데이터의 크기에 상관없이 언제나 처리속도는 동행하게 이루어진다.2. O(log n) (logarithmic)ex) Binary search입력데이터의 크기에 비례해서 처리시간이 증가해 메모리의 사용이 정비례(step : size = 1 : 1).4. O(n^2) (quadratic)ex) 이중 for문문제를 해결하기 위한 단계의 수는 주어진 상수값 C의 n제곱이다.
• https://velog.io/@ollabu3/codestates-immersive-TIL-4
• ex) 피보나치 수열, recursion
• 5. O(C^n) (exponential)
• 입력데이터의 크기에 따라 걸리는 시간은 제곱에 비례한다.
• ex) search linked list, for문을 이용한 array 검색
• 3. O(n) (linear)
• 입력데이터의 크기가 커지더라도 처리속도가 크게 달라지지 않으며, 실행시간이 지날수록 처리해야 하는 데이터의 양이 절반으로 줄어드며 실행 시간은 증가하지만 속도는 감소한다.
• ex) sorted Array search
• 1. O(1) (constant)

예제문제

입력값 N에대해 N²을 구하는 프로그램을 작성한다. 10이 입력되면 100이 출력되야한다.

몇가지 다른 방식의 알고리즘을 구현하고, 각각의 시간복잡도를 비교해보자

public int sumExam1(int N){
return N*N;
}

public int sumExam2(int N){
int sum =0;
for(int i =1; i<=N i++){
    sum +=N
}
return sum;
}

public int sumExam3(int N){
int sum =0;
for(int i =1; i<=N i++){
    for(int j=1; j<=N; j++){
        sum++;
    }
}
return sum;
}

공간복잡도

공간에 대한 개념으로 알고리즘이 공간을 얼마나 필요로 하는지 나타낸다. 시간복잡도 보다는 덜 중요시 취급되지만 신경써서 봐야할 필요가 있다.

예를들어 크기가 N인 배열을 만든다고 하면 공간복잡도는 O(N)되고, N*N인 배열을 만들면 O(N₂)이 됩니다. 함수의 재귀적인 호출의 경우 스택공간도 고려해야 한다.(스택공간을 어떻게 확인?...)

예제문제

1부터 N까지의 합을 구하는 에제를 재귀적으로 구현한 알고리즘을 살펴보자.

public int sumSpaceExam1(int N){
    int sum = 0;
    if(N<1){
        return 0;
    }
    return N + sum(N-1); 
}

그러나, 단지N번 호출했다고 항상 O(N)이 되는것은 아니다.

public int sumSpaceExam2(int N){
    int result = 0;
    for(int i=0; i<N; i++){
        result += sum(i, i+1)
    }
    return result;
}
public int sumSpaceExam3(int a, int b){
    return a+b;
}

알게 된 점

• Set이 무엇인지
  • Set은 Collection을 확장한 인터페이스로, 순서가 없으며 중복을 허용하지 않는 자료구조이다.
• Queue가 무엇인지
• 왜 Set 을 써야하는지
  • 순서가 없고 중복을 허용하지 않기 때문에, 이런 작업에 있어서는 Set을 쓰는것이 성능상 이롭다.
• 왜 Queue를 써야하는지
• Set은 어디에 쓰이는지
  • 순서가 관계없고 데이터가 존재하는지 없는지 여부만 중요할때 쓰인다.
• Queue는 어디에 쓰이는지
• Set의 다른 자료구조와의 차이점은 무엇인지
  • 순서가 없고, 중복을 허용하지 않는다.
• Queue의 다른자료구조와의 차이점은 무엇인지
• Set을 구현한 구현체들은 무엇이 있고, 각 차이점은 ?
  • HashSet
    • HashSet은 내부적으로 HashMap을 호출, 구성관계를 가지고 있다.
    • 순서가 없고, 정렬되어있지 않으며 HashMap을 사용하므로, 추가,삭제, contain등의 시간복잡도는 O(1)이다.
  • TreeSet
    • TreeSet은 이진탐색트리의 형태로 데이터를 저장 한다. 자바에서는 더 개선된 Red-BlackTree로 구현되어있다.
    • 이진탐색트리란 이진탐색과 연결리스트(LinkedList)를 결합한 자료구조이다. 정렬된 탐색에서 큰 효율을 보이는 이진탐색과 추가와 삭제가 가능한 연결리스트를 결합했다.
    • 이진탐색의 뜻은 찾고자하는 배열의 탐색범위가 단계를 거칠수록 반절로 줄어들기 때문에 붙여졌다.
    • 이진탐색은 탐색하고자 하는 범위의 임의의 중간값 X를 선택, 찾고자 하는 값 Y와 비교하여 Y가 작으면 좌측으로, 크면 우측의 범위를 대상으로하여 동일한 탐색을 실행한다.(술게임 업다운에 적용됨)
    • 이때 이진탐색의 시간복잡도는 O(logN)을 보장한다.
    • 빅오표기법은 알고리즘의 효율성을 나타내는 지표로, 시간복잡도와 공간복잡도가 있다.
    • 빅오표기법은 상수항을 무시하고, 가장 지배적인 항을 제외한 나머지 항은 무시한채 표기한다.
  • LinkedHashSet
• Queue를 구현한 구현체들은 무엇이 있고, 각 차이점은?

Reference

TIL #4 // Time Complexity

빅오 표기법 (Big-O Notation), 시간 복잡도, 공간 복잡도

이진탐색트리(Binary Search Tree)

https://coding-factory.tistory.com/555

https://ecsimsw.tistory.com/entry/%EC%9E%91%EC%84%B1-%EC%A4%91-%EC%9E%90%EB%B0%94-HashSet%EC%9D%98-%EC%9B%90%EB%A6%AC