Algorithm11

• 

  [알고리즘] 세그먼트 트리(Segment Tree) 알고리즘 동작 원리 및 구현하기 세그먼트 트리 알고리즘 개요 세그먼트 트리 알고리즘은 트리 형태의 자료구조를 사용한다. 특정 구간 내 데이터에 대한 연산(쿼리)을 빠르게 구할 수 있는 트리 알고리즘이다. 키워드 구간 범위 시간복잡도 데이터 변경 : O(logN) 연산 : O(logN) 데이터 변경 시마다 M번 연산 : O((logN + logN) * M) = O(MlogN) 특징 누적 합을 담은 트리라고 가정하자. N = 10 (노드의 개수 : 10) 인 그림에서 노드안에 적힌 순서는 값이 아닌 각 노드의 고유 번호라고 했을 때, 각 노드가 저장하고 있는 합의 범위(구간)를 나타낸 것이다. 각 노드는 다음과 같은 의미를 가진다. 리프 노드 : 해당 노드의 값 자체 리프 노드가 아닌 노드 : 왼쪽 자식과 오른쪽 자식의 합(누적 합 예시).. Algorithm/Tree & Graph 2022. 10. 26.

• 

  [자료구조] 자바 덱(Deque)의 클래스 사용하기 카프카의 소스코드를 보던 중 내부에서 Deque 클래스를 사용한 부분을 보게 되었다. Deque(덱 혹은 데크)은 Double-Ended Queue의 줄임말로 큐의 양쪽으로 엘리먼트의 삽입과 삭제를 수행할 수 있는 자료구조를 의미한다. 참고 : 월급쟁이의 경제적 사유 덱(Deque)은 어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라서 스택(Stack)으로 사용할 수도 있고, 큐(Queue)로도 사용할 수 있다. 특히 한쪽으로만 입력 가능하도록 설정한 덱을 스크롤(scroll)이라고 하며, 한쪽으로만 출력 가능하도록 설정한 덱을 셸프(shelf)라고 한다. Java에서의 Deque 자바에서의 덱은 인터페이스로 구현되었다. 덱 자료구조의 여러 연산들을 정의한 Deque 인터페이스가 있고 이를 구현한 Ar.. Algorithm/Stack & Queue 2022. 7. 7.

• 

  [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 동작 원리 및 구현하기 다익스트라 알고리즘 개요 다익스트라(dijkstra) 알고리즘은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점(노드) 뿐만 아닌, 다른 정점까지 최단 경로로 방문하여 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복한다. 그래프 알고리즘 중 최단 거리, 최소 비용을 구하는 알고리즘은 다익스트라 외에 벨만-포드 알고리즘, 프로이드 워샬 알고리즘 등이 있다. 동작 단계 출발 노드와 도착 노드를 설정한다. '최단 거리 테이블' 을 초기화한다. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. (선택한 노드는 방문 처리한다.) 해당 .. Algorithm/Tree & Graph 2022. 7. 7.

• 

  [자료구조] 자바 우선순위 큐(Priority Queue)의 클래스 사용하기 Priority Queue 일반적인 큐의 구조 FIFO (First In First Out)을 가진다. 우선순위를 먼저 결정하고, 우선순위가 높은 데이터가 먼저 나가는 구조이다. 우선순위 큐를 사용하기 위해 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야한다. Comaprable Interface 구현 시 compareTo method 를 override 하여 처리할 우선순위 조건을 리턴하면, 우선순위 큐가 우선순위가 높은 객체를 추출해준다. (기본적으로 낮은 숫자부터 큰 숫자 오름차순이다) Heap을 이용하여 구현하는 것이 일반적이다. 데이터 삽입 시 우선순위 기준으로 최대 힙, 최소 힙을 구성한다. 데이터 추출 시, 루트 노드를 얻어 루트 노드를 삭제할 때는 빈.. Algorithm/Stack & Queue 2022. 7. 5.

• 

  [자료구조] 자바 스택(Stack)의 클래스 사용하기 스택(Stack)의 특징 1. 먼저 들어간 데이터가 나중에 나오는 후입선출, LIFO (Last In First Out) 구조로, 마트용 음료수 진열대와 같은 구조이다. 2. 한 쪽 끝에서만 데이터를 넣고 뺄 수 있는 자료 구조여서 데이터를 쌓는 형식으로 저장하며 조회, 추가, 삭제 등 모두 가장 위에 있는 (가장 마지막에 삽입된) 값에서 이루어진다. 이 데이터를 Top이라고한다. 3. 그래프(Graph)의 깊이 우선 탐색(DFS)에 사용된다. 4. 재귀적(Recursion) 함수를 호출할 때 사용한다. 스택(Stack) 클래스 선언 import java.util.Stack; Stack stack = new Stack(); 메서드 public Element push(Element item);// 데이터 .. Algorithm/Stack & Queue 2022. 6. 19.

• 

  [자료구조] 자바 큐(Queue)의 클래스 사용하기 큐(Queue)의 특징 1. 먼저 들어간 데이터가 먼저 나오는 선입선출, FIFO(First In First Out) 구조로, 줄을 서서 기다리는 구조와 같다. 2. 한 쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행한다. 3. 한 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행한다. 4. 그래프(Graph)의 넓이 우선 탐색(BFS)에 사용된다. 큐(Queue) 클래스 큐(Queue) 선언 자바에서 큐(Queue)는 LinkedList를 활용해서 사용한다. import java.util.Queue; import java.util.LinkedList; Queue queue = new LinkedList(); 큐(Queue) 동작 및 메서드 Enqueue 동작 큐에 데이터를 추가하는 동작으로 o.. Algorithm/Stack & Queue 2022. 6. 19.

• 

  [자료구조] Binary Heaps (Min-Heap and Max-Heap) 간단하게 알아보기 Heap ? 힙(Heap)은 이진 힙(Binary Heap)이라고도 하며, 최대 값이나 최소 값을 빠르게 구하기 위해 구현된 완전이진트리(Complete Binary Tree)를 기본으로 한 자료구조 힙(Heap)의 속성 - 완전 이진트리 (Complete Binary Tree) - 부모 노드와 자식노드의 값 사이에 대소관계 성립 (형제노드사에의 대소관계는 정해지지 않음) 힙(Heap)의 종류 - 최소힙 (Min Heap) : 부모 노드가 자식 노드보다 항상 작은 값을 가지고 있고, 가장 작은 값이 루트(root)인 트리구조 - 최대힙 (Max Heap) : 부모 노드가 자식 노드보다 항상 큰 값을 가지고 있고, 가장 큰 값이 루트(root)인 트리구조 최소 힙의 노드 삽입하기 1. 완전이진트리에 맨 끝.. Algorithm/Tree & Graph 2022. 6. 5.

• 

  [자료구조] 연결 리스트 (Linked List) 간단하게 알아보기 연결 리스트 (Linked List) 단방향/양방향 Linked List의 개념 단방향 Linked List 구현하기 (in Java) 연결 리스트 (Linked List) 컴퓨터의 자료를 저장하는 구조의 한 종류로, 일렬로 이루어진 데이터를 저장할 때 사용한다. Linked List 에는 배열과의 비교를 빼놓을 수가 없는데, 배열은 배열 방들이 물리적으로 한 곳에 모아져있고, 배열 방 크기를 한 번 정하면 늘리거나 줄일 수 없다. 노드를 삽입하는 경우, 배열로 구현을 해야한다면, 노드 한 개 추가될 때마다 배열 방을 통째로 다시 선언해서 데이터를 다시 복사하고, 추가하는 과정을 반복해야하는 반면, Linked List는 중간에 삽입하고자 하는 노드가 있을 때, 앞 노드가 가지고 있던 주소를 삽입할 노드.. Algorithm/Linked List 2022. 6. 5.

• 

  [자료구조] 알고리즘 표기법 : 빅오(Big-O notation) 란 ? Big-O ? - 알고리즘의 성능을 수학적으로 표현해주는 기법 - 알고리즘의 시간과 공간복잡도를 표현 - Big-O 표기법은 알고리즘의 실제 러닝타임을 표기하는 것이라기보단, 데이터나 사용자의 증가율에 따른 알고리즘 성능을 예측하는게 목표이기 때문에 상수와 같은 숫자들은 모두 1이 된다. O(1) : constant time 입력데이터 크기와 상관없이 언제나 일정한 시간이 걸리는 알고리즘의 시간복잡도 F(int[] n) { return (n[0] == 0) ? true : false; } n의 크기가 1개이던 100,000개이던 상관없이 언제나 일정한 속도로 결과를 반환하는 이런 알고리즘을 'O(1)의 시간복잡도를 가진다' 라고 표현한다. O(n) : linear time 입력데이터 크기에 비례해 처리시.. Algorithm/Big O 2022. 6. 5.

• 

  [자료구조] Tree의 종류 및 Binary Tree의 3가지 순회 방법 간단하게 알아보기 목차 Tree ? Tree의 종류 Binary Tree Binary Search Tree Complete Binary Tree Full Binary Tree Perfect Binary Tree Binary Tree 3가지 순회방법 Inorder (Left, Root, Right) Preorder (Root, Left, Right) Postorder (Left, Right, Root) Tree ? 그 동안 많이 접해왔던 Array, LinkedList, Stack, Queue 와 같이 라인처럼 생긴 일직선 데이터들이 있다면, 트리(Tree)는 부모 자식 관계를 가지는 구조이며, 계층과 그룹이 있다. 각 노드(Node)는 하나 이상의 자식을 갖고 있다. 트리(Tree) 노드(Node) 중에는 부모를 아는 경.. Algorithm/Tree & Graph 2022. 6. 3.

• 

  [자료구조] 그래프(Graph)의 개념 및 탐색 간단하게 알아보기 그래프(Graph)의 용어 트리(Tree)와 그래프(Graph)의 차이 그래프(Graph)의 특징 : Directed, Undirected, Cyclic, Acyclic 그래프(Graph)를 표현하는 방법 : Adjacency Matrix, Adjacency List 그래프(Graph)의 탐색 : DFS(깊이 우선탐색), BFS(넓이 우선탐색) 그래프(Graph)의 용어 정점(vertice) : 노드(node)라고도 하며 정점에는 데이터가 저장됩니다. (0, 1, 2, 3) 간선(edge): 링크(arcs)라고도 하며 노드간의 관계를 나타냅니다. 인접 정점(adjacent vertex) : 간선에 의해 연결된 정점으로 위에서 (정점0과 정점1은 인접 정점) 단순 경로(simple-path): 경로 중 반.. Algorithm/Tree & Graph 2022. 5. 23.