자료구조6 Stack, Queue, Deque StackLIFO 후입선출이다스택에 값을 넣는건 push 빼는건 popStack은 내부에서 Vector라는 자료 구조를 사용한다 옛날에 개발된건데 하위호환을 위해 놔둔거다 지금은 Deque를 사용하면 된다. QueueFIFO 선입선출이다큐에 값을 넣는건 offer 빼는건 pollQueue인터페이스는 Collection의 자식이다Queue의 대표 구현체는 ArrayDeque, LinkedList가 있다 DequeDouble Ended Queue의 약자다 양 끝에서 요소를 추가하거나 제거할 수 있다. 큐와 스택으로 둘 다 활용이 가능하다offerFirst() : 앞에 추가offerLast() : 뒤에 추가pollFirst() : 앞에서 꺼냄pollLast() : 뒤에서 꺼냄Deque의 대표적 구현체는 Arr.. 2025. 7. 24. Map과 자주쓰이는 메서드 Map키-값의 쌍을 저장하는 자료구조키는 맵 내에서 유일해야한다. 키를 통해 값을 빠르게 검색 가능키는 중복될 수 없지만, 값은 중복될 수 있다 Map은 순서를 유지하지 않는다.자바는 HashMap, TreeMap, LinkedHashMap등 구현체를 제공함Map은 Set과 거의 비슷하다 다만 옆에 value가 딸려있느냐 없느냐의 차이다HashSet - HashMapLinkedHashSet - LinkedHashMapTreeSet - TreeMap 다 비슷하고 해시셋은 해시맵의 구현을 가져다 사용함 Map에서 value만 비우면 셋으로 사용가능메서드 설명put(K key, V value)지정된 키와 값을 맵에 저장함. 같은 키가 존재하면 값을 변경함.putAll(Map m)지정된 맵의 모든 매핑을 현재 .. 2025. 7. 24. Set과 주요 메서드 Collection 인터페이스는 java.util 패키지의 컬렉션 프레임워크의 핵심 인터페이스 중 하나다.이 인터페이스는 자바에서 다양한 컬렉션을 다루기 위한 메서드를 정의한다.Collection 인터페이스는 List, Set, Queue와 같은 다양한 하위 인터페이스 들과 함께 사용된다. Set 인터페이스는 Collection 인터페이스의 하위 요소다 중복을 허용하지 않는 유일한 요소의 집합을 나타낸다. 순서를 보장하지 않으며, 특정 요소가 집합에 있는지 여부 확인에 최적화 되어있다,Set인터페이스는 HashSet, LinkedHashSet, TreeSet 등의 여러 구현 클래스를 가지고 있으며 각 클래스는 Set 인터페이스를 구현하며 각각의 특성을 지니고 있다. Set 인터페이스의 주요 메서드메서드 .. 2025. 7. 24. HashSet 숫자는 해시 알고리즘을 이용해 저장한다문자는 숫자로 변경하고 해시 알고리즘을 이용해 저장한다객체는 Object.hashCode()를 이용해서 저장한다.보통 객체에서 재정의해서 사용한다 재정의 하지 않으면 같은 값이 중복으로 들어간다 같은 객체 인스턴스를 여러개만들었을 때 같은 값이 입력되더라도 같은 해시값이 나오기 때문임equals도 재정의 해야한다 해당 객체의 특정 값을 기준으로 동등성을 비교하도록 해야함 해시란?https://jaeiktech.tistory.com/2 해시코드와 이퀄스 모두 재정의 하지 않으면 같은 값을 두번 넣었을 때셋에 다른 곳에 같은 값이 저장된다 검색도 해시코드가 달라 되지 않는다해시코드만 재정의 한 경우 같은 값을 두번 넣었을 때셋에 같은 곳에 같은 값이 저장된다 해시코드.. 2025. 7. 24. 해시 해시 알고리즘을 쓰면 O(N)의 성능을 O(1)로 끌어올릴 수 있다. O(1)이라는건 인덱스 기반데이터를 인덱스의 값으로 같이 쓰면 중복 검사를 하지 않고 조회 시 빠르게 할 수 있음그런데 그럼 메모리 낭비가 심하다 나머지 연산으로 메모리를 아낀다 하지만 해시 충돌이 일어날 수 있다.해시 충돌은 인정해야한다. 대신 자바에서는 나머지 연산 및 갖가지 수학적 요소로 해시 충돌을 최대한 막고 사실상 충돌이 일어나는 일은 많지 않다.충돌이 일어나면 해시 안의 배열 같은 인덱스에 값이 여러개 들어가야하고 거기서 풀스캔을 해야한다.그래서 해시는 O(1)을 보장하는건 아니고 최악의 경우 O(N)이 될 수도 있다.하지만 그런일은 잘 일어나지 않고 O(1)에 가깝다고 볼 수 있다. 해시 기반 자료 구조를 사용하는 경우.. 2025. 7. 24. 배열리스트 vs 연결리스트 성능 비교 ArrayList vs LinkedList앞에 삽입, 삭제배열 리스트 O(n) - 뒤로 공간 하나씩 땡겨야함연결 리스트 O(1) - 앞에 노드 하나 만들면 됨 중간 삽입, 삭제배열 리스트 O(n) - 중간부터 뒤에 공간 땡겨야함연결 리스트 O(n) - 중간까지 노트 타고 가야함 끝에 삽입, 삭제배열 리스트 O(1) - 바로 추가하면됨연결 리스트 O(1) - 바로 추가하면됨 인덱스로 조회배열 리스트 O(1) - 메모리 주소 복사해서 바로 감연결 리스트 O(n) - 노드를 인덱스 수 만큼 이동 숫자로 조회배열 리스트 O(n) - 배열 숫자나올때 까지 순회연결 리스트 O(n) - 노드 숫자나올때 까지 순회 배열 리스트가 앞에 삽입,삭제 빼고 연결 리스트를 압승함. 같은 O(n)이라도 연결 리스트는 노드가 메모.. 2025. 7. 24. 이전 1 다음
