지적 겸손함

목차1. 신장 트리2. 최소 신장 트리3. 유니온 파인드(Union - Find) 알고리즘 4. 크루스칼(Kruskal) 알고리즘 5. 백준 1197 최소 스패닝 트리 - 크루스칼 6. 프림(Prim) 알고리즘 7. 백준 1197 최소 스패닝 트리 - 프림8. 참고자료  신장 트리 신장 트리 주어진 방향성이 없는 그래프에서 부분 그래프(Subgraph)들 중에서 모든 정점을 포함하는 트리를 의미한다.→ 무방향이면서 사이클이 없는 → 트리신장 트리는 v개의 정점을 가질때 v-1개의 정점을 가진다. (트리의 성질) 부분 그래프일부 정점과 간선만을 선택해서 구성한 새로운 그래프 신장 트리가 아닌 그래프 예시 최소 신장 트리 신장 트리 중에서 간선의 합이 최소인 트리를 의미최소 신장 트리는 동일한 그래프에서 한..

목차 설명 + 시간 복잡도Heap 설명Heap의 삽입 순서Heap (삽입)Insert SimulationHeap FindHeap Erase Simulation 자바 PriortyQueue 계층 구조 이진 검색 트리 기반 vs heap 기반참고자료설명 + 시간 복잡도우선순위 큐 = pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐원소의 추가가 O(lg N)우선순위가 가장 높은 원소의 확인 O(1)우선순위가 가장 높은 원소의 제거가 O(lg N)그냥 배열로 구현을 하면 세 연산의 시간복잡도가 O(1), O(N), O(N)이 되겠지만Heap 구조를 이용하면 O(lg N), O(1), O(lg N)에 가능하다. Heap이진 트리의 모양을 가지는 자료 구조이진 트리 : ..

TreeSet, TreeMap  -  자바 이진 검색 트리 기반 자료 구조 TreeSetTreeMap이진 검색 트리에 대한 자세한 내용 https://20240228.tistory.com/87 [BinarySearchTree] 이진 검색 트리목차트리 용어 정리이진 트리이진 검색 트리연산(Insert, Delete, Update, Find) 시뮬레이션이진 검색 트리 - 시간 복잡도자가 균형 트리용어 정리정점 : 트리에서의 각 원소루트 : 주어진 트리에서의 120240228.tistory.comTreeSet정렬된 집합 (Set)을 구현한 클래스, 이진 검색 트리 기반중복된 요소 허용 x - SortedSet 인터페이스의 확장요소들이 정렬된 순서로 저장 - SortedSet 인터페이스의 확장내부적으로 레드 -..

NavigableSet Java 컬렉션 프레임워크에서 제공하는 인터페이스SortedSet 인터페이스의 확장정렬된 집합(Set)에 대한 탐색 및 탐색 기반의 연산 지원TreeSet은 NavigableSet 인터페이스를 구현하여 네비게이션 기능 제공public interface NavigableSet extends SortedSetNavigableSet 계층 구조 NavigableSet 메서드 정리 lower(E e) : 주어진 요소 e 보다 작은 요소 중에서 가장 큰 요소를 반환한다.floor(E e) : 주어진 요소 e 와 같거나 작은 요소 중에서 가장 큰 요소를 반환ceiling(E e) : 주어진 요소 e 와 같거나 큰 요소 중에서 가장 작은 요소를 반환higher(E e) : 주어진 요소 e 보다 ..

목차트리 용어 정리이진 트리이진 검색 트리연산(Insert, Delete, Update, Find) 시뮬레이션이진 검색 트리 - 시간 복잡도자가 균형 트리용어 정리정점 : 트리에서의 각 원소루트 : 주어진 트리에서의 1번 정점리프 : 제일 말단에 위치해서 아래로 뻗은게 없는 정점간선 : 정점을 연결하는 선부모 - 자식 관계 : 간선으로 연결된 위 아래의 관계서브 트리 : 어떤 한 정점에 대해 그 밑에 있는 정점과 간선만을 모은 트리트리의 높이 : 위 아래로 뻗어있는 정도이진 트리 (Binary Tree)각 노드의 자식이 2개 이하인 트리이진 검색 트리 (Binary Search Tree)왼쪽 서브트리의 모든 값은 부모의 값보다 작고 오른쪽 서브트리의 모든 값은 부모의 값보다 큰 이진 트리 왜 이진 검색 ..

목차해시?충돌?충돌회피(Chaining)충돌회피(OpenAddressing)OpenAddressing (Linear Probing)OpenAddressing (Quadratic Probing)OpenAddressing (Double Hashing)해시해시 자료구조 : 키(Key)에 대응하는 값(Value)을 저장하는 자료구조 이러한 테이블을 해시 테이블이라고 한다.이렇게 해시 함수를 이용해서 해시 테이블을 구현하면 삽입(put), 삭제(remove), 검색(get) 등 모든 연산이 O(1)에 동작한다.충돌 충돌 현상 설명카드 번호 0000 0000 0000 5135 : kim 을 삽입이때 카드 번호 9999 9999 9999 5135 는 누구의 카드 번호인가 질문그럼 Kim이라고 대답한다.Kim의 카드 ..

https://www.acmicpc.net/problem/1676문제N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)출력첫째 줄에 구한 0의 개수를 출력한다.정답 코드 import java.util.*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long cur = 1; int cnt = 0; for (int i = 1; i

목차1. 30의 배수 :  백준 [10610] 30   2. 크기가 매우 커지는 곱하기 : 백준 [1456] 거의 소수 30의 배수 관련 문제 : 백준 [10610] 30   https://www.acmicpc.net/problem/10610 문제 설명 숫자가 주어지고 포함된 숫자를 섞어서 30의 배수가 되는 가장 큰 수를 만들고 싶다. ex) 102                    210ex)  80875542         88755420 N을 입력받는다. N는 최대 10^5개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.입력 크기가 long으로 담지 못할 만큼 큰 숫자이다. 어떻게 해결할까?먼저 30의 배수가 되는 조건을 생각해 보자. 30은 3과 10의 LCM 이다.  1. 숫자의 각 자릿..

https://www.acmicpc.net/problem/11051import java.util.Scanner;public class Main { static final int INF = 10007; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); long [][] DP = new long[n+1][n+1]; for (int i = 1; i

https://www.acmicpc.net/problem/11050import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); ..