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

정의 여기서는 일단, 컴퓨터 공학의 알고리즘 문제 해결에 관련한 백트레킹의 개념만 다룹니다. 백트래킹(backtracking)은 한정 조건을 가진 문제를 풀려는 전략이다. 백트래킹은 기본적으로 완전탐색을 하는것을 기반으로 합니다. 즉, 가능한 모든 경우를 고려하는것이 첫번째이다. 그리고 각각의 경우의 수를 만족하기 위한 한정적 조건들을 존재합니다. 가능성이 있는 후보를 점진적으로 구축하고 후보가 특정 목표까지 완료될 수 없다고 판단하는 즉시 후보를 포기합니다("backtracking") 이때 후보군을 포기할 때 솔루션에 영향을 주는 부분을 변경하였다면, 그것을 반드시 원복 시켜주어야 한다. 이것은 백트래킹뿐 아니라 완전탐색에서도 동일하게 원복시켜주어야 합니다. https://www.acmicpc.net/..

정의 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다. 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다. kotlin의 collections는 java의 collections 라이브러리를 그대로 사용한다. stack 역시 java.util.stack 패키지에서 가..

정의 브루트 포스(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)'이라고 부른다. 키 값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다. 각 노드의 자식노..