오늘도 더 나은 코드를 작성하였습니까?

정의 브루트 포스(brute force), 키 전수조사(exhaustive key search) 또는 무차별 대입(無差別代入)은 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다. 흔히 암호학에서 연구되나, 다른 알고리즘 분야에서도 사용되고 있다. 수학 문제를 원시적으로 푸는 방법인 '수 대입 노가다'의 학술적 개념이다. 컴퓨터 공학의 알고리즘 분야 특히, 문제 풀이에 있어서는 컴퓨터 CPU의 빠른 연산속도를 이용해 가능한 모든 경우의 수 및 경로를 탐색하여 해답을 도출해내는 방법이다. 예시 문제) 14500 테트로 미노 문제 분석해 보기 N*M 크기의 2차원 직사각 배열이 주어진다. 아래 5가지 형태를 각각 좌우 대칭 및 회전을 하여 위 숫자 직사각 배열에 1개의 도형을 ..

정의 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다. A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다. 힙에는 두가지 종류가 있으며, 부모노드의 키값이 자식노드의 키 값보다 항상 큰 힙을 '최대 힙(max_heap)', 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙을 '최소 힙(min_heap)'이라고 부른다. 키 값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다. 각 노드의 자식노..

Disjoint Set(서로소 집합) - 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합 DSU(Disjoint Set Union) - 데이터 구조는 여러개의 서로소 집합(겹치지 않도록) 원소(데이터)를 저장하는 자료구조이다. - union–find 또는 merge-find 라고도 부른다. - 두 서로소 집합을 합쳐 하나의 집합으로 만들 수 있다(union) - 2개의 서로 다른 원소가 같은 집합인지 "대표원소를 통해" 확인할 수 있다(find) 구현 예) 총 원소가 0번 원소부터 7번까지 8개의 원소가 있다고 가정하고, 처음에는 자기 자신만을 포함하는 총 8 개의 집합이 있다고 가정해 보자. 배열로 Index는 해당 원소, value는 속한 집합의 "대표원소" 이다. * 대표원소를 결정하는 방..

해시 충돌 hash function이 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황 Chainning (체이닝) hashTable의 각 슬롯이 연결 리스트의 형태로 데이터를 저장하여, 동일한 출력을 값을 가지는 데이터가 들어 오더라도 같은 hash table의Idx에 저장하여 충돌을 해결한다. 새로운 데이터를 넣을때는 각 해당 슬롯의 가장 앞에 삽입한다. 그러면 항상 O(1)의 시간이 걸린다. 하지만, 검색 및 삭제는 해당 슬롯의 충돌되어 삽입된 갯수에 따라 성능이 좌우된다. 이때, hashFunction을 C-Universal Function을 사용하면, 각 슬롯의 평균적인 연결리스트의 길이는 O(1)이라 이미 증명되어 있다. class ChainingHashTable(private va..