[자료구조] 그래프(Graph) -그래프: 트리와 같은 비선형 자료구조 이며 각각의 노드 (객체) 를 연결한 자료구조 연결한 객체를 정점 이라고 부르고 연결 선은 간선 이라고 부른다. 그래프의 예시 번호가 새겨진 원을 보통 노드 라고 하고 그 노드를 연결하는 파란 선을 간선 이라고 표시합니다. - 그래프와 관련된 용어 정점 : 각각의 노드간선 : 노드를 연결하는 선크기 : 정점의 개수인접 : 두개의 정점을 연결하는 간선이 있을 때, 두 정점은 인접하다경로 : 정점 V1에서 Vn의 시퀀스경로의 길이 : 간선의 개수 n 사이클 : 임의의 노드에서 자기 자신으로 돌아오는 경로단순 사이클 : 처음과 마자막 정점이 같은 사이클비순환 그래프 : 사이클이 없는 (ex 트리) 그래프 - 그래프의 구현 방법그래프를 구현하는데는 크게 두가지 방법이 있습.. 자료구조 7년 전
[자료구조] 해시테이블 자료구조에서는 데이터의 접근에서 두 가지의 접근 방법이 있습니다. 순차 접근 직접 접근 연결 리스트 배열 한쪽 끝에서 목표 혹은 다른 끝에 도달할 때 까지 탐색 인덱스를 이용한 탐색(인덱스를 알아야함) 선형 시간 상수시간 순차 접근은 탐색 시간이 오래 걸리는데 비해 데이터의 삽입, 삭제로 인한 불필요한 이동이 없는 반면에 직접 접근은 탐색 시간이 빠르지만 데이터의 이동에 불편한 점이 있습니다. 각각의 단점을 보완하기 위한 것이 해시 테이블 (hash table) 입니다. ※해시 : 원소들이 무 순서로 섞여 있다 - 해시 테이블 - 원소의 인덱스에 대한 지식 없이 직접 접근 가능 - 인덱스를 계산하는 해시 함수 사용 - 레코드와 테이블 레코드 : 여러 개의 컴포넌트를 가진 복합적인 자료구조테이블 : 동일 .. 자료구조 7년 전
kruskal 알고리즘 최소 신장 트리 (MST)를 구할 때 사용하는 알고리즘최소 신장 트리 : 그래프의 모든 정점이 연결된 서브 그래프, 그 중 모든 가중치의 합이 최소인 트리 Union & Find 연산은 제외한 코드입니다. (Union : 집합 A와 집합 B를 합침, Find : 원소 A를 가지고 있는 집합을 찾음) 간선(edge)은 오름차순으로 정렬되 있다. 정점 v가 정점 w와 이미 같은 집합에 있다면 cycle을 형성하므로 최소 신장 트리가 되지 않는다. 같은 집합에 없다면 집합을 합친다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253public void kruskal(){ Edge k[].. 자료구조 7년 전
[Dijkstra] 최단 경로 알고리즘 in Java Dijkstra 알고리즘이란 ? 가중치 그래프 사이의 정점 Vx로 부터 Vy까지의 최단 경로를 구하는 알고리즘입니다. [최단 경로 알고리즘]1. 시작 정점 X 지정2. X와 인접하고 방문되지 않은 정점 탐색3. 가장 짧은 가중치를 갖는 정점부터 방문4. 정점 Y에 대한 최단경로가 나올 때 마다 업데이트 자료구조 8년 전
[algorithm] 버블정렬(Bubble Sort) 데이터 정렬 알고리즘 중 사용하기 쉽다. 버블정렬(Bubble Sort)은 간단하게 말하면 인접한 두 수(데이터)를 비교해서 큰 쪽과 작은 쪽의 자리를 바꿔주는 알고리즘이다.자동으로 가장 큰수는 N번째에 가는 거고 가장 작은쪽은 0번째에 오게 되는 것이다. (코드로 이해하는게 더 빠르다. 어차피 쉬운 개념이기 때문에...) 이중 for문을 사용했고 숫자의 갯수(N번)만큼 돌아가면 된다. ↓ ↓ ↓ 자료구조 8년 전
