728x90 자료구조9 [자료구조] 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. [JAVA] Priority Queue Priority Queue 우선순위 큐는 먼저 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 우선순위가 높은 원소가 먼저 나가는 자료구조입니다. 보통 힙을 이용하여 구현하는 것이 일반적입니다. PriorityQueue pq = new PriorityQueue(); PriorityQueue pq = new PriorityQueue(Collections.reverseOrder()); 첫 줄은 낮은 숫자 순, 두번째 줄은 높은 숫자순 우선순위 큐입니다. 메소드 종류 add(), offer() 우선순위 큐에 요소를 삽입합니다. 넣어지면서 동시에 정렬도 알아서 합니다. clear() 우선순위 큐의 모든 요소를 삭제합니다. contains(값) 해당 큐에 값이 있다면 true를 반환합니다. p.. 2021. 10. 30. 이전 1 2 3 다음 728x90