알고리즘C++

시간복잡도와 공간복잡도에 대해 알아보고, 모든 알고리즘에 가장 기초가 되는 브루트 포스 알고리즘에 대해서도 알아보겠다

거품정렬, 선택정렬, 삽입정렬에 대해 알아보겠다 In-Place정렬 > 쉽게 말하자면 외부 메모리를 거의 쓰지않고 주어진 배열 내부의 swap이나 대입으로 작업을 수행하는 것 > 제자리 알고리즘

에라토스테네스의 체 대량의 숫자들 중 소수를 판별할 때 유용하게 사용되는 방식이다 소수들의 배수를 차례차례 삭제해나가면서 마지막에 남은 소수들을 얻어내는 것

계수 정렬 ➡ 동일한 값이 여러개일 때 정렬하기 좋은 방법으로, 특정 값이 몇번 나왔는지에 따라 정렬 수행

투 포인터 > 두 개의 포인터를 활용해서 배열의 요소를 효과적으로 탐색하는 알고리즘이다 > -> 실제 포인터는 아님 > -> 전체적인 흐름만 봤을때 end와 start를 이동시키면서 내가 찾고자 하는 값과 비교하여 해당 값이 몇개 있는지 찾는 것

이진 탐색 > 탐색 범위를 반으로 나누어서 찾는 값을 포함하는 범위를 좁혀나가는 방식의 알고리즘이다 > 주로 오름차순으로 정렬되어 있는 상태에서 사용해야한다

분할정복 > 주어진 2개 이상의 부분으로 문제를 나눈 뒤, 각 부분 문제에 대한 답을 재귀적으로 호출하여 계산하고, 답으로부터 전체 문제의 답을 계산해내는 알고리즘이다. > 쉽게 말해, 큰 문제를 작은 문제로 분할하여 문제를 해결하는 방법

정렬 알고리즘의 좋고 나쁨의 판단 기준 복잡도 추가적으로 필요한 메모리 (in-Place성) 안정적 정렬 여부 (안정성)

기준점을 얻은 다음, 기준점을 기준으로 부분 배열로 나누고, 한쪽은 기준점보다 작은 값들이 위치하고 다른 한 쪽은 기준점보다 큰 값들이 위치하도록 정렬하는 알고리즘이다

병합 정렬 > 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 정렬 알고리즘이다

1.일반적인 최대공약수 구하기 2. 유클리드 호제법

그리디 알고리즘 > 최적의 해를 구하는 데에 사용되는 알고리즘 > 여러 경우 중 하나를 결정해야 할 때 마다 그 순간에 최적이라고 생각되는 것을 선택해 최종적인 해답을 구하는 알고리즘이다 탐욕법 적용 조건 1. 탐욕 선택 속성 2. 최적 부분 구조

메모이제이션 & 다이나믹 프로그래밍과 Bottom-Up (상향식), Top-Down (하향식)

백트래킹 > 해를 찾아가는 도중에 지금의 경로가 해가 될 것 같지 않으면, 더 이상 깊이 들어가지 않고, 이전 단계로 다시 돌아가는 알고리즘이다

깊이 우선 탐색 root 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 알고리즘이다

너비 우선 탐색 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 탐색 방법이다

위상 정렬 순서가 정해져있는 작업을 순서대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘이다 -> 어떤 작업을 수행하려면 다른 작업이 먼저 끝나야한다는 의미

유니온 파인드 서로소 집합을 관리하기 위한 자료구조이다 같은 집합에 속하는지 확인할 때 사용한다 (합집합 찾기)

신장트리 (Spanning Tree) 형태와 관계없이 모든 정점을 사이클 없이 이을 수 있으면 그것이 바로 신장트리이다

**시작점으로부터 모든 노드까지의 최소 거리를 구해주는 알고리즘이다 "한 노드에서 다른 노드로 가는 경로의 최소 비용"**

시간복잡도 O(N) 빅오 표기법 -> 최고차항을 제외한 값 제거, 상수계수 무시 브루트 포스 무식한 방법임 그냥 처음부터 끝까지 다 확인하는 방법 for문 Inplace정렬 제자리 알고리즘이라고도 한다. 그냥 메모리 더 쓰지 않고 그 안에서 이루어지는 정렬 거품정렬

재귀관련 알고리즘 목록 & 문제

강한 결합 요소 그래프 안에서 강하게 결합된 정점의 집합을 의미한다 (Strongly Connected Component)

문자열 매칭 > : 문자열에 해싱 기법을 사용하여, 해시 값으로 비교하는 문자열 알고리즘이다