콘요맘떼 개발일지

집합 (Set) 집합은 중복 없이 값들을 저장하기 위해 사용된다. (중복이 존재하지 않는다는 것이 집합의 가장 큰 특징이다.) 순서가 존재하지 않는 Non-Linear 자료구조이며 중복을 허용하지 않기 때문에 똑같은 값을 삽입하면 그 중 하나만이 저장된다. 집합은 빠른 탐색에 뛰어난 성능을 보이기 때문에 특정 값이 집합 내에 존재하는지 곧바로 확인할 수 있다. 집합은 삽입할 데이터의 해시값을 구한 후 그에 해당하는 버킷에 데이터를 저장한다. 그를 통해 동일한 값에 대한 중복을 제거할 수 있으며 특정 값의 보유 여부를 빠르게 탐색할 수 있다. ※ Javascript에서의 집합 자바스크립트에서는 집합이 기본적으로 구현되어 있다. 자바스크립트의 집합인 Set 객체는 원시 값과 객체 참조를 모두 저장할 수 있으..

리스트 (List) 리스트는 가장 대표적인 자료구조 중 하나로 Array, List, Stack, Queue 등과 함께 데이터에 순서가 존재하는 선형 자료구조(Linear Data Structure)에 속한다. (참고로 비선형 자료구조에는 Tree, Graph, Set 등이 존재한다.) 리스트의 구현 방법 리스트를 구현하는 방법에는 크게 두 가지 방법이 존재한다. 논리적으로만 데이터를 연속하게 저장하는 방법이 있고 두 번째는 물리적으로도 데이터를 연속하게 저장하는 방법이다. 1. ArrayList ArrayList는 데이터를 논리적 순서에 따라 물리적 메모리에 연속해서 저장한다. 메모리 중간에 빈 공간이 존재하면 안되기 때문에 데이터를 중간에 삽입하거나 삭제할 경우 데이터 위치를 재조정하는 작업이 필요하..

맵 (Map) 맵은 데이터가 Key와 Value의 쌍으로 이루어진 자료구조를 의미한다. key를 통해 value에 접근할 수 있으며 key와 value를 연결하는 행위를 맵핑(mapping)이라고 표현한다. 맵의 특징 (1) (일반적으로) key는 중복되어서는 안 된다. (대신 value는 중복되어도 무관한다.) (2) 데이터의 순서는 보장되지 않으며 인덱스도 존재하지 않는다. (애초에 Map에서 순서는 전혀 중요한 개념이 아니다.) (3) 맵은 검색 연산에서 뛰어난 성능을 보인다. 맵의 종류와 특징 1. HashMap 해싱을 통해서 key와 value를 저장한다. 데이터의 위치는 해싱 결과에 의해 결정되기 때문에 순서는 보장되지 않는다. 하나의 key에 대해 하나의 value만 존재할 수 있다. 만약 ..

덱은 스택과 큐에 대한 기본적인 이해가 있는 것이 좋다. 혹시 스택과 큐의 개념을 잘 모른다면 관련 내용을 먼저 확인하고 오길 바란다. (스택, 큐) 덱 (Dequeue, Double-ended Queue) 덱은 스택과 큐를 합친 것이라고 보면 된다. 덱은 양쪽 끝에서 데이터를 넣고 뺄 수 있다. (큐에서 가장 앞에 위치한 데이터를 뽑아내는 연산과 표현이 같지만 동일한 개념이 아니므로 주의해야 한다.) 실제로 입출력 모두 양쪽에서 가능하도록 설정하는 덱은 별로 존재하지 않으며 기존 스택 혹은 큐에서 입력 혹은 출력 중 하나만 양쪽에서 이루어질 수 있도록 확장한 개념으로 많이 사용한다. (1) 스크롤 (scroll) : 출력은 양방향이 가능하지만 입력은 한쪽 끝만 가능한 덱 (2) 쉘프 (shelf) : ..

큐 (Queue) 큐는 FIFO(First-In First-Out)를 따르는 자료구조이다. 즉, 가장 먼저 넣은 아이템이 가장 먼저 제거되며 입구와 출구가 다른 자료구조이다. 일상적인 개념에서 '줄서기'에 빗대어 많이 표현된다. 큐의 연산 (1) enqueue( ) : 큐의 마지막에 새로운 아이템을 추가한다. (2) dequeue( ) : 큐의 첫 번째 항목을 제거한다. (3) front( ) : 큐의 첫 번째 항목을 알려준다. (가장 먼저 출력될 아이템) (4) rear( ) : 큐의 마지막 항목을 알려준다. (가장 최근에 추가된 아이템) 큐의 성능 - 탐색 : 큐에서 탐색은 모든 아이템을 하나하나 훑어봐야 되기 때문에 O(n)시간이 필요하다. - 삽입 : 상수 시간에 가능하다. - 제거 : 상수 시간..

스택 (Stack) 스택은 LIFO(Last-In First-Out)를 따르는 자료구조이다. 즉, 가장 최근에 넣은 아이템이 가장 먼저 제거되며 입구와 출구가 한 쪽만 열려있다고 생각하면 된다. 스택의 연산 (1) push( ) : 스택에 새로운 아이템을 추가한다. (가장 윗부분) (2) pop( ) : 스택의 가장 위에 있는 항목을 제거하고 반환한다. (3) isEmpty( ) : 스택이 텅 비어있는지 여부를 알려준다. (4) peek( ) 혹은 top( ) : 스택의 가장 위에 있는 항목을 보여준다. 스택의 성능 - 탐색 : 스택에서 탐색은 모든 아이템을 하나하나 훑어봐야 되기 때문에 O(n)시간이 필요하다. - 삽입 : 마지막에 데이터를 하나 추가해주면 되기 때문에 상수 시간에 가능하다. - 제거 ..