Twinparadox Factory

문서 편집 시 삽입, 삭제, 대체 연산이 사용되며이 때 어떤 특정 문자열 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..

연속된 행렬들의 곱셈에 필요한 원소 간 최소 곱셈 횟수를 찾는 문제로,일단 연속된 행렬 간의 곱셈이 모두 가능하다는 전제 조건 하에 이루어진다. 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 배열에 들어가는 정보가 여러 가지 자료형이 섞여 있는 구조체이고 그 구조체 안의 변수를 기준으로 정렬을 수행해야 한다면, 갑자기 머리가 아파온다. 대부분 레퍼런스를 참고하지 않거나..

Algorithm] Knapsack(배낭 문제) - 동적계획법 처음 내가 알고리즘 문제를 접했을 때 처음으로 배낭 문제를 접근했던 방식은 그리디였다.그리디는 다들 알고 있듯, 선택에 대한 번복도 없고, 근시안적인 선택으로 인해서경우에 따라서는 최적해를 보장하지 못하는 문제가 발생한다. 모든 배낭 문제에 대해서 그리디가 유효한 방법이 될 수 없는 건 아니고,물건을 임의로 쪼개어 담을 수 있는(용량을 정할 수 있는) 배낭 문제라면,무게 당 가격을 계산해서 적당히 담는 걸 고려하여 최적해를 구할 수 있기 때문에그리디 알고리즘으로는 해결이 가능하며 이를 부분 배낭(Fractional Knapsack)문제라고 한다.그러나, 일반적인 배낭 문제에서는 물건을 쪼개서 담을 수 없어서 다른 방식을 고려해야 한다. 이 때..

Algorithm] 작업 스케줄링(Task Scheduling) 기계에서 수행하는 n개의 작업(T1, T2, T3, ... , Tn)이 있고,각 작업에 시작 시간과 종료 시간이 존재한다고 할 때 최소한의 기계를 배치하면서모든 작업을 수행하도록 하는 문제를 작업 스케줄링이라고 한다.이 때 수행 시간이 중복되지 않게 모든 작업을가장 적은 수의 기계에 배정하는 최적해를 구하는 문제라는 것에 초점을 두자. 작업 스케줄링 문제에서 우리가 다룰 수 있는 변수와알 수 있는 정보에 대해서 조금 생각해보도록 하자. 작업의 수 n과, 각 작업들의 시작 시간과 종료 시간이 기본적으로 입력값으로 들어올 것이다.이건 입력값을 통해서 우리가 알 수 있는 정보고문제를 살펴봤을 때 우리가 알 수 있는 정보가 하나 더 있다.그 어떠한..

C++] Vector를 이용한 이중 배열 동적 할당에 대해서 익숙해지면배열을 정적으로 할당하는 경우가 줄어들게 되고거의 대부분 동적으로 할당하게 된다.그렇지 않은 사람들도 있겠지만,나는 변수 사이즈에 따라 배열 크기가 바뀌는 경우 반드시 동적할당을 통해서배열의 크기를 결정 짓는다. 그러다가 STL의 vector라는 걸 알게 되면,동적 할당도 잘 사용하지 않게 된다.구조체가 필요하고 안에 들어가는 변수 관리가 까다로운 경우가 아니면,거의 대부분의 경우 vector를 사용하게 된다.물론, vector에 임의의 구조체를 넣지 못하는 건 아니고그건 순전히 사용하는 나의 숙련도 문제에서 기인한 것이라고 생각된다. Topcoder나 비정기적 혹은 정기적으로 개최되는 코딩 대회에 참가하거나,그곳에서 나온 문제들을 풀..

Algorithm] 합병 정렬(Merge Sort) 합병 정렬은 대표적인 분할정복 방법(Divide and Conquer)을 사용한다.더 이상 부분 문제로 만들 수 없는 수준까지 분할한 뒤,이를 다시 취합하는 과정에서(정복) 정렬이 이루어지는 정렬 알고리즘이다. 일단 백문이불여일견이니 이것이 작동하는 과정을 그림으로 한 번 살펴보자. 파란색은 정렬이 완료되지 않은 부분문제, 즉 분할 대상이고주황색은 정렬이 완료된 부분문제로 정복 및 정복 대상이다.과정을 보면 알 수 있듯, 다시 한 번 말하지만 합병 정렬은 정복 과정에서 정렬이 이루어진다. 의사 코드를 한 번 살펴보자. MergeSort(arr,start,end)입력 : arr[start] ~ arr[end]출력 : 정렬된 arr[start] ~ arr[..

2011년 한국정보올림피아드(KOI) 초등부 문제 : 저울 이 문제의 답안과 채점은 Jungol이라는 사이트에서 이뤄졌다.(문제 번호 2499 : 저울) 필자는 두 가지 답안을 작성했다.그리디 알고리즘을 통해 최적해를 구하는 방법을 잘못 접근했기 때문인데,최대에서 최소로 최적해를 구성하면서 TLE(시간 초과) 문제가 발생해서 만점을 받지 못했고,최소에서 최대로 최적해를 구성하는 건, TLE 문제를 해결할 수 있었다. 아주 간단한 원리를 까먹고 진행해서... 1안 : TLE 발생 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include using namespace std;int ma..

C언어로만 작성했던 것들을 C++로 작성하면서 C++과 자료구조 공부를 동시에 하려고 한다. 지난번에는 C++로 간단한 삽입, 삭제, 출력 기능만 넣은 단일 연결 리스트를 구현했다. 이번에 올리는 글은 이중 연결 리스트(Double Linked List)로, 다음 노드에 대한 포인터만 가지고 있는 단일 연결 리스트와는 달리 이전 노드에 대한 포인터도 가지고 있어, 노드 간의 이동을 양방향으로 할 수 있게 구현하는 자료구조를 뜻한다. #include using namespace std; class Node { friend class List; private: Node* next; Node* prev; int value; Node(Node* n, Node* p, int v) { next = n; prev =..