정렬이란 이름, 학번, 학점 등의 키를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 말한다. 이렇게 데이터를 정렬하면 더 쉽게 검색할 수 있는 장점이 생긴다. 이 데이터들의 정렬 순서에 따라 2가지로 나뉠 수 있는데, 작은 데이터를 앞쪽에 늘어놓는 것을 오름차순 정렬이라고 하고, 그 반대를 내림차순 정렬이라고 한다. 그리고 정렬 알고리즘은 안정적인 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있다. 그렇다면 안정적인 알고리즘은 무엇일까? 안정적인 알고리즘은 값이 같은 원소의 순서가 정렬 후에도 유지되는 것을 말한다. 또한 내부 정렬과 외부 정렬 2가지로도 나눌 수 있는데, 내부 정렬이란 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘을 뜻하며..
소수 판별 알고리즘 기본적인 소수를 판별하는 알고리즘은 다음과 같다. def is_prime_easy_version(target): for i in range(2, target): if target % i == 0: return False return True 즉, target value를 제외한 그 전의 값들을 모두 target value와 나누어서 나누어 떨어지는 값이 있으면 그 target value는 소수가 아닌 것이다. 하지만 이 방식은 N값의 소수를 구하려고 할때, 최대 O(N)의 시간 복잡도를 갖는다. 따라서 이 시간 복잡도를 낮추기 위해 조금 다른 방법을 생각해봐야한다. 첫 번째로 생각한 것은 2부터 target value를 2로 나눈 몫까지로 target value를 나누고 만약 그 중에..
문제를 쪼개서 작은 문제의 답을 구하고, 그걸로 더 큰 문제의 답을 구하는 것을 반복하는 알고리즘 분할정복과 비슷한 느낌이다. DP 구현 2가지 방법 Top-down 구현 방법: 재귀 저장 방식: Memoization Bottom-up 구현 방법: 반복문 저장 방식: Tabulation Memoization 한 번 구한 답들은 저장해두자는 저장 방식이다. 즉, 부분 문제들의 답을 한 번 구했으면, 또 구하지 않도록 (중복연산 방지) cache에 저장해두고, 다음부터 가져다 쓰는 방식 필요한 부분 문제들만 구한다. (Lazy-Evaluation) Tabulation 부분 문제들의 답을 미리 다 구해두면 편하다. 테이블을 채워간다는 의미이다. 필요 없는 부분 문제들까지 전부 구한다. (Eager-Evalua..
탐색 전에 반드시 정렬되어 있어야하고, 범위를 절반씩 줄여가면서 답을 찾아야한다. 시간복잡도 따라서 정렬 O(NlogN) + 이진탐색 O(logN) -> 결과적으로 O(NlogN). 즉, 경우에 따라서 선형탐색 O(N) 이 더 좋은 선택이 될 수도 있다. 하지만 여러번 탐색을 해야하는 경우라면, 그 탐색의 횟수가 N번이라면, 선형 탐색의 경우에는 N * O(N) = O(N^2) 이 된다. 그러나 이진 탐색을 하면, 정렬 O(NlogN) + N * O(logN) = O(NlogN)이 된다. 결론 결과적으로 탐색을 한번만 하는 경우에는 굳이 정렬을 해가면서 이진탐색을 사용할 이유가 없다. 하지만 탐색을 여러번 해야하는 경우에는 정렬 한번 해두고, 이진탐색을 해주는게 더 빠를 수 있다. C++ lower/up..
기본적으로 모든 경우를 탐색하며, DFS/BFS와 방식은 유사하다. 하지만 백트래킹은 가지치기를 통해 탐색 경우의 수를 줄인다는 차이가 있다. 정리하면, 백트래킹은 최악의 경우에는 모든 경우를 다 살펴보게 될 수도 있지만, 가지치기를 통해서 가능한 덜 보겠다는 전략이다. 가지치기의 원리는 가망성이 없으면 가지 않겠다는 원리를 바탕으로 한다. 어려운 문제일수록 극한의 가지치기를 요구할 수 있음
시간복잡도 인접행렬: O(V^2) 인접리스트: O(V + E) == O(max(V,E)) 정점의 개수와 간선의 개수 중 더 큰 값을 기준으로 인접리스트는 간선의 개수가 적을수록 메모리 공간을 덜 잡아먹는 장점이 있었음 만약 간선의 개수가 V에 비해 월등히 적으면 O(V)로 표현이 될 수 있음 즉, 간선 개수가 적으면 인접리스트가 훨씬 유리해진다.
✍️ 정의 각 단계마다 가장 좋은 것만 선택하여 해답을 구한다. 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중에서 최선의 선택지라고 가정하는 알고리즘이다. 지금 선택이 앞으로 남은 선택에 어떤 영향을 끼치질 고려하지 않는다. 탐욕법을 적용하기 위해서 지역적으로 최적이면서 전역적으로 최적이어야 한다. 단계마다 하는 선택이 지역적으로는 최선이지만, 모든 단계를 거쳐 최종적으로 나온 해답이 최적이란 보장은 없다. 🔎 적용 조건 greedy choice property 앞의 선택이 이후 선택에 영향을 주지 않는다. 각 단계에서 가장 좋은 것을 선택하는 행위가 최적해로 가는 길이다. optimal substructure 문제의 최적해가 부분 문제에서도 최적해이다. 전체 문제 안에 여러 단계가 있고..
✍️ 정의 BFS 란? Breadth-First Search 시작 정점 방문 후 가까운 정점을 우선 방문한다. 넓게 탐색하는 방법 두 노드 사이의 최단 거리 및 최단 경로를 구할 때 자주 사용한다. 큐를 이용해서 구현 장점 최적해 찾음을 보장한다. (미로찾기 등 최단거리 구하기) 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않을 때. 단점 경로의 특징을 가지지 못한다. DFS 란? Depth-First Search 시작 정점 방문 후에 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방식 스택 또는 재귀함수로 구현 장점 최선의 경우 빠르게 해를 찾을 수 있다. 검색 대상 그래프가 정말 크다면 DFS를 고려 단점 찾은 해가 최적의 해가 아닐 가능성이 있다. ⏰ 시간..
✍️ 정의 이진 탐색, Binary Search 라고도 한다. 순차적 탐색보다 빠른 탐색을 위해 나온 탐색 방법으로 실제로 이분 탐색의 시간복잡도가 순차적 탐색보다 낮다. 🆚 순차적 탐색 vs 이분 탐색 순차적 탐색 정렬된 배열 안에서 특정 원소를 찾기 위해 인덱스 0부터 차례로 탐색 이분 탐색 정렬된 배열 안에서 특정 원소를 찾을 때, 인덱스 left와 right의 중간값과 비교 중간값과 비교해서 찾는 원소가 아니면 인덱스 left 또는 right를 다시 정해준다. 인덱스 left와 right를 정할 때마다 탐색 범위는 반으로 줄어든다. 🔎 이분 탐색 방법 처음 범위는 인덱스 left = 0, right = 끝, mid = (left + right) / 2 mid의 값과 찾는 원소를 비교한다. mid ..
