[C++] 자료구조, 알고리즘 공부
1. 알고있는 정렬 알고리즘을 설명해주세요.
버블정렬
처음부터 두개씩 큰 수를 비교 하여 swap합니다. n-1번 비교하며, n번의 swap을 진행 합니다.
task_bubble = [&sv]() // bubble sort
{
int size = sv.size();
for (int i = size - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (sv[j] < sv[j + 1]) std::swap(sv[j],sv[j+1]);
}
}
};
시간 복잡도
1. 평균 : O(N)
2. 최악 : O(N^2)
언제 유용한가요 ?
- 데이터 크기가 작을때
언제 피해야 하나요 ?
- 데이터 크기가 클때 (O(N^2))
선택정렬 O(N^2)
처음 값을 끝 사이 값중에 젤 작은 값을 변수에 저장하여 구하고 swap해 줍니다. n-1번 비교하지만 버블과 다르게 n번의 swap을 하진 않고 사이클당 한번만 swap 합니다. 작은 DB 기준으로 좋은 알고리즘입니다.
task_select = [&sv]() // select sort
{
int size = sv.size();
for (int i = 0; i < size; i++) {
int temp_idx = i;
for (int j = i+1; j < size; j++) {
if (sv[j] > sv[temp_idx]) temp_idx = j;
}
std::swap(sv[i], sv[temp_idx]);
}
};
시간 복잡도
1. 평균 : O(N^2)
2. 최악 : O(N^2)
언제 유용한가요 ?
- 데이터 크기가 작을때
- 교환 횟수가 많지 않을것 같을때
언제 피해야 하나요 ?
- 데이터 크기가 클때 (O(N^2))
- 교환 횟수가 많을것 같을때
삽입정렬 O(N^2)
두번째 값부터 시작하여 뽑아서 저장해두고 왼쪽값이랑 비교 후 작으면 왼쪽 값을 오른쪽으로 밀고 저장해놨던 값을 넣어 줍니다. 왼쪽에 값이 많을 경우 하나하나 비교 해가며, 값이 클 경우 오른쪽으로 밀려서 비어있는 그 위치에 삽입 시키는 알고리즘 입니다. 작은 DB 기준으로 좋은 알고리즘입니다.
task_insert = [&sv]() // insertion sort
{
int size = sv.size();
for (int i = 1; i < size; i++) {
int current = sv[i];
int j = i-1;
while (j>=0 && sv[j]<current) {
sv[j + 1] = std::move(sv[j]);
j--;
}
sv[j + 1] = current;
}
};
시간 복잡도
1. 평균 : O(N) (정렬되어 있을 때)
2. 최악 : O(N^2)
언제 유용한가요 ?
- 데이터 크기가 작을
- 거의 정렬이 되어 있을 때
- 새로운 데이터 실시간으로 추가하면서 진행할 때
언제 피해야 하나요 ?
- 데이터 크기가 클거나 무작위로 정렬되어 있을 때 (O(N^2))
퀵정렬 (O(log(N)))
분할정복과 재귀를 사용하는 정렬입니다. 최선의 경우엔 O(logN)이며, 첫번째 값을 pivot으로 두고 start = pivot+1, end = 마지막원소로 설정 후 start가 처음으로 pivot보다 커지는 idx, 반대로 end는 pivot보다 작아지는 idx를 찾은 후 start가 end보다 커지면(엇갈림) end와 pivot 교환 후 재귀로 교환된 위치 기준으로 두개로 나눠서 또 함수를 이어나갑니다. 만약 idx가 엇갈리지 않았으면 두 값 교환 후 다시 이어서 진행 합니다. 최악의 경우엔 O(N^2)입니다. 피벗을 고를때 그 값이 중간값이면 두개씩으로 나눠서 진행되어 NlogN이지만 첫번째나 마지막 값이면 전부 찾아야 함으로 N^2이 됩니다.
* std::sort에서도 사용할 정도 대부분 내부 정렬에서 사용됩니다.
void quick(std::vector<int> &v, int begin_, int last_) { // quick sort
int begin = begin_+1;
int last = last_;
int pivot = begin;
int temp;
while (begin<=last) {
{
if (begin >= last) return;
while (v[begin] > v[pivot] && begin <= last) begin++;
while (v[last] < v[pivot] && begin < last) last--;
if (begin>=last) continue;
temp = v[begin];
v[begin] = v[last];
v[last] = temp;
}
temp = v[last];
v[last] = v[pivot];
pivot = temp;
quick(v, begin_, last-1);
quick(v, last+1, last_);
}
}
시간 복잡도
1. 평균 : O(N*log(N))
2. 최악 : O(N^2) (피벗선택 잘못되었을때)
공간복잡도
O(log(N)) - 재귀 호출로 logn의 메모리가 필요합니다.
언제 유용한가요 ?
- 재귀 호출이 허용되는 공간일 때
언제 피해야 하나요 ?
- 최악의 피벗이 선택 되었을 때
- 안정적인 정렬이 필요할때 (퀵정렬은 불안정 정렬)
병합정렬
퀵정렬과 함께 빠른 정렬 알고리즘으로 쓰이지만, 퀵정렬은 최악일때 O(N^2)인것에 비해 병합정렬은 O(logN)이 거의 보장됩니다. 그럼 병합정렬만 쓰면 되지 않나 싶지만, 병합정렬은 따로 저장해 두는 메모리 공간이 많이 필요 함으로 메모리 공간이 여유롭지 않거나 적으면 퀵정렬, 메모리가 괜찮으면 병합정렬을 사용합니다.
시간 복잡도
1. 평균 : O(N*log(N))
2. 최악 : O(N*log(N))
공간복잡도
O(N) - N만큼의 추가적인 배열이 필요합니다.
2. Map과 HashMap 차이점을 설명해 보세요.
- HashMap은 대표적으로 unordered_map이 있습니다. 자료가 많아질수록 어떤 자료를 찾을때 unordered_map이 hashing해서 O(1)으로 유리하지만, map에서 find를 할 땐 문자를 앞에서 부터 비교 하기에 긴 문자열로 저장 될 때는 map이 우수 할 때도 있습니다. 그치만 유사도가 높으면 map 성능이 떨어집니다.
1. 자료탐색에 Map은 이진 탐색 트리를 이용하고, HashMap은 Hashing을 사용합니다.
2. 탐색속도는 Map은 O(logn)이고, HashMap은 O(1) 이상입니다. (이유는 1번을 보면 알 수 있음)
3. Map은 자료를 정렬하고 , HashMap은 자료를 정럴하지 않습니다. (이유는 1번을 보면 알 수 있음)
hashing : 해시 함수를 사용하여 해시테이블에 데이터를 저장하는것.
3. Red-Black Tree에 대해 설명해 보세요.
- 균형 이진 트리로 이루어져있습니다. 이진 트리 특성상 삽입과 삭제시 루트를 기준으로 큰것은 오른쪽 작은것은 왼쪽에 배치 되는데, 중간에 균형이 깨지면 O(logN) 이 O(N)이 될 수도 있는데 그 단점을 보안하기 위해 각 노드가 검정,빨간색을 가지며 균형 잡히게 만든 트리 입니다.
[중요한 특징]
1. 각 노드는 항상 검정,빨간색 중 한가지를 가집니다.
2. 루트 노드와 리프 노드는 항상 검정색입니다.
3. 검정의 자식들은 검정,빨강 전부 가능하지만, 빨강의 자식들은 검정만 가능합니다.
4. 루트노드에서 리프 노드까지 거치는 검정 노드의 수는 같습니다.
[삽입될 때 색 겹침 해결]
- 삽입된 숫자랑 그 부모 노드가 빨간색일때, 삼촌 노드의 색 확인 해서 해결 해야 합니다. 삼촌 노드가 검정색이면 Restructing , 빨간색이면 Recoloring 이용합니다.
1. Restructing (재구성)
- 삼촌 노드가 검정색일때 사용합니다. 삽입된 노드, 부모노드, 조부모노드를 오름 차순으로 재 정의 합니다. 그 후 가운데 숫자를 검정으로 두어 루트노드로 두고 나머지를 빨간색으로 칠해 줍니다. 전에 부모 였던 노드가 빨간 자식 노드가 됬으면 그 전 자식이였던 노드 더미들을 붙여주면 재구성 완성입니다.
2. Recoloring
- 삼촌 노드가 빨간색일때 사용합니다. 부모, 삼촌을 전부 검정색으로 만들고 조부모를 빨간색으로 바꿉니다. 그럼 조부모의 부모랑 색이 겹칠 수도 있으니 계속해서 진행 하여 줍니다. 그러다 부모 노드의 조부모 노드가 루트 노드이면 빨간색에서 다시 검정색으로 바꿔주면 젤 위가 검,검 부터 시작됨으로 균형이 맞춰집니다.
[이진 탐색 트리를 이용하는 AVL 트리와 차이점]- 삽입 삭제시 redblack-tree보다 AVL 트리가 균형 맞추기 위한 작업 횟수가 많아서 더 느립니다. 조회시에는 AVL트리가 더 빠릅니다.- 각 노드 색을 칠하는데 1bit만 필요하지만, AVL트리는 높이를 노드에 저장하기에 integer이 노드마다 들어있습니다.
4. std::map과 std::unorderedmap의 차이를 설명해 보세요.
std::map과 std::unordered_map은 모두 C++에서 키-값(key-value) 쌍을 저장하고 관리하는 컨테이너입니다. 하지만 내부 구현 방식과 동작 방식이 다르며, 이에 따라 성능과 용도에서도 차이가 있습니다.
1. 주요 차이점
| std::map | std::unordered_map | |
| 내부 구조 | 균형 이진 탐색 트리 (레드-블랙 트리) | 해시 테이블 |
| 원소 정렬 | 자동 정렬 (오름차순/사용자 정의 정렬 가능) | 정렬되지 않음 |
| 탐색 시간 복잡도 | O(log n) | 평균 O(1), 최악 O(n) |
| 삽입 시간 복잡도 | O(log n) | 평균 O(1), 최악 O(n) |
| 메모리 사용량 | 상대적으로 적음 | 더 많음 (해시 충돌 관리 추가 메모리 필요) |
| 중복 키 허용 여부 | 허용하지 않음 | 허용하지 않음 |
| 정렬된 순회 | 지원 | 지원하지 않음 |
- 해시 테이블인 unordered_map은 키에 대한 해시 함수를 호출하여 얻습니다. 정렬된 순서대로 저장되지 않으며, 삽입과 탐색이 O(1)으로 수행 됩니다. 서로 다른 데이터가 같은 해시 값을 반환 할 수도 있어서 충돌 가능성이 존재합니다.
- map은 키를 기준으로 만든 red-black tree에 키와 값이 저장됩니다. O(logN)으로 삽입,검색이 이루어지며 충돌 위험이 없습니다.
5. 해시 테이블 충돌 발생 해결법을 설명해 보세요.
1. 체이닝
- 해시 테이블 특정 위치에 값을 여러개 저장 할 수 있는 연결리스트를 만드는 기법입니다. 벡터 대신 연결리스트 사용 이유는 삭제를 빠르게 하기 위함 입니다
2. 열린 주소(open addressing) 지정
- 체이닝처럼 연결 리스트를 사용하지 않고, 모든 원소를 해시 테이블에 넣는것 입니다. 탐색 알고리즘을 사용해서 비어있는 주소 값을 찾아서 거기에 값을 넣습니다.
(1) 선형탐색 : 선택한 주소값에 값이 있으면 그 다음 주소값을 탐색하며 비어있는 주소값을 찾는 방법
(2) 이차함수 탐색 : hash(key + (i++)^2) 이렇게 이차함수 값을 더한 테이블에 값을 넣습니다.