728x90 Computer Science/자료구조8 [자료구조] Graph 개인적으로 나는 그래프가 어렵다. 자료구조를 배운 이래, 가장 진입하기 힘들었던 자료구조다. 물론 아직도 잘 모른다. 더욱이 이를 활용한 문제 풀이는 아직 먼 산이다... 그러므로 그래프에 대해 공부해본다. 자바로 한다. 그래프는 정점을 간선으로 연결한 것 그 이상도 이하도 아니다. 가장 단순한 모델은 무방향 그래프. 그래프의 정의는 이렇다. 정의 | 그래프는 정점의 집합과 그 집합의 정점 쌍을 연결하는 간선의 모음이다. 그래서 어디서 이용할까? 지도, 컴퓨터 네트워크, 소셜 네트워크 등등... 어떤 항목들을 연결하는 것이 핵심이다. 연결은 어떤 관계를 의미한다. 즉, 특정 항목들의 연결 상태, 경로 추적 등등에서 이용된다. 용어 정점, V | 쉽게 생각하면 꼭짓점이다. 간선, E | 쉽게 생각하면 선분.. 2022. 1. 31. [자료구조] 힙 힙이란? 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조입니다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조입니다. 힙은 일정의 반정렬 상태를 유지합니다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도입니다. 간단히 말하면 부모 노드의 값이 자식 노드의 값보다 항상 크거나 작은 이진트리입니다. 힙 트리에서는 중복된 값을 허용합니다. (이진트리에선 허용 안합니다.) 힙의 종류 최대힙 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리입니다. 최소힙 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리입니다. 2021. 12. 1. [자료구조] JAVA로 구현해보는 자료구조 Array //초기 크기 설정 후, for문으로 값 넣기 int[] array = new int[5]; for (int i = 0; i < array.length; i++){ array[i] = i+1; } //그냥 처음부터 값 넣기 int[] second_array = new int[]{1,2,3,4,5}; ArrayList //타입 설정을 하지 않으면 Object로 선언 ArrayList arrayList = new ArrayList(); //int타입만 사용 가능 ArrayList int_arrayList = new ArrayList(); //초기 크기 설정 ArrayList capacity_arraylist = new ArrayList(10); //생성 시 값 추가 ArrayList integer.. 2021. 11. 15. [자료구조] Graph 정의 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조입니다. 노드는 보통 vertex로 v, 간선은 보통 edge로 e를 많이 사용합니다. 특징 방향 그래프와 무방향 그래프 모두 존재합니다. 사이클 가능, 자체 간선도 가능, 순환 그래프, 비순환 그래프 모두 존재합니다. 딱히 루트 노드의 개념은 없습니다. 물론 부모-자식 개념도 희미합니다. 순회는 DFS,BFS를 사용합니다. 그래프는 네트워크 모델입니다. 인접 리스트 혹은 인접 행렬로 구현합니다. 2021. 10. 27. 이전 1 2 다음 728x90