삼성 소프트웨어 멤버십에 투고한 글. 본 글에는 차마 너무 저렴한 어휘라서 담지 못했지만 정말 날먹이 가능한(..) 기법인듯 하다. 뭔가 자료가 있는 것 같으면서도 PS에 관련된 자료는 전무한 거 같아서 (특히 한글은) 작성했다. 나도 뭐 어디서 검색해서 알게된 것은 아니고 NYPC 2019 예선 풀다가 찾은 풀이였는데 그 이후로도 종종 써먹어서 그냥 글로 작성했다. 본격적으로 시작 서론 본 글에서는 트라이를 압축하여 트라이의 깊이를 $O(\sqrt (\sum \vert S \vert))$로 만드는 기법에 대해 설명하고자 합니다. 해당 방법은 트라이와 라빈-카프 알고리즘에 대한 선행 개념이 필요합니다. 해당 개념을 모르는 사람들을 위해 아래에 간략하게 설명하겠습니다. 트라이는 접두사 트리로, 어떤 문자열..
개요 스택 역시 큐와 마찬가지로 매우 기본적인 자료구조 중 하나다. 큐가 FIFO 자료구조인 반면 스택은 LIFO(Last In First Out)자료구조이다. 영어 그대로 늦게 들어온 원소가 먼저 나간다. 스택의 기본적인 연산은 push와 pop이며 push는 스택에 새로운 원소를 집어넣는 연산이고 pop은 스택의 제일 위에 있는 원소(앞으로 이를 top이라 지칭할 것)를 제거하는 연산이다. 아래 사진은 이를 그림으로 설명한 것이다. 왼쪽부터 각 연산을 하면서 스택에 어떤 변화가 있는 지 나타냈고, top에 해당하는 원소를 빨갛게 칠해놨다. 스택의 구현 역시 리스트로 할 수 있고, 큐와는 다르게 원소의 입구와 출구가 같으므로 top에 대한 포인터 하나만 있으면 된다. 큐와 마찬가지로 push와 pop연..
개요 큐는 매우 기본적인 자료구조 중의 하나이다. FIFO (First In First Out) 자료구조인데 먼저 들어온 원소가 먼저 나간다는 것을 의미한다. 큐의 기본적인 연산은 push와 pop이며 push는 큐에 새로운 원소를 집어넣는 연산이고 pop은 큐의 제일 앞에 있는 원소(앞으로 이를 front라 지칭할 것)를 제거하는 연산이다. 아래 사진은 이를 그림으로 설명한 것이다. 보면 알겠지만 pop연산을 하기 전까지는 front는 절대 변하지 않는다. 또한 pop연산에서 사라지는 원소는 큐에 처음 들어간 순서와 일치한다. 큐의 구현은 리스트로 할 수 있고, 입구와 출구가 다르기 때문에 front 포인터와 back 포인터 두 개가 필요하다. 리스트에서 원소의 삽입과 삭제가 $O(1)$이었던 것처럼,..
개요 연결 리스트는 데이터들을 포인터로 연결시켜 관리하는 자료구조이다. 데이터는 노드에 저장되는데, 각 노드에는 데이터에 대한 정보와 다음 위치에 대한 정보, 그리고 리스트의 종류에 따라 이전 위치에 대한 정보까지 저장된다. 연결 리스트는 여러가지 종류가 있지만 흔히 볼 수 있는 건 다음과 같은 3가지이다.각 노드의 다른 노드를 가리키는 포인터가 다음 노드 하나만을 가리키는 단일 연결 리스트(Singly Linked List)이전 노드와 다음 노드 2개를 가리키는 이중 연결 리스트(Doubly Linked List)head와 tail을 연결시켜버린 원형 연결 리스트(Circular Linked List) 이 중에서 나는 이중 연결 리스트를 기준으로 설명할 것이다. (아래 설명을 잘 이해한다면 나머지 두 ..