금융 IT 전문가가 될 때까지!

유니온 파인드 알고리즘(==서로소 집합, 상호 베타적 집합) 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘으로 노드를 합치는 union / 노드를 찾는 find연산으로 구성 트리 구조로 이루어진 자료구조 / 시간복잡도는 = 0(1) 인덱스 1 2 3 4 5 6 7 부모노드 1 2 3 4 5 6 7 임의로 UNION(보통 INDEX가 작은 쪽이 부모노드가 됨). 1-2번, 4-6-7-번 연걀해범 인덱스 1 2 3 4 5 6 7 부모노드 1 1 3 4 4 6 4 Union(x,y) x= find(x); y=find(y); if x!= y if xparent[y] = x else -> parent[x] = y ​ 1)루트, y 루트 연결해줌 2)x와 y과 같지 않으면 3)y가 더 크다면(인덱스가 더 크다..

그래프: 정점과 간선을 이용해 연결되어 있는 원소 사이 다대다 관계 표현한 자료구조로 주로 정점의 집합을 V , 간선들의 집합 E로 표현 차수(degree): 정점에 연결되어 있는 간선의 수 경로(path): 정점 vi에서 vj까지 간선으로 연결된 정점을 순서대로 나열 ex) Vi >> Vj a>f / a>b>e>f / a>b>c>e>f / a>b>c>d>e>f 방향그래프 vs 무방향그래프 >> 보통 무방향(양방향 그래프) 많이 씀. bollean[] is Visited 쓰기 >> 그래프 탐색시 막힌 배열 필수!! 연결그래프 vs 비연결그래프 모든 노드들이 다 연결되어있으며 연결 그래프, 중간에 끊어져있으면 비연결그래프 비연결 그래프 탐색을 하려면 모든 노드를 다 탐색해야함. 비연결 그래프로 생각 필수!..

이진트리 순회 - DFS 깊이 우선 탐색은 리프토드까지 아래로 내려가면서 탐색함. 더 이상 탐색할 곳이 없으면 부모에게 돌아감! 종류 1) 전회 순회(preorder) 노드방문 > 왼쪽자식>오른쪽자식 예시 : A > B > D > H > E > I > J > C > F >G 대표사진 삭제 사진 설명을 입력하세요. 2) 중위 순회(inorder) 왼쪽자식 > 노드방문 > 오른쪽자식 예시 : H > D > B > I > E >J > A > F> C > G 대표사진 삭제 사진 설명을 입력하세요. 3) 후위 순회(postorder) 왼쪽자식 > 오른쪽자식 > 노드방문 예시 : H > D > I > J > E > B > F > G > C > A 백준_1991번 https://www.acmicpc.net/probl..