wonseok.log wonseok.log

c++ STL 중 하나인 Deque에 대한 설명입니다. Deque Deque는 Double-ended queue의 약자로 양쪽 어디에서든 추가, 삭제가 가능한 구조인 큐입니다. Queue 에서는 원소를 접근하기 위해서 front를 통해 하나씩 가져왔다면, Deque는 iterator와 index 접근이 모두 가능합니다. push_back, push_front, pop_back, pop_front와 같은 API를 사용하여 어디에서든 추가가 가능하고 front, back 함수를 통해 원소를 쉽게 가져올 수 있습니다. API 형태나 index 접근이 가능한것만 보면 Queue 보다는 Vector의 형태처럼 보이고, 오히려 vector보다 양쪽 끝 원소는 쉽게 가져올 수 있기 때문에 상위호환처럼 보일 수 있습니..

이 글은 "온라인 자바 스터디 내용"을 정리한 글입니다. 이진트리(Binary Tree)란? 트리란 노드와 간선으로 이루어져 반복적으로 정의되는 자료구조입니다. 이진 트리는 트리의 종류 중 하나로 모든 노드가 두 개의 서브트리를 가지고 있는 트리입니다. 이진 트리의 서브 트리는 공백이 될 수도 있고 하나의 서브트리만 가지거나 두 개 모두 가질 수도 있습니다. 이진트리 구현 노드 클래스 public class Node { int value; Node left; Node right; public Node(int value) { this.value = value; left = null; right = null; } } 먼저 이진트리를 구현하기 전에 이진트리에 필요한 노드를 클래스로 표현해야 합니다. 이 때 노..

이 글은 "온라인 자바 스터디 내용"을 정리한 글입니다. Queue란? 큐는 출구와 입구가 명백히 존재하여 데이터를 담는 방식의 자료구조입니다. 큐의 주요 특징은 First In, First Out (FIFO) 구조를 갖습니다. 배열로 큐 구현 public class Queue { public class Queue { final int MAX_SIZE = 100; int[] arr; int size; public Queue() { arr = new int[MAX_SIZE]; size = 0; } void push(int data){ arr[size++] = data; } int front(){ return arr[0]; } int pop(){ if(size == 0){ return 0; } else{ f..

이 글은 "온라인 자바 스터디 내용"을 정리한 글입니다. Stack이란? 스택은 책을 쌓는 것처럼 데이터를 담을 수 있는 자료구조 입니다. 스택의 가장 큰 특징은 First In Last Out (FILO) 구조를 가지고 있습니다. 배열로 스택 구현 public class Stack { final int MAX_SIZE = 100; int arr[]; int size; public Stack(){ arr = new int[MAX_SIZE]; size = 0; } public void push(int data){ if(size0){ size--; return 1; } return 0; } public int top(){ if(size>0){ return arr[size-1]; } return -1; } p..

이 글은 "온라인 자바 스터디 내용"을 정리한 글입니다. LinkedList란? 링크드 리스트를 노드와 노드를 연결하여 데이터를 담는 방식인 자료구조입니다. 링크드 리스트의 멤버변수로 데이터와 포인터가 존재하여 포인터로 다음 노드를 가리키는 방식입니다. 링크드 리스트와 배열과의 차이점은 명백히 존재합니다. 배열은 한 줄로 나열된 메모리 공간에 데이터를 담는 자료구조로 인덱스로 데이터에 접근 할 수 있습니다. 하지만 배열은 추가, 삭제가 용이하지 않습니다. 반면, 링크드 리스트는 메모리 공간과 상관없이 하나의 노드끼리 연결하다 보니 메모리 사용 측면에서 효율적입니다. 추가, 삭제도 용이하지만 인덱스가 없어 탐색하기에는 적합하지 않습니다. LinkedList 구현 자바에서 인스턴스 전달은 레퍼런스입니다 참조..

이 글은 c++의 stl 중 하나인 multimap 사용법입니다. multimap multimap은 map과 같이 key와 value로 구성된 container입니다. map과는 달리 key의 중복이 허용합니다. multimap은 기본적으로 오름차순 정렬되어 있습니다. multimap을 사용하기 위해서는 #include을 선언해야 합니다. multimap은 binary search tree으로 이행되기 때문에 탐색의 시간 복잡도는 O(log n)입니다. 함수 empty() multimap이 비어있는지 확인하는 함수 if multimap is empty, return 1 else 0 size() mutlimap의 크기를 반환하는 함수 return size_type (unsigned int) i..

C++ STL중 하나인 Set에 대한 설명입니다. Set 중복이 없는 집합을 나타내는 자료구조입니다. 노드 기반 균형 컨테이너로 균형 이진트리로 구성됩니다. Set을 사용하기 위해서는 #include 을 선언해야 합니다. Set 형태로 Compare에는 비교 클래스가 들어갑니다. 비교 클래스의 기본적으로 오름차순 정렬입니다. 함수 insert(element) set에 element을 추가하는 함수 if element is contained, then not insert erase(element) set에서 key 제거하는 함수 if element is contained, then element erase clear() set을 초기화하는 함수 empty() s..

C++ STL중 하나인 unordered_map에 대한 설명입니다. unorderd_map map보다 더 빠른 탐색을 하기 위한 자료구조입니다. unordered_map은 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도는 O(1)입니다. map은 Binary Search Tree로 탐색 시간 복잡도는 O(log n)입니다. unordered_map을 사용하기 위해서는 #include 을 선언해야 합니다. unordered_map은 중복된 데이터를 허용하지 않고 map에 비해 데이터가 많을 시 월등히 좋은 성능을 보입니다. 하지만, key가 유사한 데이터가 많을 시 해시 충돌로 인해 성능이 떨어질 수도 있습니다. 함수 empty( ) 맵이 비어있는지 확인하는 함수 if unor..