Twinparadox Factory

항상 고민하던 게 있다.비교 정렬의 하한이 nlogn이며 이보다 더 좋은 정렬 알고리즘은 없다는 이야기를 들었다.도대체 왜 그런 것인지, 어째서 그런 것인지에 대해서 잘 모르고 넘어갔다.주어진 문제에 대해서 시간 복잡도의 하한이라는 것은어떤 문제도 이 하한보다 빠르게 구할 수 없다는 것을 의미하는데,이 하한이 알고리즘에 대한 시간 복잡도가 아니라이 문제의 고유 특성으로 인해서 과거부터 지금까지, 혹은 미래에 만들어진어떤 효율적인 알고리즘이더라도 적어도 하한의 시간복잡도 만큼 걸린다는 것을 의미한다. n개의 숫자가 저장된 배열이 있다고 하자.여기서 최솟값을 찾는 문제의 하한은 최소한 n-1회의 비교가 필요하므로 n-1이다.이런 식으로 n개의 수를 비교 정렬할 때 필요한 최소 비교 횟수가 어떻게 되는지 생각..

기수 정렬은 흔히 알고 있는 비교 정렬들과는 조금 다른 정렬로 볼 수 있다.숫자를 부분적으로 비교하는 정렬이기 때문에,제한적인 범위 내(제한적인 크기 혹은 자릿수)에 있는 숫자들에 대해서 자릿수별 정렬을 시행하는 알고리즘으로,제한적인 상황 내에서는 어떤 비교 정렬 알고리즘에 비해서 속도가 월등하다는 장점을 가지고 있다.단점은 직전에 말했듯, 제한적인 상황에 유효하다는 것이다. 089, 035, 131, 907, 910이라는 숫자가 들어왔다고 하자.이들 입력에 대해서 각각의 자릿수(1의 자리, 10의 자리, 100의 자리)를 기준으로 정렬을 시행한다.이 때, 작은 단위의 자릿수부터 큰 단위의 자릿수로 정렬한다. 내림차순 정렬을 시행한다고 하자. input089070131907910 1의 자리 0899071..

기본적으로 3색이라 하면 RED, GREEN, BLUE의 빛의 삼원색을 말한다.옆쪽에 FND와 연결된 기판은 이것저것 시도하고 있는 것이 있어 빵판에 그대로 둔 상태고,좌측에 물려 있는 LED가 바로 3색 LED다. 2초마다 각 LED를 작동시키는데빨강, 초록, 파랑, 노랑, 보라, 청록, 흰색, 꺼짐 순으로 작동한다. 빛의 3원색은 잘 조합하면, 노랑, 청록, 자홍색을 나타낼 수 있는데노랑의 경우 빨강과 초록,자홍은 빨강과 파랑,청록은 초록과 파랑이며흰색은 3색 모두 켜지면 나타난다. 반복문을 사용해 각 LED 값을 조정해주면 무드등을 만들 수도 있다. 12345678910111213141516171819202122232425262728293031323334353637383940int redPin = ..

템플릿 이용해서 스택을 일반화해봤다. 클래스 활용도 연습을 해볼 겸, 템플릿 사용도 연습을 해볼 겸...다른 기능 없이 아주 일반적인 push, pop, 생성자만 구현했다.다음엔 리스트도 해볼 생각. #include using namespace std; template class Stack { int tos; T data[100]; public: Stack(); void push(T element); T pop(); }; template Stack::Stack() { tos = -1; } template void Stack::push(T element) { if (tos == 99) { cout

알고리즘 문제를 풀다보면, 새로운 값을 입력받을 때마다,임시적으로 사용했던 데이터들을 모두 갈아 엎고,메모리에 저장된 값을 특정한 값으로 일괄초기화를 해야 하는 경우가 생기는데,그럴 때마다 골치가 아팠는데 이럴 때 사용하기 좋은 메모리 조작 함수가 있다. memset, memcmp, memcpy, memmove는 string.h에 정의되어 있으며,memory.h에도 정의되어 있는데 이 때 memmove는 정의되어 있지 않으니,고민할 것 없이 string.h를 포함시키면 된다. 1. memset 함수 원형 1void * memset(void * ptr, int value, size_t num);cs 사용법memset(메모리 블럭 첫번째 주소, 문자(문자 하나), 메모리 블럭 크기(byte)) 활용자료형이 ..

Multiple Inheritance;다중상속 하나의 파생 클래스가 여러 클래스를 동시에 상속 받는 경우를 말하며,그 효용성에 비해 반대급부가 커서 사용하지 않는 편이며,C#, Java에서는 지원하지 않음. 여러 클래스를 상속받아 재사용과 효율을 높일 수 있겠지만,치명적인 문제를 가지고 있음 12345678910111213141516171819202122232425262728293031#include using namespace std;class BaseIO{public: int mode;};class In : public BaseIO{public: int readPos;};class Out : public BaseIO{public: int writePos;};class InOut : public In,..

RTTI(Run-Time Type Information)실행 중 객체의 타입과 관련된 정보를 알아내는 기법실행 중 포인터가 가리키는 객체의 실제 타입을 알아야 하는 경우,클래스가 상속 관계에 있을 때 포인터가 가리키는 객체가 파생클래스의 객체인지기본클래스의 객체인지 판단해야 하는 경우, RTTI 기법을 이용해 알아낼 수 있다.RTTI 활용을 위해서는 typeinfo 헤더를 포함시켜야 함. type_info 클래스는 typeid 연산자에 의해 반환되는 정보로,타입 이름과 같은 타입에 관한 정보를 가진 클래스임 123456789class type_info{public: bool operator==(const type_info& rhs); bool operator!=(const type_info& rhs); ..

문서 편집 시 삽입, 삭제, 대체 연산이 사용되며이 때 어떤 특정 문자열 S를 다른 문자열 S`으로 변환시키 과정에서 필요한최소 편집 연산 횟수를 편집 거리(Edit Distance)라고 한다. stable이라는 문자열을 strike로 바꾼다고 할 때를 생각해보자.여러 가지 방법이 존재한다. 첫 번째 방법은 s, t, e는 그대로 두고 ‘abl’을 삭제하고 ‘rik’를 삽입하는 방식으로,3회의 삭제 연산과 3회의 삽입 연산으로 총 6회의 편집 연산이 실행되었다. 두 번째 방법은, s, t, e를 그대로 사용하고 ‘abl’을 ‘rik’로 바꾸기만 하면 stable을 strike로 바꿀 수 있고,3번의 대체가 발생했기 때문에 이 때 총 3회의 편집 연산 실행되었다. 두 문자열을 바꾸는 데 필요한 편집 거리를..

연속된 행렬들의 곱셈에 필요한 원소 간 최소 곱셈 횟수를 찾는 문제로,일단 연속된 행렬 간의 곱셈이 모두 가능하다는 전제 조건 하에 이루어진다. A=10X20, B=20X5, C=5X15 다음 세 행렬에 대한 계산을 예로 들면, AxBxC는 두 가지 방법으로 계산할 수 있다. 1. (AxB)xC2. Ax(BxC) 두 가지 계산은 결과는 아무 차이가 없지만, 순서에 따라서 두 행렬 곱셈의 횟수가 차이가 나기 때문에이를 최소화하고자 하는 방법을 구성할 필요가 있다. 일단, 1번의 계산을 예로 들면, 1번의 계산에서는 AxB는 10x20x5로, 1000회의 원소 곱셈을 시행하고,AxB 행렬은 10x5로, (AxB)xC는 750회 곱셈을 진행해 전체적으로 1750회의 원소 곱셈을 시행해야 한다. 2번의 계산은 ..

C++로 알고리즘 문제를 풀거나 이런 저런 이유로 코딩을 하다 보면 vector를 사용하게 되고 이 vector 내에 들어가는 값들을 정렬하기 위해서 직접 정렬을 구현해주는 방법도 있지만 좀 더 최적화되어 빠른 속도로 정렬을 수행해주는 sort함수를 사용하게 된다. 요소의 상대적 위치가 바뀌지 않는 걸 원한다면, stable_sort를 사용하면 된다. 통상적으로 자료형이 하나(예를 들어 int 하나)만 들어가는 vector라면, 시작점과 끝만 정해주면 알아서 오름차순 정렬을 수행해버리기 때문에 문제가 되지 않지만, vector 배열에 들어가는 정보가 여러 가지 자료형이 섞여 있는 구조체이고 그 구조체 안의 변수를 기준으로 정렬을 수행해야 한다면, 갑자기 머리가 아파온다. 대부분 레퍼런스를 참고하지 않거나..