Twinparadox Factory

알고리즘 문제를 풀면서 접했던 문제 중 하나로 순서가 정해지지 않은(정렬되지 않은) 방대한 데이터를 입력 받아 특정 구간에서의 최솟값을 구하는 문제가 있었다. 하나씩 모두 비교하는 방법을 사용하는 건 구현은 간단하지만, 전체 구간에 대한 최솟값을 구하는 경우 O(N)의 시간 복잡도를 갖게 되고, 거기에 이러한 쿼리가 최대 M회 실시된다고 하면 O(NM)이며, 쿼리가 N에 근접하는 문제의 경우 O(N^2)의 시간 복잡도로 실행 시간 초과가 발생할 수 있다. 구간별 최솟값을 구해두고 쿼리에 대응하는 방법을 고안해도, 최초 구성 단계에서의 시간 복잡도의 문제가 있고, 내용을 바꾸는 쿼리가 존재한다면 재구성하는 과정에서 시간 투자가 필요하기 때문에, 아무래도 기존의 단순 비교 방식을 이용한 구간 내 최솟값 산출..

이전 포스팅에서도 말했다시피, 일반적인 재귀 방법을 사용하는 건 시간이 오래 걸린다는 단점을 가지고 있다. 메모화재귀는 동적계획법을 재귀적으로 사용하는 것으로 동적계획법의 일종으로한 번 계산이 진행된 것은 추가로 진행하지 않는 것을 목표로 하기 때문에깊이 우선 탐색을 응용해 (1,1)에 하위에서 생성된 계산값을 미리 작성해두어만일 다시 접근이 이뤄지면 그 값을 반환시키는 것을 말한다. 깊이 우선 탐색을 통해서 일반적인 재귀 방법으로 접근했을 때 중복되는 작업들을 많이 걸러낼 수 있어서제한 시간 초과라는 문제를 극복할 수 있다. const int h = 5, w = 4; int Memo_recursion[h + 1][w + 1]; int dfs(int nowh, int noww) { if (nowh > h..

B A 아마 고교시절 순열조합 부분에서 자주 접하는 문제 중 하나로,A 지점에서 B 지점으로 갈 때 최단거리의 경우의 수가 얼마나 되는지 구하는 것이 목표인 문제다. 깊이우선탐색을 사용할 때, 모든 기점마다 경로를 선택해야 하고 이 경우 30번정도 그런 과정이 필요하다.따라서 Big O는 O(2^(w+h))가 되어 2^30인데 10억이 넘어가는 수치가 된다.연산 시간이 오래 걸려 썩 좋은 방법이 아니다. 우리는 이 문제를 고교시절 기계적으로 푸는 방법을 터득한 바 있다.바로 이항정리에 근거한 조합을 이용하는 방법이고9C4=126이라는 정답에 빠르게 근접할 수 있다.Big O 또한 O(w+h)로 계산량도 적어 매우 효율적으로 보인다.그러나, 이는 모든 지점을 통과할 수 있을 때나 가능하다는 제한적인 케이스..

입력 받은 배열을 O(n)으로 히프 트리 구조로 생성할 수 있지만, 여기서는 일단 O(nlogn)으로 진행되는 히프트리 구성을 실시했다. (이 부분에 대해서는 차후 포스팅할 생각) 최대 히프트리를 구현했고, 최대 히프트리를 바탕으로 오름차순 정렬을 하는 코드다. 내림차순 정렬을 보고 싶다면, list 배열에 넣는 인덱스 순서만 바꿔주면 되고 공부 삼아 최소 히프트리를 구현하는 것도 나쁘지 않을 것이다. 숙련자가 보기에는 이 소스는 잘 짜여진 소스는 아니라는 것을 말해주고 싶다. 처음 자료구조를 배우던 시절 구조에 대해서만 깨우치고 만든 소스라서, 불필요한 메모리 할당도 있고 히프 트리 구성에서 시간 복잡도 손실을 보기는 하지만, 히프트리를 바탕으로 힙정렬(혹은 히프정렬)을 구현하는 것까지는 문제되지 않아..

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

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

외부정렬(External Sort)은 입력 크기가 매우 커 읽고 쓰기가 오래 걸리는 보조 기억 장치에저장할 수밖에 없는 상태에서 수행되는 정렬이다.통상적으로 주기억장치에서 다룰 수 있는 크기의 데이터를 다루던기존의 정렬은 내부정렬(Internal Sort)로 분류한다. 예를 들어, 주기억 장치 용량이 1GB라면, 데이터의 크기가 극단적으로 128GB라고 하자.이런 경우에는 주기억 장치에 데이터를 모두 올릴 수는 없는 상황이라어떤 내부 정렬 알고리즘으로도 직접 정렬할 수는 없어 보조기억장치(HDD,SDD)를 이용해야 한다. 그렇다면 이제 입력을 분할해 주기억 장치가 수용 가능한 만큼의 데이터에 대해내부 정렬을 수행하고 다시 이를 저장하는 방법을 반복하여,점진적으로 크기를 늘려나가는 방식을 고려해야 한다.내..

템플릿 이용해서 스택을 일반화해봤다. 클래스 활용도 연습을 해볼 겸, 템플릿 사용도 연습을 해볼 겸...다른 기능 없이 아주 일반적인 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

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

KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4..