hayu's 개발 일지

학습 키워드- 우선순위 큐(PriorityQueue) 공부한 내용우선순위 큐 선언 방법// 낮은 수가 우선순위를 가짐PriorityQueue pq = new PriorityQueue();// 높은 수가 우선순위를 가짐PriorityQueue pq = new PriorityQueue(Collections.reverseOrder());//String형 priorityQueue 선언 (우선순위가 낮은 숫자 순)PriorityQueue priorityQueue = new PriorityQueue(); //String형 priorityQueue 선언 (우선순위가 높은 숫자 순)PriorityQueue priorityQueue = new PriorityQueue(Collections.reverseOrder());우..

학습 키워드- 우선순위 큐(PriorityQueue) 공부한 내용우선순위 큐(PriorityQueue)큐 자료구조는 선입선출(FIFO) 방식이다.우선순위 큐는 들어간 순서와 상관없이 높은 우선순위를 가진 원소가 먼저 나온다는 특징을 가진다.Heap을 이용하여 구현하는 것이 일반적이다.데이터 추출 시, 루트 노드를 얻어 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입 후 아래 노드로 내려가면서 정렬하는 방식으로 진행된다.숫자가 작을수록 먼저 나오는 큐를 최소힙(Min Heap)이라 하고,숫자가 클수록 먼저 나오는 큐를 최대힙(Max Heap)이라고 한다.우선순위 큐(Heap) 특징 및 시간 복잡도특징높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조이다.→ 우선순위 큐에 들어가는 원소는..

학습 키워드- Graph 공부한 내용그래프 구현 방법그래프는 여러 형태로 구현될 수 있다.주요한 구현 방법에는 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)가 있다.두 가지 구현 방법 중 대부분 인접 리스트 방식을 많이 사용한다.인접 행렬(Adjacency Matrix)2차원 배열을 사용해 그래프를 표현한다.(2차원 배열에 저장한다.)배열의 요소는 노드 사이의 연결 여부를 나타낸다.아래와 같은 그림에서 연결된 vertex는 숫자 '1'이 데이터로 들어가고 연결되지 않은 vertex는 숫자 '0' 혹은 음수가 들어가게 된다. → 다른 노드와 인접 정점이라면 1, 아니면 0을 넣어준다.그래프에 간선이 많이 존재하는 **밀집 그래프(Dense Graph)**의 경우 사용..

학습 키워드- Graph 공부한 내용그래프 Graph 그래프는 객체 또는 개체 간의 관계를 표현하는 자료구조이다.그래프(Graph)는 정점(Vertex)의 집합 V와 간선(Edge)의 집합 E로 구성된 비선형 데이터 구조다.그래프는 노드(Node)와 노드 사이를 연결하는 간선(Edge)으로 구성된다.+ 노드(정점, Vertex) : 일반적으로 개별적인 개체나 개념+ 간선 : 노드 사이의 관계+ 그래프에서 자주 사용하는 용어vertex(정점): 노드(Node)라고도 하며 정점에는 데이터가 저장된다.edge(간선): 링크(arcs)라고도 하며 선을 통해 노드간의 관계를 나타낸다.adjacent vertex(인접 정점): 하나의 정점에서 edge에 의해 직접적으로 연결된 정점을 나타낸다.degree(차수): ..

학습 키워드- Heap 공부한 내용힙은 최소 힙(Min Heap), 최대 힙(Max Heap) 두가지가 있다.최소 힙은 루트노드가 최솟값이 되고, 부모노드의 key는 자식노드의 Key보다 작아야 한다는 규칙이 있다.최대 힙은 루트노드가 최댓값이 되고, 부모노드의 Key가 자식 노드의 Key보다 커야 한다는 규칙이 있다.최소 힙(Min Heap)최소 힙(Min Heap)은 부모 노드의 Key가 자식 노드의 Key보다 작거나 같은 완전 이진 트리이다.단지 부모 노드가 자식 노드의 Key보다 작기만 하면 된다.자바에서 최소 힙을 사용하는 것은 Primary Queue를 그대로 사용해주면 된다.PriorityQueue minHeap = new PriorityQueue();Primary Queue는 우선순위 큐로..

학습 키워드- Heap 공부한 내용Heap (max / min)힙은 완전 이진트리 형태로 최대, 최솟값을 빠르게 찾아내는데 유용한 자료구조이다.힙은 중복값을 허용한다.Java에서는 Collection으로 Heap이 없다. 하지만 Max-Heap과 Min-Heap을  Primary Queue를 활용하여 구현할 수 있다.부모 - 자식 간 (레벨 별) 정렬은 보장하고, 형제간의 정렬은 보장하지 않아서 반 정렬 상태라고 볼 수 있다.힙**(Heap)**의 특징완전 이진 트리(Complete Binary Tree) : Heap은 완전 이진 트리의 형태를 가진다. 이는 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 채워져 있는 형태를 말한다.부모-자식 노드 관계 : Heap의 부모 ..