정의 최대/최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법 시간 복잡도는 O(N^2)이다 핵심 이론 최대/최소 값을 찾고 남은 정렬 부분의 가장 앞에 있는 데이터와 Swap하는 것이 핵심이다 구현 #include #include using namespace std; void SelectionSort(vector& v) { for (int i = 0; i v[j]) { min = j; } } swap(v[min], v[i]); } } int main() { vector v = { 42,40,24,62,32 }; Selection..

정의 다른 정렬에 비해 시간이 오래걸리지만 로직이 단순하고 구현이 간단하다 데이터의 인접 요소끼리 비교, swap연산을 수행하며 정렬하는 방식 핵심 인접한 데이터의 크기를 비교해 정렬하는 방식 시간복잡도는 O(n^2)으로 다른 알고리즘에 비해 느리다 인접한 데이터간에 Swap 연산으로 정렬한다 정렬 과정 비교 연산이 필요한 루프 범위를 설정한다 인접한 데이터 값을 비교한다 swap 조건에 부합하면 swap 연산을 수행한다 루프 범위가 끝날 때 까지 2,3번 과정을 반복한다 정렬 영역을 설정하여 다음 루프를 실행할 때 이 영역을 제외한다 비교대상이 없을 때 까지 위의 과정을 반복한다 구현 #include #include using namespace std; void BubbleSort(vector& v) ..

스택 정의 삽입 삭제 연산이 후입선출로 이뤄지는 자료구조 삽입 삭제가 한 방향에서 이뤄진다 스택에 값이 들어오면 top이 새 값을 가리킨다 값을 빼낼 때는 top이 가리키는 값이 빠지고 이전 값을 가리키게 된다 용어 top: 현재 값이 들어있는 위치, 값이 없을 땐 -1에서 시작한다 pop: 데이터를 삭제하고 확인하는 연산 push 값을 넣어주는 연산 우선 탐색(DFS), 백트래킹등 재귀함수를 이용하는 알고리즘에서 효과적이다 큐 정의 스텍과 반대롤 삽입 삭제 연산이 선입선출로 이뤄진다 삽입삭제가 양 방향에서 이뤄진다 push는 back, pop은 front에서 이뤄진다 용어 back: 큐의 가장 끝의 데이터 front: 큐의 가장 처음 데이터 push: back부분에 새로운 데이터를 삽입하는 연산 pop..

정의 합 배열을 이용해 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 합 배열 S[i] = A[0] + A[1] + A[2]+ ... + A][i]를 통해 미리 합을 구해 배열에 저장해 놓는 것 합 배열을 미리 구하면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(n)에서 O(1)이 된다

배열 정의 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 인덱스를 통해 배열의 값을 참조할 수 있다 선언한 자료형의 값만 저장이 가능하다 특징 인덱스를 사용해 값에 바로 접근 가능 새로운 값을 삽입하거나 특정 인덱스를 삭제하는 것이 어렵다 크기는 선언할 때 지정할 수 있으며, 선언한 크기를 늘리거나 줄일 수 없다 구조가 간단하다 리스트 정의 값과 포인터를 묶는 노드를 포인터로 연결한 자료구조 특징 인덱스가 없어 값에 접근하려면 Head 부터 순서대로 접근해야해서 접근 속도가 느리다 포인터로 연결되어 있어 삽입 삭제가 빠르다 선언할 때 별도의 크기를 지정하지 않아도 되며 크기를 변경할 수 있다 포인터를 저장할 공간이 필요해 배열보다 구조가 조금 복잡하다 벡터 정의 기존 배열과 같은 특징을 가지면서..

시간 복잡도 연산 회수를 말한다 복잡도 유형 빅-오메가: 최고 연산 회수 빅-세타: 일반 연산 회수 빅-오: 최악 연산 회수, 코테에서 사용하는 복잡도이다 그래프 연산 횟수 계산 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출 시간 복잡도 도출 상수는 시간 복잡도 계산에서 제외 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다 이를 통해 비효율적인 로직을 효율적으로 바꾸어 시간 복잡도를 줄이는데 도움이 된다