전체 글

❒ Description이중 연결 리스트(Doubly-Linked List )에 대해서 알아보자.   ❒ Doubly-Linked List 실제 자바에서 제공하는 util 패키지의 LinkedList는 DL-List랑 같은 형식으로 되어있다. Singly LinkedList와의 차이라면 단일 연결리스트는 노드에 데이터와 다음 노드를 가리키는 노드 변수만을 갖고 있었다면 DL-List는 하나 더 추가되어 '이전 노드'를 가리키는 변수가 추가 된다. Singly LinkedList에 비해 검색(색인)능력이 좋아진다. 단방향으로 연결 된 Singly LinkedList의 경우 반드시 head부터 시작하여 탐색하였다. 만약 10개의 노드가 있고,9번 째 노드를 탐색하려고 한다면, head부터 탐색했어야 했다.하..

❒ Description우선순위 큐(Priority Queue)에 대해서 알아보자.   ❒ Priority Queue우선순위 큐(Priority Queue)는 스택과 큐와 같은 추상자료형(ADT)이다.Queue와 거의 비슷하지만, 각 요소들이 우선순위를 갖고 있다는 차이점이 있다.  P-Queue는 여러가지 자료구조로 구현이 가능하다.위와 같이 여러 구현 방식이 있지만, 최악의 경우에도 시간복잡도가 O(logN)인 'Heap(힙)' 자료구조를활용하는 방식이 가장 대표적이다.     ❒ Java에서 Priority Queue 선언하기기본적으로 아래와 같이 P-Queue를 선언한다. 이 경우는 작은 숫자가 우선순위를 가지는 P-Queue이다.PriorityQueue pq = new PriorityQueu..

❒ Description제목Merge K sorted Lists링크https://leetcode.com/problems/merge-k-sorted-lists/description/자료구조선형 (우선순위 큐)시간복잡도O(nlogk) 이번 문제에서도 가상의 노드 Root를 사용되었다. 이쯤 느껴지는 것은 뭔가 정렬이 들어가는경우에는 가상의 노드 접근을 생각해보는 것도 좋은 거 같다. 아무튼 문제의 핵심은 자료구조 Priority Queue를 사용해서 해결하는 문제였다.Priory Queue에 대한 정리는 이곳에 할 것이다.    ❒ Solution전체 코드더보기public ListNode mergeKLists(ListNode[] lists) { PriorityQueue pq = new PriorityQ..

❒ Description네트워크 기기는 계층별로 처리 범위를 나눌 수 있다. 그리고 상위 계층을 처리하는 기기는 하위 계층을 처리할 수 있지만,그 반대는 불가능 하다. 이번에는 계층별 네트워크 기기에 대해서 자세히 공부한다.   ❒ 애플리케이션 계층을 처리하는 기기1. L7 스위치L7 스위치는 여러 장비를 연결하고, 데이터 통신을 중재하며 목적지가 연결된 프로토콜만 전기 신호를보내 데이터를 전송하는 통신 네트워크 장비다. L7 스위치는 로드벨런스라고 부르기도 한다.이와 관련된 내용은 깃블로그 참고하기.   ❒ 인터넷 계층을 처리하는 기기1. 라우터라우터란 여러 개의 네트워크를 연결, 분할, 구분시켜주는 역할을 하며 "다른 네트워크에 존재하는 장치끼리서로 데이터를 주고받을 때 패킷 소모를 최소화하고 경로를..

❒ Description[LeetCode#641] Design Circular Deque에서 Array와 Doubly-Linked list를 통해서 Circular-DQ를 구현해봤다. 하지만 Doubly-Linked list를 통한 구현은 원형 큐의 이점을 잘 살리지 못한다고 했다.여기서는 왜 이점을 살리지 못하는지 정리해본다.   ❒ 동작원리1. insertFrontFront 앞에 새로운 데이터를 삽입한다.Front가 현재 0번 째 index를 가리키고 있다면, Front는 마지막 index를 가리키도록 변경된다. 2. insertLastRear 뒤에 새로운 데이터를 삽입한다.Rear가 현재 마지막 index를 가리키고 있다면, Rear는 첫 번째 index를 가리키도록 변경된다.   ❒ Why?1. ..

❒ Description제목Design Circular Deque링크https://leetcode.com/problems/design-circular-deque/description/자료구조선형 (배열 / 이중 연결 리스트)시간복잡도O(1)이번 문제는 이중 연결 리스트로 Circular-Deque를 구현하는 문제였다.근데 사실 이중 연결 리스트로  Circular-Deque를 구현하면 원형의 이점을 살릴 수 없다.실제로 원형의 이점을 살리기 위해선 이 문제를 연결리스트가 아닌 배열로 풀이해야 한다.따라서 이번 문제는 이중 연결 리스트와 배열 모두 구현 해볼 것이다.   ❒ Solution1. 이중 연결 리스트 (Doubly-Linked List)더보기public class MyCircularDeque {..

❒ DescriptionDesign Circular Queue 문제를 풀면서 알게된 Circular Queue에 대해 학습한다.긱포기 Circular Queue 포스팅을 참고했다.   ❒ Circular Queue란?Circular-Q는 normal-Q의 확장 버전으로 다음과 같은 특징을 갖고 있다.마지막 요소(rear)와 첫 번째 요소(front)가 연결된 구조를 갖는다.이런 구조로 인해 Buffer-Ring이라고 부르기도 한다.FIFO 원칙을 기반으로 한다.  ❒ Operations of Circular-Q1. FrontQ의 앞쪽 요소를 반환한다.2. RearQ의 뒤쪽 요소를 반환한다.3. enQueue(value)새로운 요소를 삽입할 때 사용한다.새로운 요소는 항상 rear 위치에 자리한다.4. d..

❒ Description제목Design Circular Queue링크https://leetcode.com/problems/design-circular-queue/description/자료구조선형 (배열)시간복잡도O(1)이 번 문제는 배열을 사용해서 Circular-Queue(원형 큐)를 구현하는 문제이다.   ❒ Solution public class MyCircularQueue { int q[]; int front = 0; int rear = -1; int len = 0; public boolean enQueue(int value) { if (!isFull()) { rear = (rear + 1) % q.length; q[r..