기록방

💡 트라이(Trie)는 트리형태로 문자열을 저장해 빠르게 탐색하는 자료구조이다. 일반적인 이진트리의 시간 복잡도는 O(logN) 이지만, 길이가 M인 문자열을 저장하면 O(M*logN)의 시간 복잡도를 갖는 문제가 생긴다.이러한 문제를 해결하기 위해서 Trie는 문자열의 문자 하나씩 노드에 저장한다.문자열 하나를 검색할 때 O(N)의 시간 복잡도를 갖는다.Java에서는 Map 자료구조를 이용해 구현한다.저장된 문자열 : cap, code, kakao, kai 🚀 트라이 자료구조 생성 및 사용검색하고자 하는 문자열을 트라이 클래스에 모두 저장한다.하나의 문자열을 저장할 때, 각 문자를 key로 자식 노드를 value로 트리 형태를 띄는지 확인한다.만약 현재 문자 key가 없다면, 생성해준다.마지막 노드..

데큐 : 스택과 큐가 합쳐진 형태로 앞 뒤 모두 입력과 출력이 가능하다. [ 기능 ] insertFront/Rear : 데큐 앞/뒤 데이터를 넣음 deleteFront/Rear : 데큐 앞/뒤 데이터를 꺼냄 peekFront/Rear : 데큐의 앞/뒤 데이터를 알림(엿봄) indexOf : 데큐에 특정 값이 있는지, 있다면 어느 위치에 있는지 알림 size : 데큐의 데이터 수 확인 clear : 데큐 비우기 isEmpty : 데큐가 비었는지 확인 isFull : 데큐가 가득 찼는지 확인 dump : 데큐의 모든 데이터 확인 [ python ] class Deque: def __init__(self): print('\n-- 데큐 프로그램 --') self.dq = [] self.max = 10 def i..

큐 : 데이터를 일시적으로 저장하기 위해 사용하는 자료구조. 선입선출(FIFO, First In First Out) [ 기능 ] enque : 큐에 데이터를 넣음 deque : 큐의 맨 앞 데이터를 꺼냄 peek(front) : 큐의 맨 앞 데이터를 알림(엿봄) indexOf : 큐에 특정 값이 있는지, 있다면 어느 위치에 있는지 알림 size : 큐의 데이터 수 확인 clear : 큐 비우기 isEmpty : 큐가 비었는지 확인 isFull : 큐가 가득 찼는지 확인 dump : 큐의 모든 데이터 확인 [ python ] class Queue: def __init__(self): print('\n-- 큐 프로그램 --') self.st = [] self.max = 1000 def enque(self, ..

스택 : 데이터를 일시적으로 저장하기 위해 사용하는 자료구조. 후입선출(LIFO, Last In First Out) [ 기능 ] push : 스택에 데이터를 넣음 pop : 스택의 맨 위 데이터를 꺼냄 peek(top) : 스택의 맨 위 데이터를 알림(엿봄) indexOf : 스택에 특정 값이 있는지, 있다면 어느 위치에 있는지 알림 clear : 스택 비우기 size : 스택의 데이터 수를 확인 isEmpty : 스택이 비었는지 확인 isFull : 스택이 가득 찼는지 확인 dump : 스택의 모든 데이터 확인 [ python ] class Stack: def __init__(self): print('\n-- 스택 프로그램 --') self.st = [] self.max = 1000 def push(s..