본문 바로가기

자료구조9

[백준 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.
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.

티스토리툴바