조금씩 꾸준히 완성을 향해

해시 테이블 (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..

그리디 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 그리디 해법은 그 정당성 분석이 중요 => 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 하지만 코딩테스트에서 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다. 각 부분에서의 선택이 다른 부분에게 영향을 주지 않는다 => 각 부분에서의 최적해결이 최종 해결방법이다. 예시 문제 분석 ▶ 문제 설명 당신은 음식점의 계산을 도와주는 점원..

복잡도(Complexity) 시간복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 => 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을 수록 좋은 알고리즘 빅오 표기법(Big-O Notation) 가장 빠르게 증가하는 항만을 고려하는 표기법 (함수의 상한만을 나타냄) ▶ 표현 방법 n이 증가할 때 가장 빨리 증가하는 항(최고차 항)만 남기고 다른 항은 모두 생략 가장 빨리 증가하는 항에 곱해진 상수 역시 생략 남은 항을 O() 안에 넣어 표기 알고리즘 설계 Tip ▶ 일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우 C언어를 기준으로 통상 1~3초 가량 시..

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) 세 가지 정보만으로 값이 저장된 곳의 주소를 계산할 수 있다 => 메모리 주소가 주어지면..

Time Complexity 수행시간이란 특정 입력에 대해 수행되는 알고리즘의 기본연산(primitive operation)의 횟수를 말한다. (가상컴퓨터에서 가상언어로 작성된 가상코드를 실행한다고 가정 알고리즘의 수행시간 = 최악의 경우의 입력(worst-case input)에 대한 기본연산의 수행 횟수 입력의 크기 n에 대한 함수 T(n)으로 표기 -> 어떠한 입력에 대해서도 T(n) 시간 이내에 종료됨을 보장 ▶ example #input : n개의 정수가 담긴 배열 A #output : A의 수 중에서 최대값 def func(A, n): max = 0 # 1번(할당) for i in A: if i > max: # n-1번(크기를 확인하는 최악의 경우) max = i # n-1번(할당을 하는 최악의..