개발하는 리프터 꽃게맨입니다.

디자인 패턴이란? 처음에 프로그래밍에 입문했을 때 이런 말을 들었습니다. '좋은 코딩 습관을 들여라' 여기서 좋은 코딩 습관이란 사람마다 생각이 다 다르겠지만, 저는 가독성이 좋은 코드를 작성하는 것이 좋은 코딩 습관이라고 생각합니다. 버그나 오류가 많은 것도 나쁜 코드겠지만, 성능이 좋다고 하더라도 나만 알아보거나 나조차도 못 알아보는 코드는 아무래도 좋은 코드가 아니겠죠. 그러나 작은 규모의 프로그램을 작성해도 설계를 할 때 있어서 실수나 문제를 피하기는 어렵습니다. 프로그램 설계에 있어 자주 발생하는 문제를 피하고, 좋은 코드를 지향하기 위해서 만들어진 설계 패턴이 디자인 패턴입니다. 컴퓨터 과학은 수십년간 발전을 이뤄왔기 때문에 내가 겪은 문제를 다른 사람이 겪지 않았을 확률은 매우 낮습니다. 그..

좋은 해쉬 함수가 뭔데? 자료구조에서의 해쉬 함수는 키 값을 이용해 해쉬 주소를 얻어낼 수 있는 함수를 뜻하며 이는 엄밀하게 정해져있는 것이 아니라, 프로그래머가 상황에 따라 재량껏 정의하여 사용합니다. 여기서 나쁜 해쉬 함수와 좋은 해쉬 함수는 엄연히 다릅니다. 좋은 해쉬함수가 되기위한 조건을 몇 가지 살펴보도록 하죠. 1) 좋은 해쉬 함수의 조건 (1) 해쉬 함수의 값이 해쉬 테이블 전체에 균일하게 분산되어야 한다. 해쉬에서는 키 값이 균일하게 분산되어 있을수록 좋습니다. 키 값이 균일하게 분산되다는 것이 곧 충돌이 적어짐을 뜻하죠. (2) 충돌 발생 빈도가 적어야 한다. (3) 연산이 빨라야 한다. 너무 연산량이 많은 해쉬의 경우에는 데이터 접근 속도가 느리기 때문에 좋은 해쉬함수라고 할 수 없습니..

선형조사법의 한계 closed hashing 인 선형조사법의 한계는 데이터 클러스터 현상입니다. 단순하게 말하면, 데이터가 한 곳에 몰려서 군집을 이룬다는 것이죠. 선형 조사법은 충돌 발생시 선형으로 빈공간을 탐색하기 때문에, 충돌이 발생한 지역 위주로 데이터가 몰릴 가능성이 높습니다. 이차조사법 및 이중해쉬는 closed hasing, open addressing 해쉬임과 동시에, 선형조사법의 클러스터 현상을 보완하는 해쉬 구조입니다. 이차조사법 1) 개요 이차조사법이 상당히 간단합니다. 그냥 선형조사법에 양념만 쳐주면 되죠. 이것이 선형조사법의 삽입 코드입니다. 충돌시 hashAddr +1, hashAddr +2, HashAddr +3... 이런 식으로 +1 씩 더해간다는 것을 알 수 있습니다. 이제..

https://powerclabman.tistory.com/58 (이전 글) 충돌 이슈 1) 개요 해쉬에서 충돌은 불가피합니다. 어떤 키값이 들어올지 예측하지 못하기 때문에 그리고 쓸데없는 메모리 공간을 차지하는 것을 막이 위해 해쉬 테이블은 제한된 공간을 가지고 있고 해쉬 주소는 해쉬 함수를 통해 만들어지는데 다른 키 값에 대해서 값은 해쉬 주소가 나오는 건 어쩔 수 없습니다. 해쉬 테이블의 크기가 M개가 존재한다고 했을때, 들어올 수 있는 데이터의 수는 M 이상 일 수 있기 때문에 충돌이 발생할 수 밖에 없는 것이죠. 사이즈 100의 해쉬 테이블에 30개의 데이터만 넣어도 돌 확률이 99%에 도달합니다. 그래서 기본적으로 충돌이 발생한다고 생각하고, 어떻게 충돌에 대처할 것 인가를 생각하는 것이 중요..

1. 해쉬란? 1) 개요 탐색에 있어서 매우 강력한 자료구조입니다. 앞서 살펴봤던 배열, 연결리스트의 경우 삽입/삭제/탐색 에 있어서 O(N) 트리 기반 자료구조의 경우 삽입/삭제/탐색 에 있어서 O(log2 N) 의 시간 복잡도가 소요됩니다. 하지만 해쉬의 경우 O(1) 라는 매우 빠른 시간에 삽입/삭제/탐색을 수행할 수 있죠. 그런데, 어떻게 이런 일이 가능할까요? 해쉬는 키를 해쉬함수를 통해 유의미한 정수로 바꿉니다. 그리고 해쉬테이블에 데이터를 저장하죠. 이런 일련의 과정을 해싱이라고 합니다. 잘 이해가 안가신다면 이렇게 생각해보세요. 사이즈 100의 배열이 있고, 우리가 접근하고 싶은 데이터의 주소를 알고있다면 바로 접근이 가능하잖아요? 이것을 기본 개념으로 출발합니다. key값을 해쉬테이블을 ..

레드블랙 트리 기본 1) 개요 레드블랙 트리(이하 RB트리)는 AVL트리와 같은 '자가 균형 이진 탐색 트리'입니다. 삽입 및 삭제 시 스스로 균형을 유지하여 탐색에 있어 평균 O(log2 N) 만에 수행할 수 있도록 보장해 주죠. 멀쩡한 AVL 트리가 있는데 레드블랙 트리는 왜 등장했을까요? AVL 트리는 매우 엄격한 균형을 유지하는 트리이며, 오버헤드가 큽니다. 특히 높이를 계산하는 과정은 재귀를 통해 일어나기 때문에 자료가 많으면 많을수록 삽입/삭제 시 소모되는 계산 오버헤드는 커지게 되죠. (높이 계산을 매번 하지 않고 노드 자체에 저장하는 최적화 방법이 존재합니다.) 그러나 RB트리는 덜 엄격한 균형을 이룹니다. 심지어 balance factor를 균형의 규칙으로 사용하지도 않기에 시간적, 공간..

1. 이진 탐색 트리의 문제점 이진 탐색 트리는 매우 효율적인 자료구조입니다. '균형 트리'라는 전제하에 삽입, 삭제, 탐색이 모두 O(log2 N)만을 소모합니다. 그런데, 이진 탐색 트리는 '균형' 을 보장하지 않습니다. 만약 삽입을 하다 이런 트리 구조가 나왔다면, 시간 복잡도가 O(N) 에 가까워지는 것이죠. 따라서 이진 탐색 트리에서는 균형을 유지하는 것이 매우 중요하여, 여러가지 스스로 균형을 잡은 자가 균형 트리에 대해서 알아보도록 하겠습니다. 2. AVL 트리 1) 개요 AVL 트리는 이진 탐색 트리에서 한 가지 조건을 더 추가합니다. 왼쪽 서브트리와 오른쪽 서브 트리의 높이 차이가 1 이하 AVL 트리는 항상 균형 트리를 보장되기 때문에 탐색이 O(log2 n) 만에 완료됩니다. 2) B..

[ 목차 ] 1. 개요 1) 개요 리스트, 큐, 스택, 배열과 같은 자료구조를 선형 자료 구조라고 부릅니다. 데이터들을 연속적으로 접근할 수 있는 것이죠. 근데, 예를 들어 가족의 가계도, 회사의 조직도, 컴퓨터의 디렉터리 등에 대한 자료구조를 어떻게 표현하면 좋을까요? 이 경우에 사용하는 것이 트리(tree) 계층적 자료 구조입니다. 트리 구조는 마치 나무를 거꾸로 뒤집을 형태라고 그렇게 부릅니다. 가장 최상단 노드를 루트노드라고 부르며, 루트의 아래로 작은 트리들이 재귀적으로 정의되는 것을 기본 구조로 합니다. 2) 용어 트리는 한 개 이상의 노드로 이루어진 유한 집합입니다. 트리에서 최상위 노드를 루트 노드 한 노드에서 뻗어 나오는 노드들을 자식 노드 그 반대를 부모 노드라고 합니다. 2의 경우 7..

[ 목차 ] 개요 1. 리스트란? 리스트는 자료를 정리하는 방법 중 하나입니다. 항목이 '연속적으로' 저장되어 있는 자료구조의 가장 기본적인 한 형태라고 할 수 있죠. 대부분의 언어에서 기본적으로 제공하는 '배열' 역시 '리스트'의 한 종류 입니다 그리고 '리스트'를 구현하는 방법이 하나 더 있는데, 그것이 연결 리스트입니다. 2. 연결리스트 연결리스트는 노드라는 데이터 단위가 존재하고, 노드 내부에는 데이터가 연결되는 데이터 영역, 그리고 다른 노드를 가리키는 링크 영역이 존재합니다. 저장하고 싶은 데이터를 데이터 영역에 저장하고, 링크 영역에서 링크라는 연결이 다른 노드를 가리킵니다. 이런 방식으로 메모리가 링크라는 줄로 연결된 상태입니다. 이런 링크라는 표현은 다른 여러 가지의 자료구조를 구현하는데..

필요해서 직접 만든 STL 호환 '크기 고정 벡터'입니다. '동적 배열'을 사용하지 않고 굳이 fixed_vector라는 고정길이 벡터를 만든 이유는 기존 '동적 배열'은 매우 뛰어난 자료구조이지만 몇 가지 문제점이 있습니다. 1) 힙 메모리를 사용하기 때문에 스택 메모리에 비해 조금 느리다. 2) 재할당 발생 시 O(n)의 시간복잡도가 소모된다. (초기화시 큰 reserve 를 할당하면 해결 가능) 3) 잦은 재할당 발생시 메모리 파편화 현상이 문제가 될 수 있다. 그렇기 때문에 굳이 동적 배열이 필요하지 않은 경우에는 일반 '배열'을 사용하는 것이 더 유리할 경우가 있습니다. 그냥 배열을 쓰지 않고 fixed_vector를 만든 이유는 필요시 편리한 기능이나 오류 체크 같은 것을 하기 위함이고 최적화..