힙 힙이란 완전 이진 트리의 일종으로 우선순위 큐를 구현하기 위한 자료구조입니다. 여러 개의 값들 중 최댓값이나 최솟값을 빠르게 찾아내는데 사용됩니다. 이진 트리는 그림과 같이 트리 층에서 모든 노드가 최대 2개의 자식 노드를 가질 수 있는 구조를 말합니다. 이진트리는 왼쪽 자식과 오른쪽 자식을 구분한다는 특징이 있습니다. 우선순위 큐 우선순위 큐는 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조를 말합니다. 우선순위 큐는 단순히 리스트를 이용하여 구현할 수도 있고 힙을 이용하여 구현할 수도 있습니다. 우선순위 큐를 단순히 리스트를 이용하여 구현하면 삽입하는 시간 복잡도는 O(1)이고 삭제할 때 시간 복잡도는 가장 우선순위가 높은 데이터를 찾기 위해 걸리는 시간이 포함되어 선형적인 탐색 시간이 소요..

이번에는 스택과 큐에 대해 알아보도록 하겠습니다. 스택/큐 스택과 큐는 메모리 안에 데이터들을 효율적으로 관리하게 도와주는 처리 방식입니다. 스택 스택은 한국말로 쌓아 올리다라는 말로 스택이라는 자료 구조 안에 데이터를 쌓아올리는 방식입니다. LIFO(Last In First Out)방식으로 처음 들어온 데이터가 맨 마지막에 나가는 구조입니다. 대표적으로 스택을 구현하는 방법은 정적인 1차원 배열로 하는 방식과 동적인 리스트를 이용한 배열이 있습니다. 정적인 1차원 배열로 구현하면 구현하기는 쉬우나 input size를 미리 알아야한다는 단점이 존재하고 동적인 리스트를 이용한 배열로 구현하면 정적인 1차원 배열에 비해 구현하기 어렵지만 input size에 제한이 없다는 장점이 있습니다. 스택 주요 기능..

Hash hash란 단방향 암호화 기법으로 hash 함수를 이용하여 고정된 길이의 암호화된 문자열로 바꾸는 것으로 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있어 빠른 속도로 문제를 처리할 수 있습니다. 예를 들어 어떤 한 가게에서 손님이 물건을 사러 왔을 때 물건의 가격이 적혀져있는 장부를 찾아서 가격을 봐야한다고 가정할 때, 만약 장부가 정렬되어 있지 않다면 O(n)만큼의 시간, 정렬되어 있다면 O(log(n))만큼의 시간이 소요될 것 입니다. 이때 필요한 것은 가격을 외우고 있는 사람이 옆에 있는 것인데 hash 함수가 이 역할을 합니다. hash함수(hash 알고리즘) 정의 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수 입력으로 key를 받아 0부터 배열의 크기-1 사이의 값을 ..