소수 (Prime Number)소수란? 1보다 큰 자연수 중에서, 1과 자기 자신으로만 나누어 떨어지는 숫자를 말한다. 즉, 약수가 2개인 자연수이다. 소수는 2, 3, 5, 7, 11, … 등으로 무한히 많으며, 규칙성이 아직 증명되지 않았다. 소수 판별법만약, 특정 숫자 N이 소수인지 아닌지를 확인하는 문제를 해결한다고 하자. 소수의 정의에 의해서 소수는 1과 자기 자신으로만 나누어 떨어지므로, 반대로 2부터 자기 자신보다 1 작은 값까지는 나누어 떨어지지 않는다는 것을 알 수 있다. 따라서, N이 소수인지 여부를 판단하려면, 2부터 N-1까지 모든 숫자에 대해서 나누어 떨어지는지를 확인하는 방법을 사용할 수 있다.def is_prime(N: int) -> bool: for i in range(..

우선순위 큐일반적인 큐(Queue)는 First-In-First-Out(FIFO) 구조로, 먼저 들어온 데이터가 먼저 나가게 된다. 우선순위 큐는 일반적인 큐와는 다르게, 각 데이터에 우선순위가 존재하여 Pop 연산을 수행할 때 우선순위가 가장 높은 원소가 (or 우선순위가 가장 낮은 원소가) 나오는 큐이다. 우선순위 큐와 Linked List우선순위 큐는 일반적인 큐와 같이 Linked List를 이용해서 구현할 수 있다. 이렇게 구현하게 된다면 데이터 추가에 드는 시간복잡도는, Linked List의 Rear에 데이터를 추가하는 시간이므로 $O(1)$이 된다. 그러나, 우선순위 큐에서 값을 제거하는 연산은, 최대값 or 최소값을 찾아야하므로 Linked List 내부의 모든 데이터를 확인해야만 가능하..

이진 탐색 트리이진 탐색 트리는 다음 조건을 만족하는 트리이다.특정 노드의 자식 노드가 최대 2개인 이진 트리특정 노드의 왼쪽 서브트리에 존재하는 모든 값이 해당 노드의 값보다 작음특정 노드의 오른쪽 서브트리에 존재하는 모든 값이 해당 노드의 값보다 큼이진 탐색 트리는 최적의 경우, 노드의 개수가 $N$일때 삽입, 삭제, 탐색 모두 $O(\log N)$의 시간복잡도를 갖게 된다. 일반적으로는 트리의 높이를 $h$라고 했을 때, 세 작업 모두 $O(h)$의 시간복잡도를 갖게 된다. 이진 탐색 트리의 구현트리의 기본적인 뼈대를 Python으로 구성하면 아래와 같다. 이때 탐색, 삽입, 제거의 동작을 구현해보자.class Node: def __init__(self, val): self.val..

투 포인터투 포인터 알고리즘은, 배열이나 문자열에서 두 개의 포인터(=인덱스)를 사용해서 탐색 범위를 줄이는 알고리즘. 특히, 다중 반복문을 사용해서 모든 쌍을 확인해야 하는 경우에 문제를 더 효율적으로 풀 수 있도록 해준다. 만약, 배열에서 모든 쌍을 확인해야 한다면 이중 for문으로 $O(N^2)$의 시간복잡도를 통해 확인할 수 있지만, 조건이 존재한다면 투 포인터를 이용해 포인터를 조건에 따라 움직이며 $O(N)$의 시간복잡도만으로 해결할 수 있다. 즉, 모든 경우를 확인하는 대신에 조건에 맞는 경우를 찾아서 순회하는 알고리즘이라고 할 수 있다. 이러한 투 포인터로 풀 수 있는 문제 중 다수는 이분 탐색으로도 풀 수 있고, 이분 탐색으로 풀 수 있는 문제도 마찬가지로 투 포인터로 풀 수 있는 문제가..

이진 탐색이미 정렬되어 있는 데이터에서 특정 데이터를 찾기 위해, 탐색 범위를 계속 절반으로 나눠 탐색하는 알고리즘이진 탐색은 배열에서 특정 데이터를 탐색하기 위한 알고리즘이다. 배열의 모든 원소를 탐색하면서 $O(N)$의 시간복잡도로 원하는 데이터를 찾는 선형 탐색과는 다르게, 한 번 탐색할 때마다 범위를 절반으로 줄여가면서 탐색하므로 $O(\log N)$의 시간복잡도를 갖게 된다. 그러나, 이진 탐색은 반드시 정렬된 배열에서만 사용할 수 있으므로, 정렬되지 않은 데이터에 대해서는 정렬을 하기 위한 시간복잡도가 추가로 필요하게 된다. 해당 링크에서 선형 탐색과 이진 탐색의 시각적인 동작에 대해서 확인할 수 있다. 이진 탐색은 변수 3개를 이용해서 수행한다. 탐색 범위의 시작을 나타내는 start, 탐색..

그리디 알고리즘매 선택 시, 현재 시점에서 가장 최적인 값만을 선택하여 결과를 도출하는 알고리즘말 그대로, 현재 나한테 제일 이익이 되는 것은 무엇일지 보고 해당 값을 선택해가는 알고리즘이다. 이렇게 각 단계에서 최선의 선택을 하는 것이, 전체적으로도 최선임을 가정한 상태로 해결하게 된다. 다이나믹 프로그래밍(DP)와 같이, 매 순간의 최적값이 전체 문제의 최적값이라는 점은 동일하지만, DP와 다르게 꼭 세부 문제들이 동일한 구조는 아니어도 된다. 또한, 현재 시점에서의 최적 해결 방법만을 찾으면 되는 알고리즘이므로, 백트래킹과 같이 모든 경로를 탐색할 필요는 없기 때문에 연산 속도 측면에서 이득을 볼 수 있다. 그러나 반대로 생각하면 현재 시점에서의 최적 방법의 합이 전체적으로는 최적 해결 방법이 아닐..

다이나믹 프로그래밍하나의 큰 문제를 해결하기 위해서, 여러 개의 작은 문제로 나누어 해당 문제들을 푼 후, 이를 쌓아올려 주어진 큰 문제를 해결하도록 하는 알고리즘이다.이름의 유래?Dynamic에는 별 뜻이 없고, 리처드 벨만이 “Dynamic” 이라는 단어가 멋있어 보여서 붙였다고 한다. Programming은 최적화 연구에서 최적의 프로그램을 찾을 때 쓰는 단어라고 한다.이러한 다이나믹 프로그래밍(Dynamic Programming, DP)은 아래 두 가지 조건을 만족하는 문제에서 사용할 수 있다.Optimal Substructure(최적 부분 구조): 전체 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성되어야 한다.Overlapping Subproblems(부분 문제 반복): 동..

백트래킹이란?백트래킹(Backtracking)이란, 현재 상태에서 가능한 모든 후보를 탐색하여 정답을 찾도록 하는 알고리즘을 말한다.이때 일반적인 브루트포스(Brute Force) 알고리즘과 백트래킹의 차이점은, “정답을 찾는 도중 정답이 될 가능성이 없는 경우, 그 즉시 되돌아가 다른 경로를 탐색하여 답을 찾는다”는 것이다. 백트래킹이 작동되는 방식은 크게 다음과 같다:현재 상태에서 가능한 후보 중 하나를 고른다.해당 후보에서 재귀적으로 다음 단계를 탐색해 나간다.탐색하는 중, 정답이 될 수 없는 경우 탐색을 종료한다.주어진 조건을 모두 만족하는 경로인 경우, 해당 경로를 정답으로 처리한다.탐색이 끝나면, 상태를 원래대로 되돌린 후, 다른 후보를 골라 반복한다.문제를 풀기 위해서 위와 같은 상태 공간 ..

재귀함수란?재귀함수란, 함수 내부에서 자기자신을 다시 호출해 작업을 수행하도록 하는 함수를 말한다.재귀함수를 통한 문제 해결은 귀납적인 사고로 문제를 해결하는 방법이다. 다시 말해 어떠한 문제를 재귀적으로 푼다는 것은, 해당 문제를 수학적 귀납법의 형태로 표현 가능하다는 이야기로도 볼 수 있다.수학적 귀납법이란?주어진 명제가 모든 자연수에 대해서 참임을 증명하기 위해, 주어진 명제에 대해서해당 명제가 n=1일때 성립함을 보인다.해당 명제가 n=k일때 성립한다고 가정한 후, n=k+1일때도 성립하는지 증명한다. 재귀함수를 구현할 때는 아래와 같은 역할을 하도록 하여야 한다.특정한 입력에 대해서는 자기자신을 다시 호출하지 않고 함수가 종료되어야 한다. (= Base Condition)모든 입력은 Base C..

너비 우선 탐색 (BFS)BFS(Breadth-First Search)란, 한 지점에서 다른 지점들을 방문할 때, 너비를 우선으로 모든 지점을 방문하는 것장점: 시작 지점으로부터 도착 지점까지의 최소 거리를 항상 구할 수 있다.단점: DFS에 비해 더 많은 메모리를 사용한다.특정 노드를 기준으로 “인접한” 노드를 우선적으로 탐색하는 방식이다. 즉, 시작 지점으로부터 가까운 노드를 우선적으로 방문하고, 멀수록 늦게 방문하게 된다. 이는 특히 거리 측정 알고리즘을 구현할 때 주로 사용될 수 있다. 주로 다차원 배열에서 특정 지점까지 걸리는 최소 시간을 구하는 문제에 BFS를 주로 사용할 수 있다. 코드로 구현하기 위해서는 Queue를 사용한다. BFS를 이용해 모든 지점을 방문하는 방법은 다음과 같다.비어있..