자료구조10 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. [백준 13334] 철로 / 자바 / 라인스위핑 ** #문제 레벨: G2알고리즘: 라인 스위핑 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/13334#문제 풀이 라인 스위핑 을 직역하면 싹스리 하는 이라는 뜻이다. 한 마디로 한 쪽 방향으로 정렬된 직선을 스캔하며 정해진 기준에 따라 답을 업데이트 하는 것이다. 그리드 알고리즘의 종류라고 생각하면 된다.이 문제는 끝점을 기준으로 오름차순 정렬한다. 놓아야 하는 직선 L을 정렬된 끝점에 맞추어 계속해서 대보는 것이다. 기준에 부합하면 시작점을 큐에 넣고 L보다 튀어나온 큐에 있는 시작점들은 Poll 해준다. 간단하지 않은가? +라인스위핑 문제느 변수를 사용해서 답을 관리하는 것보다 우선순위 큐의 사이즈로 관리하는 것이 용이하다.!!!!.. 2024. 8. 28. [백준 1717] 집합의 표현 / 자바 / 자료구조(유니온 파이든) #문제 레벨: G5알고리즘: 자료구조(유니온 파이든) 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/1717#문제 풀이 이 문제는 "Disjoint Set(분리 집합)" 또는 "Union-Find" 알고리즘을 사용하여 효율적으로 해결할 수 있다.유니온 파인드 자료구조는 자기의 부모를 기록하는 것이다. 위 그림에서 2와 3이 같은 집합인지 알려면 최상위 부모가 같은지 확인 하는 거다. 집합을 추가하는 방법은 또 그림으로 설명하겠다. 3과 6이 같은 집합인 걸 알고 집합을 추가할 때, 6의 최상위 부모인 7과 3의 최상위 부모인 1를 자식-부모 관계로 만들면 된다. 1을 자식으로 두던 7을 자식으로 두던 그건 구현하는 사람 마음이다.#.. 2024. 8. 26. [백준 1275] 커피숍2 / 자바 / 자료구조(세그먼트 트리) #문제 레벨: G1알고리즘: 자료구조(세그먼트 트리) 풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/1275#문제 풀이 위 문제는 세그먼트 트리의 전형적인 문제이다.https://jsw5913.tistory.com/208 [백준 2243] 사탕상자 / 자바 / 자료구조(세그먼트 트리)#문제 레벨: P5알고리즘: 세그먼트 트리풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2243#문제 풀이 위 문제는 2가지로 구현할 것이다.위 문제를 봤을 때 가장 직jsw5913.tistory.com위 글을 보고 오면 이해하기 쉬울 것이다.#풀이 코드 import java.i.. 2024. 8. 22. [백준 2042] 구간 합 구하기 / 자바 / 자료구조(세그먼트 트리) #문제 레벨: G1알고리즘: 자료구조(세그먼트 트리) 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2042#문제 풀이 문제를 처음 봤을 때 누적합을 떠올렸다. 앞서 말하지만 누적합은 정답이 아니다. 배열의 1 ~i 까지의 합을 적어 놓은 것이다. 그러면 A ~ B 까지의 합을 구할 때는 A ~ B 까지 순회하는 것이 아닌 arr[B] - arr[A]를 하면 되는 것이다. 그러나 여기서 문제인 것은 값을 바꿀 때이다. 만약 2 번째 숫자를 2 -> 5를 바꿨다면 2 번째 뒤에 있는 값들은 다 업데이트 해야 한다. 왜냐하면 1 ~ i 까지의 숫자합이기 때문에 새로 바뀐 2의 숫자로 더해줘야 하기 때문이다. 답을 출력하는 것 O(1)이.. 2024. 8. 7. [백준 1655] 가운데를 말해요 / 자바 / 우선순위 큐 #문제 레벨: G2알고리즘: 자료구조 (우선순위 큐)풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/1655#문제 풀이 이 문제를 봤을 때 한 번에 떠올리는 아이디어로 한다면 시간초과가 날 것이다. 입력을 받을 때마다 정렬을 하고 중간값을 찾는 다는 생각은 오답이다. 배열 정렬의 최선의 시간복잡도는 O(n)이고 최악은 O(n^2)이다. 그래서 우리는 더 나은 정렬된 자료구조를 사용해야 한다. 그건 정렬의 특화된 우선순위 큐이다. 우선순위 큐 정렬(Heap정렬 사용)의 시간복잡도는 O(logn)이다.아이디어는 이러하다. 중간값보다 낮은 숫자들을 담을 maxHeap과 중간값보다 높은 숫자들을 담을 minHeap을 생성한다. maxHeap은.. 2024. 7. 20. [백준] 카드 정렬하기 / 자바 문제 https://www.acmicpc.net/problem/1715레벨: G4알고리즘: 그리드풀이시간: 1시간힌트 참조 유무: 무1 번째 시도 오름차순 정렬 필요두가지 생각이 들었습니다. 정렬 후1. 두 묶음씩 묶어서 계속 더해가며 줄일 것인가2. 1 번째와 2 번째만 계속 더해가며 줄일 것인가예시를 들어 비교1 3 5 10 4 + 15 + 4 + 15 = 38 4 + 4+5 + 9 +10 =32 결론: 2 번째 방법 선택 // 3, 5킬로그램 봉지가 있다.// 최대한 5킬로그램 봉지를 많이 들고가야 한다.// 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.import java.util.*;import java.io.*;class Main { public static v.. 2024. 4. 29. 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. 이전 1 2 다음
