Official-Dev. blog

레드-블랙 트리(Red-Black Tree)를 왜 사용할까? 레드 블랙 트리(Red-Black Tree)는 어떤 목적을 위해서 사용할까? 알아보자. 먼저 자바의 TreeSet과 TreeMap은 레드-블랙 트리를 베이스로 한 구현을 사용한다. 우리가 트리에 저장하는 절차를 살펴보자. 트리 일반적인 트리 구조에서는 삽입할 데이터 n이 있을 때 부모 노드부터 탐색하면서 삽입한 데이터보다 n이 해당 노드보다 작으면 왼쪽 노드에, 해당 노드보다 크면 오른쪽 노드에 저장한다. 그럼 데이터 1, 2, 4, 8이 저장되면 어떻게 될까? 편향 이진 트리가 된다. 배열로 표현하면 공간도 많이 소모될 뿐 아니라 탐색하는데 시간 복잡도 O(n)이 소모된다. 이러한 현상을 막으려면 중간중간에 재배열을 해서 위와 같이 시간복잡도..

Top-down / Bottom-up DP(Dynamic Programming) 방식은 크게 두 가지로 나뉜다. Top-down 방식과 Bottom-up 방식이다. 두 방법 모두 큰 문제를 여러 개의 부분 문제들로 나누어 푸는 방식인데 아래의 차이가 있다. - Top-down 방식은 가장 큰 문제를 방문한 후 작은 문제를 호출하여 답을 찾는 방식이다. - Bottom-up 방식은 가장 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식이다. 일반적으로 Top-down은 재귀 호출을 Bottom-up은 반복문을 이용하여 구현한다. 피보나치 문제의 구현하는 예시를 살펴보자. Top-down 아래는 Top-down 방식의 예시이다. int fibonacci(int n) { if (n == 0) retu..

해시 충돌(Hash Collision) 해시 자료구조에서는 hashCode로 먼저 비교를 하고, 결과가 같다면 equals로 추가로 비교한다. 관련하여는 자바에서 equals와 hashCode의 관계를 다루는 이전 포스팅 (https://jaehoney.tistory.com/168)을 참고하자. 요약하자면, 해시 알고리즘에서 낮은 확률로 다른 Instance이지만 같은 HashCode를 가질 수 있다. 우리가 아는 해시 테이블의 구조는 아래와 같이 생겼다. 그렇다면, 만약 여기서 새로운 Instance가 추가 되었는데, 해시(Hash)를 적용하니 HashCode가 01이 나왔다! 그러면 기존의 01번 버킷에 데이터를 덮어쓰면 될까? 당연히 안된다. 해당 포스팅에서는 이런 경우에 새로운 데이터는 어디에 저..

정규식 정규식(Regular expressions, Regex)는 문자열에서 문자열을 검색, 치환을 위한 용도로 사용합니다. 예를 들어, 어떤 문자열이 "name: {text} email: {text} address: {text} phone: {number}" 구조인지 확인해야 한다고 가정합니다. 심지어 name은 알파벳이어야 하고, email에서는 @와 .을 허용하고, phone은 숫자여야 하는 등을 구현하려면.. 구현하는 것도 일이고 알아보기도 힘들겁니다. 정규식을 사용하면 이를 간결한 코드로 해결할 수 있을 뿐 아니라, 정규식을 사용하면 생각보다 다양한 것을 할 수 있습니다. 예시 abc 간단한 문자열을 정규표현식으로 사용하면 해당 문자열들을 선택할 수 있습니다. abcaabcaaabc a.c '...

O(log n), O(n log n) 사용을 왜하는 걸까? Google, Facebook의 경우 특정 테이블은 레코드가 몇십억, 몇백억 개가 있고, 테라 바이트, 페타 바이트 단위 이상이라고 합니다. 인덱스를 태우지 않고, 선형탐색으로 했을 때 레코드가 500만개만 있어도 요청 하나를 200초 안에도 처리하지 못합니다. O(n) 알고리즘을 사용했을 때 1000만번 계산해야 할 때, O(log n) 알고리즘을 사용할 때 수십 번만 계산해도 처리가 가능합니다. 그 차이는 데이터가 커질수록 기하급수적으로 커지겠죠. 그래서 대규모 서비스를, 아니 중규모 이상 서비스를 고려한다면 O(n) 알고리즘을 O(log n) 알고리즘을 사용하는 것이 중요합니다. 이런 이유로, Basic하게 배운 선형 탐색들을 사용하기 보다..