nomad-programmer

단위 테스트(unittest) 파이썬에서는 PyUnit이라고도 불리는 unittest 모듈이 있다. 이 모듈은 일반적으로 어던 모듈이나 함수를 작성할 때 정상 동작 여부를 테스트하는 과정을 거치게된다. 이러한 테스트케이스들은 한 번 사용하고 버리는 경우가 대부분이다. 하지만 다음에 코드가 수정되어도 기존에 작성한 테스트들을 수행할 수 있다면 더욱 편리하겠다. 이러한 기능을 제공해주는 라이브러리가 바로 unittest 이다. TestCase 기본적으로 unittest 모듈은 다음과 같이 간단하게 사용할 수 있다. # _*_ coding: utf-8 _*_ import unittest def sum(a, b): return a + b class Module1Test(unittest.TestCase): def..

Udemy에 접속하여 강의를 시청한다. 그런데 그 강의가 영어로된 강의라면 조금 답답할 수 있다. 이럴 때 이래와 같은 방법으로 영어 자막을 한글 자막으로 실시간 번역하여 시청할 수 있다. 대본에서 마우스 우측 클릭하여 "한국어로 번역"을 클릭하면 위와 같이 한국어로 변역된 것을 볼 수 있다. 여기서 중요한 점은 마우스로 스크롤을 위 아래 움직여가며 한국어로 모두 "번역" 해야한다는 점이다. 관리자 도구 - Console 로 이동하여 아래의 코드를 붙여 넣기 후 "Enter"를 누른다. 결과값으로 숫자가 나올 것이다. 그러면 성공이다. if(typeof window.i!=='undefined'){clearInterval(window.i)} else{let lastText=''; function check..

이진 탐색 트리는 '탐색에 효율적인 자료구조'이다 그리고 '이진 트리'의 일종이다. 이진 트리의 구조를 보면, 트리는 탐색에 효율적이라는 사실을 쉽게 알 수 있다. 이진 트리에 저장된 데이터의 수가 10억 개 수준에 이른다 해도 트리의 높이는 30을 넘지 않기 때문이다. 그렇다면 이것이 탐색에 있어서 어떤 의미를 지니겠는가? 예를 들어 연결 리스트에 10억 개의 데이터가 저장되어 있다고 가정해보자. 그리고 찾는 데이터가 이 리스트의 정중앙에 위치한다는 정보를 얻었다고 가정해보자. 이는 분명 유용한 정보이다. 하지만 이러한 정보를 가지고 있음에도 불구하고 데이터에 이르기 위해서는 약 5억 개의 노드를 지나야 한다. 반면 이진 트리의 경우에는 위치를 알고 있다면, 즉 데이터에 이르는 길을 알고 있다면 루트 ..

탐색의 이해 탐색은 '데이터를 찾는 방법'이다. 탐색은 알고리즘보다 자료구조에 더 가까운 주제이다. 이유는 다음과 같다. "효율적인 탐색을 위해서는 '어떻게 찾을까'만을 고민해서는 안 된다. 그보다는 '효율적인 탐색을 위한 저장방법이 무엇일까'를 우선 고민해야 한다." 그런데 효율적인 탐색이 가능한 대표적인 저장방법은 '트리'이다. 때문에 탐색에 관한 이야기의 대부분은 트리의 연장선상에 놓여있다. 정렬도 탐색을 목적으로 하는 경우가 대부분일 만큼 탐색은 자료구조에서, 컴퓨터 공학에서 매우 중요한 위치를 차지하고 있다. 보간 탐색(Interpolation Search) 정렬되지 않은 대상을 기반으로 하는 탐색 : 순차 탐색 정렬된 대상을 기반으로 하는 탐색 : 이진 탐색 이 중에서 이진 탐색은 중앙에 위치..

레드 블랙 트리를 시뮬레이션할 수 있는 사이트이다. www.cs.usfca.edu/~galles/visualization/RedBlack.html Red/Black Tree Visualization www.cs.usfca.edu

입력 속도 비교 www.acmicpc.net/blog/view/56 입력 속도 비교 여러가지 언어와 입력 방법을 이용해서 시간이 얼마나 걸리는지 비교해 보았습니다. 방법: 첫째 줄에 정수의 개수 N (= 10,000,000), 둘째 줄부터 N개의 줄에 한 개의 자연수(10,000 이하)가 적힌 파일 www.acmicpc.net 출력 속도 비교 www.acmicpc.net/blog/view/57 출력 속도 비교 여러가지 언어와 출력 방법을 이용해서 시간이 얼마나 걸리는지 비교해 보았습니다. 방법: 총 N개의 줄에 1부터 10,000,000까지의 자연수를 한 줄에 하나씩 출력하는 시간을 측정. 10번 측정해서 평 www.acmicpc.net

기수 정렬은 정렬순서상 앞서고 뒤섬의 판단을 위한 비교연산을 하지 않는다. 비교연산은 정렬 알고리즘의 핵심이라 할 수 있다. 특히 두 데이터 간의 정렬순서상 우선순위를 판단하기 위한 비교연산은 핵심중의 핵심이다. 때문에 모든 정렬 알고리즘들은 이 연산을 포함하고 있다. 뿐만 아니라 알고리즘의 복잡도도 이 연산을 근거로 판단해왔다. 그런데 이런 유형의 비교연산을 하지 않고서도 정렬을 할 수 있는 것이 "기수 정렬"이다. 그리고 정렬 알고리즘의 이론상 성능의 한계는 O(nlog2n)으로 알려져 있는데, 기수 정렬은 이러한 한계를 넘어설 수 있는 유일한 알고리즘이다. 물론 이렇게 좋은 점만 있는 것은 아니다. 다른 알고리즘에는 없는 단점도 있다. 그것은 바로 '적용할 수 있는 범위가 제한적'이라는 것이다. 예..

병합 정렬과 마찬가지로 '분할 정복(divide and conquer)'에 근거하여 만들어진 정렬 방법이다. 실제로 퀵 정렬 역시 정렬 대상을 반씩 줄여나가는 과정을 포함한다. 퀵 정렬은 그 이름이 의미하듯이 평균적으로 매우 빠른 정렬의 속도를 보이는 알고리즘이다. 위 그림에서는 퀵 정렬의 대상이 되는 배열을 보이고 있다. left : 정렬대상의 가장 왼쪽 지점을 가리키는 이름 right : 정렬대상의 가장 오른쪽 지점을 가리키는 이름 피벗(pivot)의 사전적 의미는 다음과 같다. pivot : 중심점, 중심축의 의미 즉 피벗은 정렬을 진행하는데 필요한 일종의 '기준'이라 할 수 있따. 때문에 정렬의 진해을 위해서는 피벗이라는 것을 진행해야 한다. low : 피벗을 제외한 가장 왼쪽에 위치한 지점을 가..

병합 정렬은 '분할 정복(divide and conquer)'이라는 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법이다. 분할 정복이란, 말 그대로 복잡한 문제를 복잡하지 않은 문제로 '분할(divide)'하여 '정보(conquer)'하는 방법을 말한다. 단 분할해서 정복했으니 정복한 후에는 '결합(combine)'의 과정을 거쳐야 한다. 즉 다음 3단계를 거치도록 알고리즘을 디자인 하는 것이 분할 정복법이다. 1단계 분할(Divide) : 해결이 용이한 단계까지 문제를 분할해 나간다. 2단계 정복(Conquer) : 해결이 용이한 수준까지 분할된 문제를 해결한다. 3단계 결합(Combine) : 분할해서 해결한 결과를 결합하여 마무리한다. 이 방법을 근거로 어떻게 병합 정렬 알고리즘이 디자인되었을까..

힙 정렬은 힙의 다음 특성을 활용하여 정렬하는 알고리즘이다. 힙의 루트 노드에 저장된 값이 가장 커야 한다. 이는 '최대 힙(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)이란? 힙은 '..

Key Combinations for Switching Pairing Modes and Operation Modes Operation Key Combination LED Registering pairing information Fn + Q Fn + Control + 1 to 4 Blinks in blue (twice per second) Blinks in blue fast (four times per second) Deleting all of the pairing information Fn + Q Fn + Z + Delete Blinks in blue (twice per second) Blinks in orange -> Turned off (Power off) Deleting pairing informa..

클라이언트에서 서버로 현재 시간을 알려달라는 명령을 요청하면 서버에서 이를 처리하여 서버의 현재 시간을 클라이언트에게 보내주는 간단한 타임서버이다. 타임서버의 존재는 모든 클라이언트의 로컬 시간이 각기 다를 수 있는 문제점이 잠재적으로 있을 수 있기에 타임 서버를 둠으로써 모든 클라이언트의 시간을 동일하게 맞출 때 존재 의미가 있다. 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 ..