CS Study

1. Disjoint set(서로소 집합)- Disjoint set(Union Find)는 대표적인 그래프 알고리즘이다.- 여러개의 노드가 존재할 때 두 개의 노드를 선택헤서 현재 이 두 노드가 서로 같은 그래프에 속하는 지 판별하는 알고리즘/ - 해당 그래프를 표로 나타내면 다음과 같다.012345000144 - 이렇게 부모를 합칠 때 일반적으로 더 작은 값 쪽으로 합친다. 이를 합침(Union)이라고 한다. - 하지만 해당 graph에서 3과 0이 연결되어있는지 어떻게 파악할 수 있는지가 관건이 된다.- 0의 부모는 0 3의부모는 1이므로 '부모노드'만 보고는 한번에 파악이 불가능이다. --> 그렇기에 재귀함수를 이용하여 해결 가능하다.ex)3의 부모노드 -> 11의 부모노드 -> 00의 부모노드 =..

1. B-tree?- B-tree는 Tree Data Structure의 일종으로 Binary Tree를 확장하여, - 하나의 노드의 차수의 최댓값이 2보다 큰 Tree 라고 말 할 수 있다.https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Tree [자료구조] 그림으로 알아보는 B-TreeB트리는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 벨런스를 맞추는 트리입니다.velog.io- B-tree에 대해 자료를 수집하는 중, 가장 정리가 잘된 블로그를 공유한다. - B-tr..

1. Amortized Analysis?- 분할 상환 분석(Amortized Analysis)에 대해서 알아보자.- Amortized Analysis는 알고리즘의 시간 복잡도를 분석하는 방법 중 하나로, 특정 연산의 평균 실행 시간을 계산하는 데 초점을 둠- 이는 최악의 경우 시간 복잡도를 항상 고려하는 Worst-case Analysis와 달리, 일련의 연산이 여러번 반복되는 경우 전체 작업에 대한 총 수행 시간을 분석하여 ''연산당 평균 비용''을 구하는 데 초점을 맞춘다. 2. Amortized Analysis가 필요한 이유- 어떤 데이터 구조나 알고리즘에서는 일부 연산이 매우 비싸지만, 다른 연산들은 거의 비용이 들지 않는 경우가 있다.ex) 동적 배열, Hash table...- 이때 단순히 최..

1. Greedy Algorithm?- 매 순간 국소적인 최적해를 찾는 과정을 반복함으로써 전체 문제에 대한 해를 찾는 문제 해결의 한 패러다임- Greedy Algorithm으로 얻은 해가 전체 문제에 대해 반드시 최적의 해라는것을 항상 보장 불가 2. Greedy Algorithm의 최적해를 가질 때2.1. ex 1) 거스름 돈(각각의 동전들이 배수관계)https://www.acmicpc.net/problem/11047n, k = map(int,input().split())cost = list(int(input()) for _ in range(n))cnt = 0 for _ in range(n): p = cost.pop() cnt += k//p k = k%pprint(cnt) 3. 결론..