알고리즘/자료구조7 [백준 1197] 최소 스패닝 트리 / 자바 / 자료구조(크루스칼 알고리즘/유니온 파인드) #문제 레벨: G4알고리즘: 자료구조(최소 스패닝 트리)풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/1197#문제 풀이 MST란 n개의 정점을 최소한의 간선(n-1)으로 이은 트리(싸이클x)이다. MST는 크루스칼 알고리즘과, 프릴 알고리즘을 사용해 풀 수 있다. 크루스칼 알고리즘은 유니온 파인드 자료구조를 사용한다. 프림 알고리즘은 다익스트라 비슷하게 풀이한다. 크루스칼 vs 프림 크루스칼 알고리즘프림 알고리즘탐색 방법간선 위주정점 위주탐색 과정시작점 따로 지정없이 최소 비용의 간선을 차례대로 대입하면서 사이클이 이루어지기 전까지 탐색시작점을 지정한 후 가까운 정점을 선택하면서 모든 정점을 탐색사용간선의 개수가 적은 경우 크루스칼 알고.. 2024. 8. 30. [백준 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. [백준 2243] 사탕상자 / 자바 / 자료구조(세그먼트 트리) #문제 레벨: P5알고리즘: 세그먼트 트리풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2243#문제 풀이 위 문제는 2가지로 구현할 것이다.위 문제를 봤을 때 가장 직관적으로 떠오르는 자료구조는 TreeMap이다. 입력하면 항상 키의 오름차순대로 정렬된다. 사탕을 넣고 뺐을 때는 O(logM)으로 사탕을 줄 때는 O(M)이다. 왜 이렇게 되냐 하면, 키의 위치를 찾는 건 O(logM)이지만, 사탕의 순위를 알기 위해서는 1순위부터 차례대로 순위를 매겨가며 해당 순위의 사탕을 줘야 하기 때문에, 1~M순위까지의 Key를 다 탐색해야 하기 때문이다. 그러나 해당문제는 세그먼트 트리 문제이다. 글보다는 그림이 이해하기 쉬우니 아래.. 2024. 8. 11. [백준 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. [백준 14891] 톱니바퀴 / 자바 / 구현 + 자료구조 #문제 레벨: G5알고리즘: 구현 + 자료구조풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/14891#문제 풀이 위 문제는 간단한 구현 문제이다. 회전을 하기 전 그 상태가 모든 톱니바퀴의 회전 여부를 결정하기 때문이다. 만약 처음 그상태가 아니라 톱니바퀴 하나를 돌리고 나서 다른 톱니바퀴의 회전 여부를 결정해야 했다면 이것보다는 조금 더 구현이 복잡해졌을 수 있다. 1. 해당 톱니바퀴를 기준으로 연속적으로 왼쪽 톱니바퀴들이 회전하는지 체크하고 같은 방식으로 오른쪽 톱니바퀴들이 회전하는지 체크한다.2. 회전 시켜준다. 3. 스코어를 구한다. 난 이 문제를 통해 구현연습을 한 것도 있지만 자료구조를 더 집중적으로 공부해봤다. 톱니바퀴의.. 2024. 8. 1. [백준 1655] 가운데를 말해요 / 자바 / 우선순위 큐 #문제 레벨: G2알고리즘: 자료구조 (우선순위 큐)풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/1655#문제 풀이 이 문제를 봤을 때 한 번에 떠올리는 아이디어로 한다면 시간초과가 날 것이다. 입력을 받을 때마다 정렬을 하고 중간값을 찾는 다는 생각은 오답이다. 배열 정렬의 최선의 시간복잡도는 O(n)이고 최악은 O(n^2)이다. 그래서 우리는 더 나은 정렬된 자료구조를 사용해야 한다. 그건 정렬의 특화된 우선순위 큐이다. 우선순위 큐 정렬(Heap정렬 사용)의 시간복잡도는 O(logn)이다.아이디어는 이러하다. 중간값보다 낮은 숫자들을 담을 maxHeap과 중간값보다 높은 숫자들을 담을 minHeap을 생성한다. maxHeap은.. 2024. 7. 20. 이전 1 다음
