갑갑이의 개발세상

트라이(Trie)란? 트라이는 문자열을 효율적으로 검색하기 위해 고안된 Search Tree의 일종입니다. 어떠한 알고리즘을 이용하여 정수나 실수 등과 같은 기본 자료형의 변수를 비교할 때에는 각 자료마다 동일한 시간이 걸릴 것이지만, 문자열의 경우 각각의 문자열마다 길이가 다르기 때문에 동일한 알고리즘으로 비교하더라도 같은 시간이 걸린다고 말할 수 없습니다. 최악의 경우 문자열의 길이만큼의 시간이 더 걸리게 될 것입니다. BST를 이용한 검색 (1) 정수 자료형의 경우 한 번의 검색마다 트리의 깊이가 1씩 깊어집니다. 트리의 깊이가 1씩 깊어질 때마다 비교해야 할 자료형은 절반씩 줄어들기 때문에 총 검색의 시간복잡도는 O(logN) 일 것입니다. (2) 문자열의 경우 한 번 검색마다 트리의 깊이가 1씩..

그래프에 정보를 저장했으면, 정보를 사용하기 위해서는 그래프에 어떤 정보가 어떻게 저장되어 있는지 파악해야 할 것이다. 그래프를 탐색하면 그래프를 탐색하는 과정에서 간선이 어떠한 방식으로 연결되어있는지, 탐색 순서는 어떻게 되었는지 등을 통해서 그래프의 전체적인 구조를 파악할 수 있다. 즉, 그래프 탐색의 목적은 임의의 정점에서 시작하여 연결되어있는 모든 정점을 한 번씩 방문하면서 그래프의 구조를 파악하는 것에 있다. 그렇다면 그래프는 어떠한 방법으로 탐색할 수 있을까? 그래프를 탐색하는 방법은 대표적으로 DFS와 BFS의 두 가지가 있다. 1. 깊이 우선 탐색(Depth-First Search, DFS) DFS는 임의의 정점에서 시작하여 방문할 수 있는 정점 중 하나를 방문하고, 방문한 정점에서 방문할..

그래프(Graph)란? 그래프란 사물이나 개념 간의 연결 관계를 표현해주는 자료구조의 일종이다. 예를 들면 SNS에서 친구와 친구 사이의 관계라던지 도로의 교통망, 웹사이트 간의 링크 등과 같이 어떤 요소와 요소간의 관계를 나타낼 때 주로 사용할 수 있다. 그래프는 어디에 활용할 수 있을까? 철도, 도로 등 교통망 분석: 어떤 교통망을 이용해야 최소 비용/최단 거리/최소 시간 내에 이동할 수 있는가? SNS 분석: 친구 관계 분석 및 친밀도 분석 인터넷 망 분석: 어떤 라우터로 가야 최대한 빨리, 최소 비용, 최소 전송 용량으로 전송할 수 있는가? 한 붓 그리기: 그래프 탐색을 통해 단순 사이클을 생각해보면 한 붓 그리기 문제를 해결할 수 있다. 이 외에도 현실세계의 다양한 모델에 그래프 이론을 활용하면..

HashMap은 Map의 인터페이스를 구현한 대표적인 Map 컬렉션의 일종으로, 당연히 Map을 상속받았기 때문에 키(Key)와 값(Value)로 구성된다는 Map의 구조를 그대로 따르고있다. HashMap 선언 아래 예시와 같은 경우 key값의 형식으로 String을, value값의 형식으로는 Integer값을 사용함을 의미한다. // HashMap hm1 = new HashMap(); HashMap hm2 = new HashMap(hm1);// hm1과 동일한 값을 가진 HashMap 생성 HashMap hm3 = new HashMap(10);// 초기 용량(capacity) 지정 HashMap hm4 = new HashMap(){{ put("apple", 1); }};..

비트마스크에 대해서 본격적으로 알아보기 전, 먼저 비트연산에 대해서 알아보도록 하자 비트 연산이란? 비트 연산이란 한 개 또는 두 개의 이진수에 대해서 비트 단위로 수행하는 연산을 말한다. 비트 연산의 종류로는 AND, OR, NOT, XOR, 쉬프트 연산이 있다. AND(&) 두 이진수의 각 자릿수를 비교해 두 값이 모두 1일때만 1을, 나머지의 경우에는 0을 계산한다. 0111 & 1101 = 0101 OR(|) 두 이진수의 각 자릿수를 비교해 두 값이 모두 0일때만 0을, 나머지의 경우에는 1을 계산한다. 0111 | 1101 = 1111 NOT(~) 이진수의 각 자릿수의 값을 반대로 바꾸는 연산이다. 0일 경우 1로, 1일 경우 0으로 바꿔준다. ~0111 = 1000 XOR(^) 두 이진수의 각..

힙(Heap)이란? 힙은 완전 이진트리의 일종으로, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 자료구조이다. 최댓값 및 최솟값에서 알 수 있겠지만, 힙의 종류로는 최대 힙과 최소 힙이 있다. 최대 힙 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리이다. 루트값이 가장 큰 값(최댓값)을 갖는다. 최소 힙 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리이다. 루트값이 가장 작은 값(최솟값)을 갖는다. 우선순위 큐란? 큐(Queue)라고 되어 있어서 일반적인 큐와 동일하게 FIFO(First-In-First-Out)방식의 자료구조를 생각할 수도 있겠지만, 우선순위 큐는 큐와는 전혀 다른 자료구조이다. 우선순위라는 말 그대로, 우선순위 큐에 있는 ..