본문 바로가기
728x90

그래프3

[Algorithm] 그래프 그래프 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조 정점의 개수 v개, 간선의 개수 e개 일 때 최대 간선의 개수 : v(v-1)/2 선형 자료구조 / 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이 그래프 유형 무향/유향 그래프 : 방향의 유무 가중치 그래프 사이클 없는 방향 그래프 완전 그래프 : 정점들에 대해 가능한 모든 간선들을 가진 그래프 부분 그래프 : 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프 그래프 표현 # 노드, 간선의 개수 V, E = 7, 8 # 간선의 연결 (무방향) temp = [1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7] 위와 같은 입력이 들어왔을 .. 2021. 10. 20.
[SWEA/Python] 1251. 하나로 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 Prim 알고리즘을 사용하였다. 임의의 섬을 하나 선택하고 방문체크한다. 아직 방문하지 않은 섬을 순회하면서 현재 섬과의 거리와 이미 dist에 저장된 거리를 비교해서 더 작은 값을 dist에 저장한다. 방문하지 않은 섬을 순회하면서 dist가 최소인 섬을 고르고 방문체크한다. 4번의 섬이 2번의 섬과 연결된 것이므로 4번의 섬에 저장된 dist를 E를 곱해서 pay에 더해준다. 모든 섬을 방문할 때까지 위의 과정 반복 📌 코드 import sys sys.stdi.. 2021. 10. 15.
[Algorithm] Tree 트리 (Tree) 그래프 자료구조 중 하나 그래프와 트리의 차이점 싸이클 존재 여부 : 트리는 싸이클이 없다! 루트 노드가 반드시 하나 부모 노드가 반드시 하나 트리는 일반적인 경우, 암묵적으로 방향 표기x (단방향) 비선형 구조 : 원소들 간에 1 : n 관계 원소들 간에 계층관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양의 구조 용어 정리 트리 : 한 개 이상의 노드로 이루어진 유한 집합 부 트리 (subtree) : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리, 최상위 노드를 제외한 나머지 노드들은 분리집합으로 분리가능 -> 이는 각각 하나의 트리가 되며 (재귀적 정의) 루트의 부 트리 노드 (node) : 트리의 원소 (A, B, C, D, E, F, .. 2021. 10. 3.
728x90

티스토리툴바