[알고리즘 개념정리] 11. 분리집합/최소 신장 트리 **본 포스팅은 22Winter 신촌캠프 초급반 강사 raararaara님의 강의를 참고하여 작성하였습니다.** 분리 집합 (Disjoint Set) 서로 겹치는 원소가 없는 집합들을 관리하는 자료구조 서로소 집합, 유니온-파인드 (Union-Find) 포레스트의 일종 Find - 주어진 원소가 포함된 집합의 대푯값을 구하는 연산 - 집합마다 유일한 대푯값 존재 - 나머지 다른 원소에서 대표로 가는 경로 존재 Union - 두 집합을 합치는 연산 - 한 집합의 대푯값을 다른 집합의 대푯값으로 linking int par[1000001], height[1000001]; int find(int num){ if(num==par[num]) return num; //self roop만났음! 즉, 대푯값 찾았음! .. 2022. 2. 17. [알고리즘 개념정리] 10. 최단경로 알고리즘 **본 포스팅은 22Winter 신촌캠프 초급반 강사 dart님의 강의를 참고하여 작성하였습니다.** 가중치 그래프 그래프에 더 많은 정보를 표현하기 위해 간선에 여러 가지 속성을 부여할 수 있는데, 그중 하나가 바로 '가중치'라는 수 하나를 부여하는 것 두 정점간의 거리, 이동시간, 두 물건 사이의 교환비율, 한 정점에서 다른 정점으로 갔을 때 얻을 수 있는 이득/손해 등 -> 간선에 가중치를 부여해보자! 인접 리스트 adj[s].push_back({e,c}); s에서 e로 가는, 가중치 c를 갖는 간선 : pair을 이용해서 간선의 가중치도 같이 넣는다. 인접 행렬 adj[s][e]=c; : 연결을 1로 나타내는 게 아니라 그 가중치로 나타낸다. 최단경로 알고리즘 BFS를 이용하면 그래프에서의 최단경.. 2022. 2. 14. [알고리즘 개념정리] 9. 트리 **본 포스팅은 22Winter 신촌캠프 초급반 강사 raararaara님의 강의를 참고하여 작성하였습니다.** 트리 (Tree) Connected Acyclic Undirected Graph 모든 정점이 이어져있음(연결 그래프) / 사이클 존재하지 않음 / 방향성 없음 계층형 자료구조 리프노드를 제외한 노드들은 T1, T2, ... Tn을 root로 하는 서브트리들을 가진다. 부모/자식, 형제(부모 노드가 같음), 조상(부모 노드들의 집합), 자손(자식 노드들의 집합), 리프 노드, 서브 트리(어떤 노드 t와 그 자손들로 구성된 트리), 포레스트(트리가 여러개) 간선의 개수 = 정점의 개수 -1 : sparse graph 이므로 인접리스트로 표현할 수 있다. 임의의 서로 다른 두 정점 사이의 경로가 유.. 2022. 2. 9. [알고리즘 개념정리] 8. 그래프/그래프 탐색 **본 포스팅은 22Winter 신촌캠프 초급반 강사 dart님의 강의를 참고하여 작성하였습니다.** 그래프 정점(vertice)의 집합 V와 간선(edge)의 집합 E로 이루어지며 보통 (V,E)로 표기한다. 각각의 간선은 두 정점의 쌍으로 나타낸다. 간선에 방향이나 가중치가 부여되는 경우도 있다. 관련 용어 무방향/방향 그래프, 인접, 사이클, 가중치 그래프, 연결 그래프(정점들이 모두 이어져있는 그래프) 간선 표현 방법 인접 리스트 vector adj[100005]; : 간선 개수에 비례하는 메모리만 차지 but 연결성 여부 판단 O(V) 대부분의 경우 정점 개수가 꽤 많기 때문에 인접 리스트가 유리하다. 인접 행렬 int adj[1005][1005]; : 연결성 여부 판단 O(1)에 가능 but .. 2022. 2. 5. [알고리즘 개념정리] 7. 이분탐색/분할정복 **본 포스팅은 22Winter 신촌캠프 초급반 강사 raararaara님의 강의를 참고하여 작성하였습니다.** 이분탐색(Binary Search) : 정렬된 리스트 arr에서 특정한 값 key를 찾는 알고리즘 탐색 구간의 중앙값 mid와의 대소 비교를 통해 다음 탐색 구간을 설정함 탐색 연산이 반복적으로 요구될 때 사용함 key값의 유무를 반환함 https://www.acmicpc.net/blog/view/109 bool binary_search(int *arr, int len, int key){ int l = 0; int r = len-1; int mid; while(l key) { //key값이 mid 값보다 작으면 왼쪽으로 r = mid - 1; } else { //key값이 mid 값보다 크면 .. 2022. 2. 2. [알고리즘 개념정리] 6. 완전탐색/백트래킹 **본 포스팅은 22Winter 신촌캠프 초급반 강사 dart님의 강의를 참고하여 작성하였습니다.** 완전 탐색(Brute Force) : 모든 경우를 탐색해 가면서 무언가를 세거나 어떤 조건이 가능한 경우가 있는지 확인하는 방법 ★ 완전 탐색 문제 판별법 하나의 경우마다 따져야 할 게 명확한 경우 어떤 상태를 구성하고, 그 상태가 특정 조건을 만족하는지 검토해야 하는 등의 문제 나올 수 있는 경우의 수가 모두 탐색할 수 있을 만큼 적은 경우 (N제한이 작을 때!!) ★ 완전 탐색 문제 접근법 모든 경우(상태)를 생성할 수 있는 방법을 생각한다. 각각의 경우에 대해 그 문제의 조건을 만족하는지 체크한다. * 문제에 따라 모든 경우를 따질 필요가 없거나 각 경우에 대해 체크할 조건이 없는 등의 상황도 있다.. 2022. 1. 29. 이전 1 2 다음
