CS/자료구조7 Bitset 자료구조란 Bitset이란BitSet은 비트를 효율적으로 저장하고 조작할 수 있는 자료구조입니다.Bitset 사용 이유1. 메모리 효율boolean[]은 실제로는 한 요소당 1바이트 이상 사용되지만,BitSet은 64개의 비트를 long 1개에 담아 8바이트로 처리합니다.👉 즉, 대량의 true/false 값을 다룰 때 훨씬 가볍습니다.2. 성능비트 연산 (|, &, ^)을 통해 대량의 boolean 값을 한 번에 계산할 수 있어 빠릅니다.예: bitset1.and(bitset2) → 배열 전체를 순회하면서 동시에 AND 처리3. 개발자 실수 줄여줌Java는 정수 타입을 이용한 직접적인 비트 연산보다 BitSet을 사용할 때 더 읽기 쉽고 안전한 코드를 작성할 수 있게 해줍니다.컴파일러가 bitIndex 음수 체.. 2025. 4. 4. LiskedList vs ArrayDeque vs 배열 // 원형 배열의 경우realIndex = (head + index) % array.length;element = array[realIndex];// 일반 배열의 경우element = array[index];Queue의 구조는 한쪽에서는 삽입만 일어나고 한쪽에서는 삭제만 하는 자료구조 입니다. 즉, 먼저 들어간 것이 먼저 나오는 FIFO 구조입니다. 앞과 뒤 전부에서 삽입 삭제가 가능한 Deque도 있습니다. Queue와 Deque의 인터페이스를 구현하는 대표적인 두 가지 클래스는 LinkedList와 ArrayDeque가 있습니다. LinkedList 앞, 뒤 노드를 참조하고 있어 배열, ArrayDeque보다 상대적으로 오버헤드가 있음요소들이 연속적으로 메모리 할당이 되어있지 않음 ArrayDeque.. 2024. 8. 1. HashMap 동작원리 HashMap은 Key와 Value가 짝 지어진 자료구조입니다. HashMap 동작원리HashMap은 key의 HashCode을 이용해서 시간복잡도 O(1)으로 value를 찾아낸다. HashCode를 인덱스로 삼는 배열 자료구조이다. 실제 계산은 HashCod % size 이다.나머지 연산을 하는 이유는 배열의 인덱스 중 하나로 매핑시키기 위함이다.특정 값에 대한 해시값 만약 3288449라는 값을 배열의 인덱스로 사용한다면 최소 3288449 크기의 배열을 생성해야한다. 메모리를 많이 차지할것이다. 때문에 이 값을 배열의 Size로 나눈 나머지를 구하고 이를 Index로 사용하는 것이다. 만약 HashMap 내부 배열 Size가 10이라면 3288449 % 10 = 9. 즉 9라는 인덱스를 갖게 된.. 2024. 5. 23. Iterator에 대하여 Iterator 자바의 컬렉션에 존재하는 값들을 읽어오기 위한 방법으로 'iterator'라는 클래스가 존재한다. 이 iterator는 해당 컬렉션의 주소값을 기반으로 하나씩 값을 조회하는 클래스이다. 따라서, 대표적으로 다음과 같은 두 개의 함수가 존재한다. hasNext() : 다음 값을 갖고 있는지 true/false 반환 next() : 다음 값으로 이동 및 반환 자바에서는 각각의 컬렉션별로 Iterator를 반환하는 함수를 갖고 있고, 이 함수는 컬렉션의 첫 번째 주소 값을 반환하는 형식으로 되어있습니다. Iterator를 이용해 컬렉션을 추출하는 방법은 '첫 번째 주소를 담은 Iterator 생성 -> 반복문을 통해 하나씩 이동하며 저장된 값 반환' 입니다. 이를 코드로 나타내면 다음과 같습니.. 2024. 4. 16. Set에 대하여 Set은 중복을 없애기 위해 사용한다. Set의 구현체로는 HashSet, LikedHashSet, TreeSet이 있다. HashSet: 순서x, 중복x LikedHashSet: 순서o, 중복x TreeSet: 오름차순, 중복x HashSet intHashSet = new HashSet(); LinkedHashSet intLinkedHashSet = new LinkedHashSet(); TreeSet intTreeSet = new TreeSet(); for (int i : new int[] { 3, 1, 8, 5, 4, 7, 2, 9, 6}) { intHashSet.add(i); intLinkedHashSet.add(i); intTreeSet.add(i); } Set strHashSet = new Ha.. 2024. 4. 16. List <-> 배열 변환하는 법 배열을 List로 1. Arrays.asList() String[] arr = { "A", "B", "C" }; List list = Arrays.asList(arr); 배열의 요소를 수정하든 List의 요소를 수정하든 서로의 영향을 받는다 ex) 배열에서 "A"를 "D"로 바꾸면 List에서도 "A"가 "D"로 바뀜 얕은 복사(Shallow Copy)로 생각하시면 됩니다. 2. new ArrayList( Arrays.asList()) String[] arr = { "A", "B", "C" }; List list = new ArrayList(Arrays.asList(arr)) 그래서 new 생성자로 새로운 List를 만든 후 거기에 복사해줍니다. 깊은 복사(Deep Copy)로 생각하시면 됩니다. 그런데.. 2024. 3. 29. HashMap 사용법 HashMap은 Key와 Value의 묶음모음으로 이루어져 있는 자료구조입니다. HashMap 생성법 HashMap h1 = new HashMap( ); // 기본 capacity:16, load factor:0.75 HashMap h2 = new HashMap(20); // capacity:20으로 설정 HashMap h3 = new HashMap(20, 0.8); // capacity:20, load factor:0.8로 설정 HashMap h4 = new HashMap(h1); // 다른 Map(h1)의 데이터로 초기화 c capacity는 데이터 저장 용량, load factor는 데이터 저장공간을 추가로 확보해야 하는 시점을 지정합니다. load factor 0.8 은 저장공간이 80% 채워져 .. 2024. 3. 28. 이전 1 다음
