nomad-programmer

힙 정렬은 힙의 다음 특성을 활용하여 정렬하는 알고리즘이다. 힙의 루트 노드에 저장된 값이 가장 커야 한다. 이는 '최대 힙(max heap)'의 특징이다. 이것을 다음과 같은 특징을 갖도록 힙을 구성할 수도 있다. 힙의 루트 노드에 저장된 값이 정렬순서상 가장 앞선다. 2021/03/07 - [Programming/Algorithm] - [Programming/Algorithm] 우선순위 큐와 Heap 자료구조 [Programming/Algorithm] 우선순위 큐와 Heap 자료구조 Queue의 핵심 연산 두 가지는 다음과 같다. enqueue : 큐에 데이터를 삽입하는 행위 dequeue : 큐에서 데이터를 꺼내는 행위 이와 마찬가지로 '우선순위 큐'의 핵심 연산 두가지도 다음과 같다. enqueu..

삽입 정렬은 보는 관점에 따라서 별도의 메모리를 필요로 하지 않는 '개선된 선택 정렬'과 유사하다고 느낄 수 있다. 하지만 전혀 다른 방법으로 정렬을 이뤄나간다. 삽입 정렬은 정렬 대상을 두 부분으로 나눠서, 정렬 안 된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에 '삽입'해 가면서 정렬을 진행하는 알고리즘이다. 정렬된 상태로 삽입하기 위해서는 특정 위치를 비워야 하고, 비우기 위해서는 데이터들을 한 칸씩 뒤로 미는 연산을 수행해야 한다. 정렬이 완료된 영역의 다음에 위치한 데이터가 그 다음 정렬 대상이다. 삽입할 위치를 발견하고 데이터를 한 칸씩 뒤로 밀수도 있지만, 데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾을 수도 있다. 삽입위치를 찾는 과정과 삽입을 위한 공간마련의 과정을 구분할 필요가 ..

선택 정렬은 버블 정렬보다도 쉽고 간단한 알고리즘이다. 선택 정렬은 정렬순서에 맞게 하나씩 선택해서 옮기는, 옮기면서 정렬이 되게 하는 알고리즘이다. 정렬순서상 가장 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고, 원래 그 자리에 있던 데이터는 빈 자리에 가져다 놓는다. #include using std::cout; using std::cin; using std::endl; void SelSort(int arr[], int n) { int maxIdx; int temp; for (int i = 0; i < n - 1; i++) { maxIdx = i; // 최솟값 탐색 for (int j = i + 1; j < n; j++) { if (arr[j] < arr[maxIdx]) { maxIdx = j; } ..

버블 정렬은 정렬의 대명사로 알려져 있는 정렬 방법이다. 그만큼 이해하기도 구현하기도 쉽다. 물론 이해와 구현이 쉬운 만큼 성능에는 아쉬움이 있따. 버블 정렬은 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다. 두 데이터를 비교하여, 정렬 순서상 위치가 바뀌어야 하는 경우에 두 데이터의 위치를 바꿔나간다. 버블이란 이름이 붙은 이유도 앞에서부터 순서대로 비교하고 교환하는 일련의 과정이 거품이 일어나는 모습에 비유되어 버블 정렬이라 이름 지어진 것이다. #include #define SWAP(a, b) { a ^= b; b ^= a; a ^= b; } using std::cout; using std::cin; using std::endl; int main() { int arr[] = { 5,..

Queue의 핵심 연산 두 가지는 다음과 같다. enqueue : 큐에 데이터를 삽입하는 행위 dequeue : 큐에서 데이터를 꺼내는 행위 이와 마찬가지로 '우선순위 큐'의 핵심 연산 두가지도 다음과 같다. enqueue : 우선순위 큐에 데이터를 삽입하는 행위 dequeue : 우선순위 큐에서 데이터를 꺼내는 행위 반면 연산의 결과에는 차이가 있다. 큐는 연산의 결과로 먼저 들어간 데이터가 먼저 나오지만, 우선순위 큐의 연산결과는 다음과 같다. 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. 우선순위 큐를 구현하는 방법은 다음과 같이 세 가지로 구분할 수 있다. 배열을 기반으로 구현하는 방법 연결 리스트를 기반으로 구현하는 방법 힙(heap)을 이용하는 방법 힙(Heap)이란? 힙은 '..

클라이언트에서 서버로 현재 시간을 알려달라는 명령을 요청하면 서버에서 이를 처리하여 서버의 현재 시간을 클라이언트에게 보내주는 간단한 타임서버이다. 타임서버의 존재는 모든 클라이언트의 로컬 시간이 각기 다를 수 있는 문제점이 잠재적으로 있을 수 있기에 타임 서버를 둠으로써 모든 클라이언트의 시간을 동일하게 맞출 때 존재 의미가 있다. Server 구현 #include #include #include #include #include #pragma comment(lib, "ws2_32.lib") #define PORT 3333 #define BUF_SIZE 100 int main(int argc, char* argv[]) { WSADATA wsaData; SOCKET servSock; SOCKADDR_IN ..

알고리즘 중에 분할 정복 알고리즘(Divide and Conquer Algorithm)이 있다. 어려운 문제를 작게 쪼개서(divide) 해결해 나가는(conquer) 것을 말한다. 대표적인 분할 정복 알고리즘인 퀵 정렬에 대해 알아보자. pivot은 정렬되지 않은 리스트에서 가운데 위치한 인덱스의 데이터를 말한다. 주의할 점은 인덱스가 아니라 데이터라는 것이다. start는 첫 번째 인덱스이고 end는 미자막 인덱스이다. left와 right는 각각 start와 end를 가리킨다. left 인덱스는 오른쪽으로 이동하고 right 인덱스는 왼쪽으로 이동한다. 목적은 pivot을 기준으로 왼쪽은 pivot보다 작은 데이터가 모이고, 오른쪽은 큰 데이터가 모이도록 만드는 것이다. 그렇게 하려면 left는 오..

이진 탐색 알고리즘을 요약하면 다음과 같다 리스트의 모든 데이터는 정렬된 상태여야 한다. 첫 번째 인덱스를 start로 설정하고 마지막 인덱스를 end로 설정한다. 가운데 인덱스를 mid로 설정하고 mid 데이터와 target 데이터를 비교한다. target 데이터와 mid 데이터가 같다면 mid를 반환한다. target 데이터가 작다면 end를 mid-1로 한다. target 데이터가 크면 start를 mid+1로 한다. 데이터를 찾거나 start와 end가 교차하기 전까지 계속 진행한다. 데이터를 찾지 못했다면 -1 혹은 None을 반환한다. 이진 탐색 알고리즘을 적용하려면 반드시 데이터가 정렬된 상태여야 한다. 이미 정렬이 상태이므로 target이 mid의 데이터보다 작다는 것은 mid 이후 데이터..

이진 탐색 트리의 특징 이진 탐색 트리는 두 가지 중요한 특징이 있다. 첫째, 어떤 특정 노드를 선택했을 때 그 노드를 기준으로 왼쪽 서브 트리에 존재하는 노드의 모든 데이터는 기준 노드의 값보다 작고, 오른쪽 서브 트리에 있는 노드의 모든 데이터는 기준 노드의 값보다 크다는 것이다. 루트 노드를 기준으로 왼쪽 서브 트리의 모든 데이터는 루트 노드의 데이터인 6보다 작다. 오른쪽 서브 트리의 모든 데이터는 6보다 크다. 위의 그림에서 루트 노드의 왼쪽 자식 노드가 기준 노드일 때, 기준 노드의 왼쪽 서브 트리의 모든 데이터는 기준 노드의 데이터인 3보다 작다. 오른쪽 서브 트리의 모든 데이터는 3보다 크다. 기준 노드가 루트 노드의 오른쪽 자식 노드일 때도 같은 조건이 성립한다. 즉, 특정 노드를 기준으..

Python으로 만드는 이진 트리 알고리즘 class TreeNode: def __init__(self): self.__data = None self.__left = None self.__right = None def __del__(self): print('TreeNode of {} is deleted'.format(self.data)) @property def data(self): return self.__data @data.setter def data(self, data): self.__data = data @property def left(self): return self.__left @left.setter def left(self, left): self.__left = left @property ..

프로그램은 하드디스크에 저장된 실행 파일을 말한다. 프로세스는 프로그램을 실행한 상태 즉, 하드디스크에서 메인 메모리로 코드와 데이터를 가져와 현 재 실행되고 있는 상태를 말한다. 프로세스는 동시에 여러 개가 존재할 수 있다. 프로세스 상태 오늘날의 운영체제는 대부분 멀티프로세스 기반이다. 프로세스 여러 개를 동시에 실행할 수 있다. 프로세스를 실행하려면 독자적인 메모리 공간과 CPU가 필요하다. CPU는 한 번에 하나의 프로세스에만 할당할 수 있다. 여러 프로세스가 완벽하게 '동시에' 실행되는 건 불가능하다. 즉, 프로세스는 프로그램을 실행하는 순간부터 창을 닫을 때까지 계속해서 실행 상태로 있는 것이 아니다. 프로세스 상태는 상황에 따라 변한다. 총 다섯 가지 상태가 있다. 1. 생성(Created)..

클래스 메서드(class method)와 정적 메서드(static method)가 어떻게 다른지 예제를 보며 살펴보자. class MethodClass: @staticmethod def static_method(): print('static method') @classmethod def class_method(cls): print(cls.__name__) if __name__ == '__main__': stc_mtd = MethodClass() stc_mtd.static_method() stc_mtd.class_method() """ 결과 static method MethodClass """ static_method() 함수는 정적 메서드이다. 정적 메서드는 인자로 클래스나 객체를 받지 않는다. 함수의 ..

C++에서는 C스타일의 형 변환 연산자를 가리켜 '오래된 C스타일 형 변환 연산자(Old C-style cast operator)'라 부르기도 한다. 이렇듯 C스타일의 형 변환 연산자는 C언어와의 호환성을 위해서 존재할 뿐, C++에서는 새로운 형 변환 연산자와 규칙을 제공하고 있다. #include #pragma warning(disable: 4996) using std::cout; using std::cin; using std::endl; class Car { private: int fuelGauge; public: Car(int fuel) : fuelGauge(fuel) {} void ShowCarState() const { cout

함수 템플릿과 static 지역 변수 template void ShowStaticValue(void) { static T num = 0; num += 1; cout

템플릿을 정의할 때 결정되지 않은 자료형을 의미하는 용도로 사용되는 T 또는 T1, T2와 같은 문자를 가리켜 '템플릿 매개변수' 라 한다. 그리고 템플릿 매개변수에 전달되는 자료형 정보를 가리켜 '템플릿 인자' 라 한다. 템플릿 매개변수에는 변수의 선언이 올 수 있다. template class SimpleArray { private: T arr[len]; public: T& operator[] (int idx) { return arr[idx]; } }; 이렇듯 템플릿 매개변수에도 변수가 올 수 있다. 그리고 이를 기반으로 다음의 형태로 객체생성이 가능하다. SimpleArray i5arr; SimpleArray d7arr; 위의 두 문장에서 템플릿 매개변수 len에 전달된 인자 5와 7은 해당 템플릿..

클래스 템플릿의 특수화 방법 및 개념은 함수 템플릿과 매우 유사하다. 클래스 템플릿 특수화 함수 템플릿을 특수화하는 이유는 특정 자료형에 대해서 구분이 되는 다른 행동을 보이기 위해서다. 마찬가지로 클래스 템플릿을 특수화하는 이유는 특정 자료형을 기반으로 생생도니 객체에 대해, 구분이 되는 다른 행동양식을 적용하기 위해서이다. 즉, 클래스 템플릿을 특수화하면, 템플릿을 구성하는 멤버함수의 일부 또는 전부를 다르게 행동하도록 정의할 수 있다. 클래스 템플릿을 특수화하는 방법은 다음과 같다. 먼저 다음과 같이 정의된 클래스 템플릿이 존재할 때, template class SoSimple { public: T SimpleFunc(T num) { ... } } 이를 기반으로 자료형 int에 대해 특수화 한 템플..

클래스 템플릿의 정의방법은 함수 템플릿의 정의방법과 동일하다. #include #pragma warning(disable: 4996) using std::cout; using std::cin; using std::endl; template class Point { private: T xpos, ypos; public: explicit Point(const T x = 0, const T y = 0) : xpos(x), ypos(y) {} void ShowPosition() const { cout

함수 템플릿과 템플릿 함수 다음의 정의를 가리켜 '함수 템플릿(Function Template)' 이라 한다. template T Add(T num1, T num2) { return num1 + num2; } 반면 위의 템플릿을 기반으로 컴파일러가 만들어 내는 다음 유형의 함수들을 가리켜 '템플릿 함수(Template Function)' 이라 한다. int Add(int a, int b) { return num1 + num2; } double Add(double num1, double num2) { return num1 + num2; } 템플릿 함수의 표시에서 와 은 일반함수가 아닌, 컴파일러가 만들어낸 템플릿 기반의 함수임을 표시한 것이다. 함수 템플릿 함수를 만드는데 사용되는 템플릿 템플릿 함수 템플..

C++ 표준 라이브러리에는 string이라는 이름의 클래스가 정의되어 있다. 해당 클래스는 문자열의 처리를 목적으로 정의된 클래스이며, 이 클래스의 사용을 위해서는 헤더파일 을 포함해야 한다. #include #include usging namespace std; int main(void) { string str1 = "C++ "; string str2 = "Language Love"; string str3 = str1 + str2; cout

C++에서는 객체간의 대입연산을 허용한다. 당연하게도 두 객체의 자료형이 일치할 때에만 대입연산이 가능하다. #include #pragma warning(disable: 4996) using std::cout; using std::cin; using std::endl; class Number { private: int num; public: Number(int n = 0) : num(n) { cout