조금씩 꾸준히 완성을 향해

해시 테이블 (Hash Table) Hash Table? 키(Key)에 데이터(Value)를 저장하는 데이터 구조 Key를 통해 데이터를 바로 받아올 수 있음 → 속도가 획기적으로 빨라짐 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예 - Key를 가지고 바로 데이터(Value)를 꺼냄 보통 배열로 미리 Hash Table 사이즈만큼 생성 후 사용(공간과 탐색 시간을 맞바꾸는 기법) 파이썬에서는 해쉬를 별도로 구현할 필요 없음 - 딕셔너리 타입을 사용하면 되기 때문 해시 함수란? 임의의 길이를 갖는 메세지를 입력받아 고정된 길이의 해시값을 출력하는 함수 Python Hash (Dictionary) 의 활용 ▶ 딕셔너리 삽입 hash = dict() hash = {} #딕셔너리 생성 hash..

우선선위 큐 (Priority Queue) 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용 예) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우 ▶ 우선순위 큐를 구현하는 방법은 다양하다. 1) 단순히 리스트를 이용하여 구현 가능 2) 힙(heap)을 이용하여 구현 가능 ▶ 데이터의 개수가 N개일 때, 구현 방식에 따라서 시간 복잡도 비교 힙(Heap)의 특징 완전 이진 이트 자료구조의 일종 힙에서는 항상 루트 노트(rooot node)를 제거 최소힙(min heap) : 루트 노트가 가장 작은 값을 가지는 힙 최대힙(max heap) : 루트 노트가 가장 큰 값을 가지는 힙 ▶ 완전 이진 트리 (Com..

문제 정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여섯 가지이다. push X: 정수 X를 큐에 넣는 연산이다. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 큐에 들어있는 정수의 개수를 출력한다. empty: 큐가 비어있으면 1, 아니면 0을 출력한다. front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. ..

문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열..

문제 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자! 입력 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다. 정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할..

문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보..

Queue FIFO(First In First Out, 선착순) : 삽입할 땐 가장 최근에 저장된 값 다음에 저장되고(stack과 동일) 삭제할 땐 가장 오래전에 저장된 된 값부터 나간다. enqueue(val) : value를 큐의 오른쪽(rear)에 삽입 (push와 같음) dequeue(): 가장 왼쪽에 저장된 값을 삭제 후 리턴 dequeue를 상수시간에 실행하기 위해선, dequeue가 될 값의 인덱스(index)를 저장하고 관리한다 → dequeue가 되면, 인덱스 값이 하나 증가하여 다음 dequeue 될 예정인 값의 인덱스를 가리키도록 관리! ▶ Queue class 생성 class Queue: def __init__(self): # 생성자 함수 self.items = [] # 데이터 저장..

Stack LIFO(Last In First Out) : 값을 저장할 때는 가장 최근에 저장된 값 다음에 저장되며, 값이 나갈 때는 가장 최근에 저장된 값이 먼저 나간다 데이터는 리스트에 저장 (append, pop 함수가 제공되므로) 연산은 push, pop, top, isEmpty, size(len) 등 5 가지 연산 제공 ▶ Stack class 생성 class Stack: def __init__(self): # 생성자 함수 self.items = [] # 데이터 저장을 위한 리스트 준비 def push(self, val): #삽입 self.items.append(val) def pop(self): #삭제 try: # pop할 아이템이 있으면 return self.items.pop() # pop 수..

Array (배열) & List (리스트) 데이터를 연속적인 메모리 공간에 저장하고, 저장된 곳의 주소(address, reference)를 통해 매우 빠른 시간에 접근할 수 있는 가장 기본적인 순차적인(sequential) 자료구조 C 언어의 배열 ▶ 배열의 저장 및 메모리 할당 int A[4] = {2, 4, 0, 5} // 정수 4개를 저장할 수 있도록 연속적인 메모리 공간 할당 A[2]의 주소 = A[0]의 시작 주소 + 2 * 4 bytes (index=2, sizeof(int)=4) //108번째 배열의 시작 주소, 저장된 값의 종류(바이트 개수), 몇 번째에 저장되어 있는지를 나타내는 인덱스(index) 세 가지 정보만으로 값이 저장된 곳의 주소를 계산할 수 있다 => 메모리 주소가 주어지면..