본문 바로가기

Computer Basics/Algorithm Techniques19

퀵 정렬(Quick sort)_개념/시간복잡도/Unstable/In-place 퀵 정렬에 대한 이해 - 퀵 정렬이란, 피벗을 설정하여 이를 올바른 위치로 이동시킨 뒤 나머지 원소들을 두 개의 배열로 분할하여 재귀적으로 정렬시키는 알고리즘이다. - 합병정렬과 달리, 배열이 불균등하게 분할된다.(운이 좋으면, 균등하게 분할 될 수도 있다.) 코드를 먼저 보면, void quickSort(int st, int en) { if (en 2022. 2. 19.
합병정렬(Merge sort)_개념/시간복잡도/Stable/Not In-place 합병 정렬에 대한 이해 - 합병정렬이란, 하나의 배열을 두개의 균등한 배열로 분할하고 분할된 배열을 각각 정렬한 다음, 이를 다시 합하여 정렬을 완성하는 알고리즘이다. - 합병정렬은 분할 정복의 일종으로, 하나의 큰 문제를 두개의 작은 문제로 분할하여 해결한 다음, 결과를 모아서 문제를 완전히 해결하는 전략이다. 코드를 먼저 살펴보면, void mergeSort(int st, int en) { if (en == st+1) return ; int mid = (st+en)/2; mergeSort(st, mid); //arr[st:en]을 두개의 균등한 배열로 분할하여 각각 정렬 mergeSort(mid, en); merge(st, en); //정렬된 두개의 배열 arr[st:mid], arr[mid:en]을.. 2022. 2. 19.
최대공약수(GCD)_Euclidean, 최소공배수(LCM) 최대공약수(Greatest Common Divisor) 최대공약수란, 두 수의 공통된 약수들 중 가장 작은 수이다. 예를 들어, 20과 12의 약수는 다음과 같고 공통된 약수 중 가장 큰 수는 4이다. 20 : 1, 2, 4, 5, 10, 20 12 : 1, 2, 3, 4, 6, 12 두 수의 최대 공약수를 구하는 가장 원초적인 방법은 두 수의 약수를 모두 구하고, 이중 for문으로 공통인 약수를 탐색하면서 최댓값을 찾는 것이다. #include #include using namespace std; vector getDivisor(int n) { vector v; for (int i=1; i*i=0; i--) { if (v[i] == n/v[i]) continue; v.push_back(n/v[i]); .. 2022. 2. 15.
삽입정렬(Insertion Sort) 개념/시간복잡도/Stable/In-place 삽입정렬에 대한 이해 - 삽입정렬이란, 새로운 원소를 이전까지 정렬된 원소 사이에 올바르게 삽입시키는 알고리즘이다. - 새로운 원소를 올바른 위치에 삽입시켜나가는 과정을 모든 원소에 대해 수행하면 정렬이 완성된다. N = 8인 다음과 같은 수열을 오름차순으로 정렬해보자. 0번째 인덱스에 있는 수는 그 자체로 정렬이 되어있으므로 그 다음 인덱스인 1번 인덱스 부터 올바른 위치에 삽입을 시작한다. 인덱스 1번 이전에 있는 수와 1번을 비교했을 때, 인덱스 0번에 있는 수 3은 인덱스 1번에 있는 수 7보다 작으므로 자리 교환없이 삽입을 끝낸다. 이후, 인덱스 2번에 있는 수를 이전까지 정렬된 수열 [3, 7] 에 삽입한다. 인덱스 2번 이전에 있는 수들과 2번을 비교했을 때, 인덱스 1번에 있는 수 7은 인.. 2022. 2. 11.
버블정렬(Bubble sort) 개념/시간복잡도/Stable/In-place 버블정렬에 대한 이해 - 버블 정렬이란, 인접한 두 원소를 비교해 나가며 가장 큰 원소를 끝으로 보내는 과정을 N-1번 반복하는 알고리즘이다. - 선택정렬과 유사하게, N-1번 부터 1번까지의 자리에 대하여 남아있는 수들 중 가장 큰 수를 각 자리로 보낸다. - 이 때, 버블정렬은 남아있는 수들 중 가장 큰 수를 인접한 두 수를 비교해가며 찾는다. N = 8인 다음과 같은 수열을 오름차순으로 정렬한다고 할 때, 7번째 자리에 위치해야 할 숫자는 인덱스 0번부터 7번까지에 있는 숫자들 중 가장 큰 숫자가 된다. 인접한 두 수를 비교해가며 가장 큰 수를 끝으로 보낸다. 인덱스 0번과 1번에 있는 숫자를 비교하였을 때, 0번에 있는 숫자 3은 1번에 있는 숫자 7보다 작으므로 넘어간다. 이어서, 인덱스 1번에.. 2022. 2. 11.
선택정렬(Selection sort) 개념/시간복잡도/Unstable/In-place 선택정렬에 대한 이해 - 선택 정렬이란, N-1번부터 1번까지의 자리에 대하여 해당 자리에 넣어야 하는 원소를 선택하는 알고리즘이다. - 오름차순으로 정렬한다면, N-1번부터 1번까지의 자리에는 남아있는 수들 중 가장 큰 수를 선택하여 넣어야 한다. N = 8인 다음과 같은 수열을 오름차순으로 정렬한다고 할 때, 7번째 자리에 위치해야 할 숫자는 인덱스 0번부터 7번까지에 있는 숫자들 중 가장 큰 숫자가 된다. 따라서 0번부터 7번까지의 인덱스를 순회하여 가장 큰 숫자가 있는 인덱스 1번을 알아낸다. 이후, 인덱스 7번에 있는 숫자 0과 1번에 있는 숫자 7을 swap() 함수를 이용하여 교환한다. 6번째 자리에 위치해야 할 숫자는 인덱스 0번 부터 6번까지에 있는 숫자들 중 가장 큰 숫자가 된다. 따라.. 2022. 2. 3.
BFS(Breadth First Search) BFS에 대한 이해 - BFS 란, 시작점으로 부터 너비(거리)를 우선으로 탐색을 진행하는 방법이다. - 보통 BFS 알고리즘은 그래프 자료구조나 2,3차원의 배열과 함께 쓰인다. 너비를 우선으로 탐색한다함은 '거리'를 기준으로 가까운 노드부터 탐색한다는 의미이다. 다음과 같은 그래프 자료구조에서 보라색 노드를 시작 지점으로 탐색을 진행할 때, 보라색 노드로 부터 거리가 1인 초록색 노드들을 먼저 탐색하고, 보라색 노드로 부터 거리가 2인 주황색 노드들은 다음으로 탐색한다. 따라서 BFS 탐색 방법을 사용하여 위의 그래프를 모두 탐색하는 경우, 노드 번호를 기준으로 1 -> 3 -> 2 -> 5 -> 4 -> 6 -> 7 을 지나 탐색이 종료된다. BFS의 구현 BFS는 '큐'로 구현하는 것이 일반적이다.. 2022. 1. 10.
동적계획법(Dynamic Programming) 동적계획법에 대한 이해 피보나치 수열은 첫째항이 0, 둘째항이 1이고 이전 두항을 더해가며 새로운 항의 값을 구해나가는 수열이다. 0, 1, 1, 2, 3, 5, 8, 13 ... 과 같이 이어지며, 점화식은 다음과 같다. F(N) = F(N-1) + F(N-2) (N >= 2) F(0) = 0, F(1) = 1 N번째 항의 값을 구하는 문제는, N-1번째 항을 구하는 문제와 N-2번째 항을 구하는 문제로 나누어질 수 있다. 이렇게 큰 문제를 작은 문제로 나누어 풀 수 있는 경우를 최적 부분 구조(Optimal Structure) 라고 한다. 최적 부분 구조에 대해 자세히 말하면, 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우를 말한다. 최적 부분 구조를 가지는 피보나치 수.. 2021. 11. 17.
소수 판별 알고리즘과 에라토스테네스의 체 소수 판별 알고리즘 소수 판별 알고리즘은 시간복잡도에 따라 다르게 구현 가능하다. 시간 복잡도 O(N) 소수란, 약수가 1과 자기자신 뿐인 수를 말한다. 따라서 N이 소수인지 판별하는 가장 쉬운 방법은 2부터 N-1까지의 수로 나누어 떨어지는지 확인하고, 나누어 떨어진다면 소수가 아니라고 판단하는 것이다. bool isPrime(int N) { if (N < 2) return false; for (int i=2; i 2021. 11. 9.

티스토리툴바