완전 탐색이란? 완전 탐색이란, 가능한 모든 경우의 수를 탐색하여 답을 구하는 기법을 의미한다. 연산마다 다르지만 C++기준 약 1억번의 연산에 대해 약 1초가 소요된다. 따라서 문제에서 요구하는 연산량이 많지 않고, 제한 시간이 목표 시간 내에 들어온다면 완전 탐색 기법을 사용해 풀이를 시도할 수 있다. 경우에 따라서 완전 탐색 기법을 최적화하여 풀이를 진행한다. (ex. Backtracking!) https://osmopolirt.tistory.com/47 선형 구조를 탐색하는 방법으로는 순차 탐색, 비선형 구조를 탐색하는 방법으로는 아래의 링크에 제시된 DFS, BFS 등이 있다. 백트래킹(Backtracking) 백트래킹(Backtracking)이란? 제약 조건(constraints)을 가진 최적..
이분 탐색이란? 정렬된 배열(or collection)에서 특정한 값의 원소를 찾을 때 사용하는 탐색 방법이다. 최적화 문제의 조건 Condition을 만족시키는 x의 최대 혹은 최소를 찾을 때 많이 사용한다. x의 값에 따라 Condition의 값이 두 구간 (T, T, ... , F, F)로 나뉠 때, T와 F가 바뀌는 경계를 이분 탐색으로 찾는다. O(logN)의 시간 복잡도를 가지기 때문에, 매우 큰 수에 대해 문제가 나오는 경우가 많다. 오버플로우 주의! 탐색 과정 low = 배열의 시작 인덱스, high = 배열의 끝 인덱스로 초기화 한다. mid = (low + high) / 2 Condition(mid)를 확인한 후, 해당 Condition이 바뀌는 지점이 있는 범위로 탐색을 좁힌다. Co..
백트래킹(Backtracking)이란? 제약 조건(constraints)을 가진 최적화 문제, 결정 문제를 푸는 방법 중 하나로 퇴각 검색이라고도 부른다. 완전 탐색(brute force)과 비슷하게 모든 경우의 수를 시도한다. 탐색 과정에서 현재 경로(해, solution)가 조건을 만족하지 못할 것 같다면 배제하고 이전 단계로 돌아간다. 해가 될 가능성이 있는 해를 유망하다(promising)고 한다. non-promising한 해를 제외하는 것이라고도 할 수 있으며, 이를 가지치기(pruning) 라고도 부른다. 일반적인 완전 탐색에 비해 탐색해야 하는 경우의 수가 줄어들게 된다. 일반적으로 DFS를 이용해 구현하며, 탐색 과정에서 제약 조건을 걸어 만약 해당 조건을 만족 시키지 못한다면 이전 No..
BFS(Breadth First Search)란? Tree 또는 graph를 탐색할 때 사용되는 탐색 알고리즘의 일종 임의의 node에서 시작하여 해당되는 분기에서 단계별로, 너비를 우선하여 탐색한다. Breadth First!) 즉, 시작 정점에서 인접한 정점들을 우선적으로 방문하는 방법이다. BFS의 특징 목표 상태까지의 정보(step, distance)를 알지 못하는 uninformed search의 일종이다. 시작 노드에서 가까운 노드를 우선적으로 탐색하므로, 주로 가중치가 없는 그래프에서 두 노드 사이의 최단 경로 또는 임의의 경로를 찾을 때 사용한다. DFS는 보통 재귀적으로 구현했지만, BFS는 주로 FIFO 자료구조인 Queue를 사용한다. Pseudo code Function bfs() ..
DFS(Depth First Search)란? Tree 또는 graph를 탐색할 때 사용되는 탐색 알고리즘의 일종 임의의 Root node에서 시작하여 해당되는 분기에서 가능한 깊게 탐색한다. (Depth First!) DFS의 특징 목표 상태까지의 정보(step, distance)를 알지 못하는 uninformed search의 일종이다. 특정 분기를 모두 탐색했을 때, 해당 노드에서 자식 노드 (다음 방문할 노드)가 없다면 backtrack한다. (부모로 되돌아감) BFS에 비해서 공간 복잡도 측면에서 유리하다. 현재 탐색하는 경로만 우선적으로 기억하면 되기 때문이다. 해가 존재하지 않는 경로에 너무 깊게 들어가는 것을 막기 위해 depth bound, backtracking을 사용하기도 한다. Ps..
아직까지 수학적으로 소수를 계산할 수 있는 효율적인 공식은 존재하지 않는다. 그렇기 때문에 이러한 특성을 이용해 암호화(RSA 등) 알고리즘에 사용되기도 한다. 소수를 구하기 위해서는 간단한 알고리즘과 computational power를 사용한다. 과제로 RSA를 구현하다가 간단하게 정리해보았다! 1. brute force Function isPrime(N) for i
