알고리즘

1. 개념 1. 퀵 셀렉트퀵 셀렉트는 주어진 배열에서 k째로 작은 원소를 찾는데 활용되는 알고리즘입니다. 퀵 셀렉트 알고리즘은 퀵 정렬과 비슷한 분할-정복 방식을 활용하지만, 주어진 배열을 모두 정렬하는 대신 특정 원소를 찾는 작업에 초점을 맞춥니다. 퀵 셀렉트 알고리즘은 평균적으로 O(n)의 시간 복잡도를 가지며, 최악의 경우 O(n²)의 시간 복잡도를 갖습니다. 최악의 시간 복잡도가 O(n²)인 이유는 퀵 정렬과 같습니다. 2. 동작 방식주어진 배열에서 피벗을 선택합니다.피벗 원소를 기준으로 배열을 두 개의 부분 배열로 나누고, 피벗 원소보다 작은 원소는 왼쪽 부분 배열로 이동시키고, 반대로 피벗 원소보다 큰 원소는 오른쪽 부분 배열로 이동시킵니다.k(찾고자 하는 k번째 작은 원소의 위치)가 피벗의 ..

#1. 개념 1. LCA(Least Common Ancestor) LCA 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상 노드를 찾는 알고리즘입니다. 이때, 가장 가까운 노드란, 주어진 두 노드의 경로 상에서 가장 깊은 곳에 위치한 공통 조상 노드를 의미합니다. LCA 알고리즘을 효율적으로 구현하는 방법으로 Binary Lifting 기법이 있습니다. 2. Binary Lifting 기법  Binary Lifting 기법은 주어진 트리 자료구조에서 두 노드의 LCA를 찾는 방법 중 하나입니다. 특히, Binary Lifting 기법은 깊이가 깊은 트리에서 두 노드의 LCA를 찾는데 효율적입니다. BL의 핵심 개념은 각 노드에 대해 미리 점프할 수 있는 조상 정보를 계산해 ..

#1. 개념 1. 투 포인터 [정의] : '투 포인터' 알고리즘은 두 개의 포인터를 활용해 원하는 조건을 만족하는 부분을 찾는 알고리즘입니다. [특징] : '투 포인터' 알고리즘은 일반적으로 정렬된 배열 혹은 리스트에서 활용합니다. [동작 방식] 배열의 시작 지점을 가리키는 포인터, 그리고 끝 지점을 가리키는 포인터, 두 개의 포인터를 초기화합니다. 두 포인터가 움직이며 주어진 조건을 만족하는지 검사합니다. 조건을 만족할 경우, 원하는 동작을 수행하고, 조건을 만족하지 못할 경우, 포인터를 이동시킵니다. 원하는 결과 값을 얻을 때까지, 2~3번 동작을 반복합니다. #2. 예제 1. 연속된 부분 수열의 합 [Programmers]#Level2_연속된 부분 수열의 합, 투 포인터 [Programmers 알고..

[알고리즘]#6_백 트래킹 백 트래킹 알고리즘에 대해 알아보겠습니다. Overview 개념 예제 #0. 개념 1. 백 트래킹 백 트래킹 알고리즘은 문제 해결을 위해 여러 후보 해결책들을 점진적으로 탐색하며, 현재 선택한 경로가 해결책으로 이어질 수 없다고 판단되면, 이전 단계로 돌아가(백 트래킹) 다른 경로에 대한 탐색을 시도하는 방법입니다. 이처럼 백 트래킹 과정을 통해 문제의 모든 후보 해결책들을 효과적으로 탐색할 수 있습니다. 특히, 백 트래킹 알고리즘은 모든 가능한 해결책 후보를 조합적으로 탐색해야 할 때, 최고의 성능(시간, 자원)을 보여줍니다. 따라서, 백 트래킹 알고리즘은 (1) 미로 찾기, (2) 스도쿠, (3) 순열, (4) 조합, (5) N-Queens 문제, 그리고 (6) 그래프의 탐..

[알고리즘]#5_동적 계획법 동적 계획 알고리즘에 대해 알아보겠습니다. Overview 개념 예제 #0. 개념 1. 동적 계획법(Dynamic Programming) 동적 계획법은 최적화 문제를 해결하는 데 사용되는 알고리즘 디자인 기법 중 하나입니다. 동적 계획법은 입력 크기에 따라 중복되는 하위 문제를 재귀적으로 해결하고, 이 결과 값들을 기억하는 것으로 중복 계산을 피해 최적화를 수행하고 효율적으로 최적해를 찾아냅니다. 2. Memoization #include #include using namespace std; long long dp[101] = { 1, 1, }; long long Fib(int n) { if (n

[알고리즘]#4_분할-정복 알고리즘 분할-정복 알고리즘에 대해 알아보겠습니다. Overview 개념 예제 #0. 개념 1. 분할 정복 알고리즘 분할 정복 알고리즘은 먼저 전체 문제를 원래 문제와 유사하지만 크기가 더 작은 몇 개의 부분 문제로 "분할"하여 재귀적으로 해결합니다. 그리고, 분할된 부분 문제들에서 찾은 해를 결합하여 원래 문제의 해를 찾아내는 알고리즘 방법론입니다. 일반적으로, 분할-정복 알고리즘은 다음 세 가지 단계로 구성됩니다. (1) 분할 : 현재 문제를 같은 문제를 다루는 다수의 부분 문제로 분할한다.(2) 정복 : 이렇게 분할된 부분 문제들을 재귀적으로 해결합니다. 분할된 부분 문제들의 크기가 충분히 작다면(Base Case) 직접적인 방법으로 해를 찾아냅니다. (3) 결합 : 부분..

#1. 개념 1. 정렬 알고리즘 [정의] : 정렬 알고리즘은 데이터를 특정한 순서로 재배치하는 알고리즘입니다. 정렬 순서는 일반적으로 오름차순(ascending order/less) 또는 내림차순(descending order/greater)으로 정렬되며, 정렬된 데이터는 효율적인 검색, 삽입, 삭제 등의 연산을 가능케 합니다. [종류] 1. 삽입 정렬 : 배열을 순회하며, 현재 원소를 이미 정렬된 부분 배열과 비교하며 적절한 위치에 삽입 2. 선택 정렬 : 배열에서 가장 작은 원소를 선택해, 정렬되지 않은 부분의 첫 번째 원소와 교환 3. 버블 정렬 : 배열의 인접한 두 원소를 비교하여 정렬 4. 병합 정렬 : 분할-정복을 기반으로 배열을 두 부분 배열로 분할하여 정렬하고, 병합 5. 퀵 정렬 : 분할..

#1. 개념 1. 길 찾기 알고리즘[정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구성된 그래프에서 최단 경로 혹은 특정 조건을 만족하는(최소 신장 트리, etc) 경로를 찾는 데 사용됩니다. 다양한 종류의 길 찾기 알고리즘이 있으며, 알고리즘의 선택은 그래프의 크기, 가중치의 종류, 실행 시간 제약 등을 고려합니다. 따라서, 알고리즘의 특징과 제약 사항 등을 이해해야 주어진 문제에 가장 적합한 알고리즘을 선택할 수 있습니다.[종류]1. "단일 출발(single-source)" :  주어진 단일 노드 v로부터 다른 모든 노드 사이의 최단 경로를 찾는 문제 2. "단일 쌍(single-pair)" :..

#0. 개념 1. 이분 탐색? [정의] : 이분 탐색은 정렬된 배열에서 특정 값을 찾기위해 사용되는 탐색 알고리즘입니다. [동작 방식] 1. 먼저, 배열의 왼쪽 경계와 오른쪽 경계를 설정합니다. 2. 중간 값을 얻어 찾고자하는 특정 값과 그 크기를 비교합니다. 3. 위 비교 연산의 결과에 따라서 왼쪽 경계 혹은 오른쪽 경계를 변경합니다. 4. 위 작업을 반복하며, 최종적으로 특정 값을 찾아냅니다. * 주의할 점 : 이분 탐색은 '정렬된' 배열에 사용되는 탐색 알고리즘입니다. 2. 코드 int BinarySearch(vector v, int l, int r, int x) { while (l x) r = mid - 1; // 찾고자 하는 값이 중간값보다 큰 경우, 오른쪽 배열 탐색 else l = mid +..