개요top이 가리키는 한 쪽 끝에서 Push, Pop이 일어나는 순서 리스트후입선출(Last In First Out, LIFO)스택에서 구현할 기능생성자: 스택 capacity 초기화 및 스택 배열 할당소멸자: 스택 배열 해제IsEmpty: 스택이 비어있는 지 확인Top: top이 가리키는 값 리턴Push: 꽉 찬 경우 두 배로 늘려서 데이터 옮기기Pop: top이 가리키는 값 추출Print: 스택 출력코드#pragma once#include template class Stack{public: Stack(int stackCapacity); ~Stack(); bool IsEmpty() const; T& Top() const; void Push(const T& item); void Pop(); void Pr..

Quick Sort분할 정복을 이용한 정렬 알고리즘이다. (값에 따른 비균등 분할)피벗을 정한 뒤 피벗의 위치를 확정해가며 정렬을 수행하는 것이 특징일반적으로 각 부분 배열의 맨 앞 or 뒤를 피벗으로 정하는데, 이는 정렬 과정 동안 유지되어야 한다.피벗이 확정되면 피벗의 앞에는 피벗보다 작은 값, 뒤에는 큰 값이 오게 한다. (오름차순 기준)코드#include void Print(int* arr){ for (int i = 0; i p부터 pivot 한 칸 앞까지 전진 for (int j = p; j 왼쪽/오른쪽에 pivot보다 작은/큰 수로 나뉨 return i;}void QuickSort(int* arr, int p, int r){ if (p QuickSort에서 배열을 분할..

Merge Sort분할 정복 알고리즘을 사용한 정렬위치에 따른 균등 분할모든 원소를 하나가 될 때까지 나눈 후, 순서를 맞춰 다시 합침코드#include int temp[100];void Print(int* arr){ for (int i = 0; i arr[j]) temp[k++] = arr[j++]; else temp[k++] = arr[i++]; } // 남은 값 모두 옮기기 while (i MergeSort 함수에서 p와 r은 배열의 처음과 마지막을 가리키는 포인터다. p  Merge 함수에서는 나뉜 배열의 arr[p ~ q]와 arr[q+1 ~ r]을 정렬해서 합친 새로운 배열 temp를 만든다. 모든 과정이 끝났다면 원본..

Insertion Sort정렬된 부분과 정렬되지 않은 부분으로 나눔정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하는 것을 반복정렬된 배열을 유지하면서 진행맨 처음 원소는 정렬되었다고 가정하고 시작함코드#include void Print(int* arr){ for (int i = 0; i pivot && j >= 0) { arr[j+1] = arr[j]; // 오른쪽으로 당김 j--; } arr[j+1] = pivot; }}int main(){ std::cin.tie(0); std::ios::sync_with_stdio(0); int arr[10] = {8, 31..

Bubble Sort이웃하는 값과 비교해 특정 수(최대 or 최소)를 한 쪽(앞 or 뒤)로 이동시키는 과정을 반복 코드#include void Print(int* arr){ for (int i = 0; i 0; i--) { for (int j = 0; j arr[j+1]) std::swap(arr[j], arr[j+1]); } }}int main(){ std::cin.tie(0); std::ios::sync_with_stdio(0); int arr[10] = {8, 31, 48, 73, 3, 65, 20, 29, 11, 15}; Print(arr); BubbleSort(arr); Print(arr);..

Selection Sort각 루프마다 남아있는 원소 중 가장 큰 원소를 선택한 후, 남아있는 원소 중 맨 오른쪽 원소와 바꿈교환된 수는 다음 루프에서 제외하나의 원소가 남을 때까지 반복코드배열의 크기가 10으로 고정되어있다고 가정하고 작성한 코드이다.#include void Print(int* arr){ for (int i = 0; i 0; i--) { int maxNum = arr[0]; int maxIdx = 0; for (int j = 0; j maxNum) { maxNum = arr[j]; maxIdx = j; } } std::s..

개요이전 게시글에서 백트래킹 기법을 사용해 배열을 통해 순열과 조합을 구현했다. 다만, 백트래킹을 사용한 순열과 조합의 구현은 복잡하기 때문에 실수할 여지가 있다. 이번 게시글에서는 algorithm 헤더파일의 next_permutation과 prev_permutation을 통해 순열과 조합을 쉽게 구현하는 방법을 알아보자.next_permutation로 순열 구하기next_permutationbool std::next_permutation(BidirIt first, BidirIt last) // STL 컨테이너 사용 가능bool std::next_permutation(T *first, T *last) // 배열 사용 가능[first, last) 범위에서 다음 수열 결과를 인수로 전달된 컨테이너 or 배..

백트래킹이란?백트래킹은 가능한 모든 경우의 수를 따라 들어가면서 탐색하는 알고리즘이다.답이 될 수 없는 경우 더 이상 탐색하지 않고 뒤로 돌아간다.주로 재귀 함수를 사용해 구현한다.시간 복잡도는 O(N!)으로 매우 큰 편이다. 그렇기 때문에 백트래킹 관련 문제에서는 N이 작게 주어진다. 백트래킹 구현에서 가장 중요한 점은 방문 상태 변화 & 상태 원상 복구 두 가지다. 로직을 작성할 때 항상 염두에 두자.백트래킹과 순열, 조합순열과 조합을 구할 때, 가능한 모든 경우의 수에 대해 검사하기 때문에 백트래킹을 사용할 수 있다.아래에서 설명하는 순열과 조합은 오름차순으로 정렬된 집합을 기준으로 한다. 아래 코드에서 공통적으로 나오는 변수들은 다음을 나타낸다.isUsed[i]: i번째 수가 사용되었는 지 여부를..