Study
-
[자료구조] C++ HashTable 구현Study/자료구조,알고리즘 2022. 11. 11. 16:16
#pragma once #include #include class HashNode { private: std::string m_Key; int m_Value; HashNode* m_Next; public: HashNode() : m_Next(nullptr) { } HashNode(const std::string& key, int val) : m_Key(key), m_Value(val), m_Next(nullptr) { } HashNode* GetNext() { return m_Next; } void SetNext(HashNode* node) { m_Next = node; } const std::string& GetKey() const { return m_Key; } int GetValue() const ..
-
[알고리즘] 병합 정렬 (Merge Sort)Study/자료구조,알고리즘 2022. 11. 4. 18:21
01. 병합 정렬의 개념 안정 정렬이다. 정렬을 위한 별도의 공간이 필요하다. 분할 정복 알고리즘이다. 주로 순환 호출로 구현 매우 빠른 속도를 보장 ( O(NlogN) ) 02. 과정 설명 배열을 반으로 나누는 것을 반복한다. 사이즈 1짜리 배열까지 나누고 나면, 나눈 순서의 역순으로 정렬해가며 부분 배열을 합친다. 말로는 사실 설명할 게 별로 없다... 그림으로 보는 게 더 설명이 쉬울 듯 하여 첨부 03. C++ 코드 void Merge(int*& arr, int*& tmp, int left, int right) { if (left == right) return; int l = left; int mid = (l + right) / 2; int midIdx = mid + 1; int idx = l; ..
-
꼬리 재귀 (Tail Recursion)Study/자료구조,알고리즘 2022. 11. 3. 17:19
1. 꼬리 재귀 재귀 호출이 끝나면 아무것도 하지 않고 리턴하는 방법 컴파일러 최적화에 의해 재귀 호출이 깊어져도 스택 프레임이 쌓이지 않고 재사용하기 때문에 빨라진다. 2. 예시 int Factorial(int n) { if (n == 1) return 1; return n * Factorial(n - 1); } int FactorialTail(int n, int acc = 1) { if (n == 1) return acc; return FactorialTail(n - 1, n * acc); } 팩토리얼을 구하는 함수를 재귀방식, 꼬리 재귀 방식으로 작성해 보았다. 위 함수는 return statement에서 n * Factorial(n-1) 에 의해 재귀 호출을 빠져나가는 과정에서 * 연산을 해 주어..
-
[알고리즘] 퀵 정렬 (Quick Sort)Study/자료구조,알고리즘 2022. 11. 3. 12:35
01. 퀵 정렬의 개념 불안정 정렬이며, 다른 원소와의 비교를 통해 정렬하는 비교 정렬 분할 정복 알고리즘이다. 매우 빠른 속도를 보장 ( O(NlogN) ) 주로 순환 호출로 구현 02. 과정 설명 오름차순으로 정렬한다고 가정한다. 리스트 안에 있는 한 요소를 선택 (보통 맨 앞의 원소), 이를 Pivot이라고 한다. 피벗을 기준으로, 피벗보다 작은 요소들을 모드 왼쪽으로 옮기고 피벗보다 큰 요소를 오른쪽으로 옮긴다. 피벗을 제외한 왼쪽, 오른쪽 요소들을 각각 따로 정렬한다. 나눠진 부분들이 더 이상 분할이 불가능 할 떄까지 반복 03. 자세한 설명 배열에 [4, 6, 3, 2, 8, 7, 9, 1, 0, 5] 가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬한다. 초기 상태에서 pivot을 0번 ..
-
[알고리즘] 카운팅 정렬(Counting Sort)Study/자료구조,알고리즘 2022. 10. 21. 12:28
1. 특징 원소간 비교를 수행하지 않는 정렬이다. 모든 원소는 양의 정수여야 함 시간 복잡도는 O(n+k), k는 정렬할 배열의 최대값이다. 공간 복잡도는 O(n+k), 정렬을 위한 배열 하나, 카운팅을 위한 배열 하나가 필요하다. 2. 과정 입력 자료 input을 탐색하여 최대값 k를 구한다. k + 1 사이즈의 배열 counts를 생성한다. input을 순회하며, 등장하는 수의 빈도를 기록한다.. (input의 원소가 3이라면, counts[3]에 +1) 0이 1번, 2가 5번 등장하는 배열이라면, counts배열은 [1, 0, 0, 5]가 될 것 input을 순회하며 누적합을 구한다. 오름차순 정렬의 경우, 이전 값 (i-1)을 i에 더한다. 내림차순 정렬의 경우, input의 뒤쪽부터 시작해서, ..
-
[알고리즘] Bubble Sort와 Selection Sort 시간 비교Study/자료구조,알고리즘 2022. 10. 20. 13:25
Bubble Sort와 Insertion Sort를 구현, 시간을 비교해봤다. Bubble Sort void BubbleSort(const vector& input) { cout out[j - 1]) { swap(out[j], out[j - 1]); } } } chrono::duration sec = chrono::system_clock::now() - start; for_each(out.begin(), out.end(), print_vec); cout
-
[C++] stringstream을 while문의 조건으로 사용할 때 주의할 점Study/C & C++ 2022. 10. 13. 14:13
코딩 테스트 문제를 풀다 보면 stringstream으로 값을 추출할 때가 많다. 공백이나 특정 문자 기준으로 잘라내기 위해 while문과 stringstream 객체를 조합하여 사용할 경우가 많다. stringstream객체를 while문의 조건으로 사용할 때, 주의하지 않으면 분명 다 읽었는데 반복을 한 번 더 돌거나 하는 문제가 생길 수 있다. 아래 코드는 공백으로 구분된 문자열을 받아, 공백을 지우고 출력하는 코드이다. #include #include #include using namespace std; int main() { string input; getline(cin, input); // 개행문자 전까지 한 줄 읽음 stringstream ss(input); string buf; while ..
-
[운영체제] 가상 메모리(Virtual Memory)와 페이징, 세그멘테이션Study/컴퓨터 구조 & 운영체제 2022. 10. 11. 18:27
메모리란? 메모리는 프로세스 실행에 필요한 데이터 및 코드를 저장하는 장치 메모리는 크게 내부 기억장치인 주 기억장치, 외부 기억장치인 보조 기억장치로 나눈다. 내부 기억장치는 보통 CPU의 Cache, Register, 또는 RAM이다. 보조 기억장치는 HDD, SDD이다. 내부 기억장치의 읽기/쓰기 속도가 보조 기억장치보다 훨씬 빠름 당연히 내부 기억장치에서 모든 것을 처리하면 좋겠지만, 내부 기억장치는 용량이 작고 휘발성이므로 보조 기억장치를 사용한다. 가상 메모리 가상 메모리는 왜 쓰는가? 실제 메모리 크기보다 요구 메모리가 큰 프로그램(프로세스)를 실행하기 위해서 보통 사용하는 RAM의 전체 용량은 16GB정도가 보통이다. 그런데 용량이 50GB나 되는 게임들을 어떻게 실행할 수 있을까? -> ..