IT

이 포스터에선 소수 구하기에 대해 알아보겠다. Naive한 방식과 에라토스테네스의 체 방식을 코드로 살펴보도록하자. 먼저, 소수(Prime Number)란 무엇인가? 양의 양수가 1 혹은 자기 자신 밖에 없는 1보다 큰 자연수를 의미한다. 예를 들어, 8의 약수는 1, 2, 4, 8이기 때문에 소수가 아니다. 7의 약수는 1, 7이기 때문에 소수이다. Naive 방식 코드 bool is_prime_number(int n) { if (n N; // 초기화 for (int i = 2; i

원리 머지 정렬(Merge Search)의 정렬 원리는 다음과 같다. 머지 정렬은 퀵 정렬과 마찬가지로 Divide and Conquer 방식을 사용한다. 따라서 재귀 함수를 사용하며, 종료 구문이 필요하다. 시간 복잡도는 O(n * Log n)에 해당한다. 새로운 메모리를 할당해야 한다는 단점이 있다. 하지만 Instructions 처리 과정에서 원본 메모리 값은 유지된다는 점에서 Stable Sort 기법으로 분류된다. C++ algorithm 헤더 파일의 stable_sort 함수가 머지 정렬을 사용한다. 코드 #include #include #define VEC_SIZE 10 using namespace std; /* 아이디어 1. 배열을 절반으로 나누기 (크기가 1 이하가 되면 멈추기) 2. 쪼..

원리 퀵 정렬 (Quick Sort) 정렬 원리는 다음과 같다. 퀵 정렬은 Divide and Conquer 방식을 사용한다. 따라서 재귀 함수를 사용하며, 종료 구문이 필요하다. 시간 복잡도는 O(n * Log n)에 해당한다. 효율적인 정렬 방법으로, 현재 가장 많이 사용하는 방식이다. 동일 메모리 값이 실시간으로 처리되는 점에서 Unstable Sort 기법으로 분류된다. C++ algorithm 헤더 파일의 sort 함수가 퀵 정렬을 사용한다. 코드 #include #include using namespace std; void swap(int& a, int& b) { int temp = a; a = b; b = temp; } void quick_sort(vector& arr, int s, int ..

원리 버블 정렬(Bubble Search)는 직관적인 알고리즘이다. 정렬 원리는 다음과 같다. 버블 정렬은 선택 정렬과 동일하게 이중 반복문을 통해 완전 탐색을 수행한다. 따라서 시간 복잡도는 O(n^2)에 해당한다. (선택 정렬과 차이점은 Swap 횟수로, 버블 정렬이 좀 더 Swap이 자주 일어남) 비효율적인 정렬 방법으로, 작은 크기일 때 사용한다. 코드 #include #include using namespace std; void swap(int& a, int& b) { int temp = a; a = b; b = temp; } void bubble_sort(vector& arr) { int min_idx; for (int i = 0; i < arr.size(); i++) { min_idx = i..

원리 선택 정렬(Selection Sort)는 직관적인 알고리즘이다. 정렬 원리는 다음과 같다. 선택 정렬은 이중 반복문을 통해 완전 탐색을 수행한다. 따라서 시간 복잡도는 O(n^2)에 해당한다. 비효율적인 정렬 방법으로, 작은 크기일 때 사용한다. 코드 #include #include using namespace std; void selection_sort(vector& arr) { for (int i = 0; i arr[j]) min_idx = j; int temp = arr[i]; arr[i] = arr[min_idx]; a..

1. string (#include ) string: 문자열을 효율적으로 처리해주기 위한 class이다. 2. string 초기화 int main(void) { string s = "Alice"; string s1("Bee"); // s1 = Bee string s2(s); // s2 = Alice string s3(4, '0'); // s3 = 0000 string s4(s, 0, s.length() - 2); // s4 = Ali string s5("12345", 3); // s5 = 123 return 0; } 3. string 참조 방법 int main(void) { string s = "Alice"; cout

1. map (#include ) map의 특징 노드는 pair 형태를 가진다. 중복 제거 노드 기반으로 index 접근 불가 Red-Black 트리 기반의 균형 이진 트리 Search: O(log n) Insert: O(log n) Delete: O(log n) 장점 삽입, 삭제, 검색과 같은 기본 작업 속도가 빠르다. 균형 이진 트리를 유지하는 방식이 Red-Black 트리 기반이기 때문에 오버헤드가 크진 않다. 단점 Red-Black 트리의 노드 색상을 저장하기 위해 각 노드마다 1 bit의 추가 저장 공간이 요구된다. multimap은 중복 허용인 map이라고 생각하면 된다. unordered_map은 정렬이 아닌 map이라고 생각하면 된다. unordered_multimap은 정렬이 아닌 mul..

1. set (#include ) set의 특징 중복 제거 노드 기반으로 index 접근 불가 Red-Black 트리 기반의 균형 이진 트리 Search: O(log n) Insert: O(log n) Delete: O(log n) 장점 삽입, 삭제, 검색과 같은 기본 작업 속도가 빠르다. 균형 이진 트리를 유지하는 방식이 Red-Black 트리 기반이기 때문에 오버헤드가 크진 않다. 단점 Red-Black 트리의 노드 색상을 저장하기 위해 각 노드마다 1 bit의 추가 저장 공간이 요구된다. multiset은 중복 허용인 set이라고 생각하면 된다. unordered_set은 정렬이 아닌 set이라고 생각하면 된다. unordered_multiset은 정렬이 아닌 multiset이라고 생각하면 된다. ..

1. Linked List (#include ) 정의: 노드들이 메모리 상에 퍼져서 분포하며, 각 노드에는 Data와 다음 노드를 가리키는 Link로 이루어진 자료구조이다. Index 접근이 불가능하다. (C++ STL List: Double Linked List) Search: O(n) Insert: O(1) Delete: Search + O(1) 장점: 삽입이 빠르다. 단점: 선형 탐색을 사용하여 탐색이 느리다. link pointer에 대한 추가 메모리가 발생한다. 2. Vector (#include ) 정의: 크기가 변하는 동적 배열 자료구조이다. 배열의 크기가 기존보다 커지면 원래 크기의 2배씩 늘린다. 이때, 배열을 복사하여 다른 메모리에 저장하여 배열의 크기를 증가시킨다. (Dynamic A..