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; } ..