c++39 [C++] 스레드(thread) & 뮤텍스(mutex) 스레드 ? 스레드는 프로세스 내에서 실행되는 작은 실행 단위 이며 한 프로세스는 여러개의 스레드를 가지고 있을 수 있습니다. 스레드는 독립적인 실행 경로를 가지고 프로세스 내의 자원을 공유합니다. 이런 특성으로 인해 프로세스의 실행 속도와 효율성을 향상 시킬 수 있습니다. 여러 작업들을 한번에 실행(병행)할 수 있으나 서로 다른 스레드 간의 동기화와 조율이 필요하게 됩니다. 동기화에 필요한 것이 뮤텍스 입니다. 뮤텍스 ? 뮤텍스는 상호 배제(Mutual Exclusion)를 의미하며 공유 자원에 대하여 동시 엑세스를 조절합니다. *임계 구역(Critical Section)에 들어가는 스레드가 지원을 독점할 수 있도록 허용하며 다른 스레드는 임계 구역에 진입할 수 없도록 제어하는 기능을 합니다.(임계 구역.. 2023. 8. 11. [C++/자료구조] 우선순위 큐(Priority Queue) 우선순위 큐 ? C++의 표준 라이브러리(Library)에서 제공되는 priority_queue 는 우선순위 큐 자료구조를 구현한 클래스 입니다. 우선순위 큐는 데이터를 삽입과 동시에 자동으로 정렬이되고 정해진 기준에서 가장 높은 우선순위를 가진 요소가 항상 상단에 위치하도록 유지 합니다. priority_queue 를 사용하기 위해서는 헤더 파일의 선언이 필요합니다. 1. 우선순위 큐의 기본 동작 및 특성 1. 정렬 순서는 기본 내림 차순으로 가장 큰 값이 상단에 위치합니다. 2. 요소의 삽입, 삭제가 이루어 질때마다 자동으로 정렬을 실행합니다. 3. 힙(heap) 자료구조를 기반으로 구현되어 효율적으로 작동합니다. *힙(heap) 자료구조 복습하기(아래 접은글) 더보기 힙(heap) 힙은 특정한 규칙.. 2023. 8. 9. [알고리즘] 이진 탐색(Binary Search) 이진 탐색(Binary Search) 정렬된 배열에서 특정 값을 찾는 알고리즘입니다.(필수조건!) 특징 반복 또는 재귀적 구현: 이진 탐색은 반복문이나 재귀 함수를 사용하여 구현할 수 있습니다. 정렬된 배열에서 사용: 이진 탐색은 정렬된 배열에서만 사용할 수 있습니다. 배열의 중간 값을 기준으로 탐색 범위를 좁혀가며 값을 찾습니다. 시간 복잡도: 이진 탐색의 시간 복잡도는 O(log n)입니다. 배열을 반으로 분할하면서 탐색 범위를 절반으로 줄여나가기 때문에 탐색 시간이 로그 시간에 비례합니다. 알고리즘 동작 방식 탐색 범위의 시작 인덱스와 끝 인덱스를 설정합니다. 탐색 범위의 중간 인덱스를 찾습니다. 중간 값과 찾고자 하는 값을 비교합니다. 중간 값이 찾고자 하는 값과 일치하면 탐색 성공입니다. 중간 .. 2023. 7. 16. [알고리즘] 병합 정렬(Merge Sort) 병합 정렬(Merge Sort) 특징 안정 정렬(Stable Sort): 동일한 값에 대해 상대적인 순서가 유지됩니다. 즉, 동일한 값의 원소들은 입력 배열에서의 순서와 동일한 순서로 정렬됩니다. 분할 정복(Divide and Conquer): 큰 문제를 작은 문제로 분할하여 해결하는 방식을 사용합니다. 추가적인 메모리 사용: 임시 배열을 사용하여 원소들을 병합하는 과정에서 추가적인 메모리가 필요합니다. 평균적으로 빠른 속도: 평균 시간 복잡도가 O(n log n)으로 매우 효율적입니다. 비교 기반 정렬(Comparison Sort): 원소들의 상대적인 크기를 비교하여 정렬합니다. 알고리즘 동작 방식 주어진 배열을 반으로 분할합니다. 분할된 부분 배열에 대해 재귀적으로 병합 정렬을 수행합니다. 분할된 부.. 2023. 7. 16. [알고리즘] 퀵 정렬(Quick Sort) 퀵 정렬(Quick Sort) 특징 불안정 정렬(Unstable Sort): 동일한 값에 대해 상대적인 순서가 유지되지 않을 수 있습니다. 제자리 정렬(In-place Sort): 입력 배열 내에서 정렬이 수행되며, 추가적인 메모리를 사용하지 않습니다. 분할 정복(Divide and Conquer): 큰 문제를 작은 문제로 분할하여 해결하는 방식을 사용합니다. 평균적으로 빠른 속도: 평균적으로 O(n log n)의 시간 복잡도를 가지므로 대부분의 경우에 빠른 속도를 보입니다. 재귀적 구현: 주로 재귀 함수를 통해 구현되며, 스택의 호출로 인해 추가적인 메모리를 사용할 수 있습니다. 알고리즘 동작 방식 배열에서 하나의 원소를 피벗(Pivot)으로 선택합니다. 피벗을 기준으로 작은 값은 피벗의 왼쪽에, 큰 .. 2023. 7. 16. [알고리즘] 버블 정렬(Bubble Sort) 버블 정렬(Bubble Sort) 특징 안정 정렬(Stable Sort): 동일한 값에 대해 상대적인 순서가 유지됩니다. 즉, 동일한 값의 원소들은 입력 배열에서의 순서와 동일한 순서로 정렬됩니다. 제자리 정렬(In-place Sort): 입력 배열 이외에 추가적인 메모리를 사용하지 않습니다. 입력 배열 내에서 정렬이 수행됩니다. 비교 기반 정렬(Comparison Sort): 원소들의 상대적인 크기를 비교하여 정렬합니다. 알고리즘 동작 방식 버블 정렬은 인접한 원소들을 비교하고 필요에 따라 위치를 교환하는 과정을 반복하여 전체 배열이 정렬될 때까지 진행합니다. 첫 번째 원소부터 인접한 원소와 비교합니다. 인접한 두 원소의 순서가 잘못되어 있다면, 두 원소의 위치를 교환합니다. 배열의 끝까지 위의 과정을.. 2023. 7. 16. 이전 1 2 3 4 5 ··· 7 다음
