Twinparadox Factory

https://www.acmicpc.net/problem/2193 알고리즘이 복잡한 건 없다.알고리즘에 대해서 지식이 전무한 사람은 모든 케이스를 테스트하려고 하지만,기본적으로 숫자길이를 확장해나가는 것에 있고,이전의 값을 바탕으로 답을 구해나갈 수 있다는 점을 감안하면 쉽게 풀어낼 수 있다. 숫자의 자릿수가 늘어날 때마다, 이전에 판단했던 이친수에서얼마나 많은 이친수를 만들어낼 수 있는지에 관한 점화식을 작성하기만 하면 된다.복잡한 2차원 테이블을 작성하는 것도 아니라서 비교적 쉬운 편이다. 유의해야 하는 점 하나는,n값이 커지면 int 범위를 넘어가기 때문에여기서 long long int를 사용했던 것처럼 이를 담아낼 수 있는 적합한 자료형을 사용해야 한다는 점이다. 123456789101112131..

항상 고민하던 게 있다.비교 정렬의 하한이 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)를 이용해야 한다. 그렇다면 이제 입력을 분할해 주기억 장치가 수용 가능한 만큼의 데이터에 대해내부 정렬을 수행하고 다시 이를 저장하는 방법을 반복하여,점진적으로 크기를 늘려나가는 방식을 고려해야 한다.내..

알고리즘 문제를 풀다 보면, Time Limit(시간 제한)에 대해서 신경 쓰지 않을 수가 없다.제한된 메모리에서 최대한 빠른 시간 내에 정확한 답을 찾는 것이 좋은 알고리즘이고,그렇지 못한 알고리즘은 TLE나 시간 초과 등을 이유로 답을 처리해주지 않는다. 입출력이 수천 번에 머무르면 시간 초과가 발생하면거의 대부분 알고리즘에 문제가 있지만,입출력이 수십만 개, 수백만 번에 이르면 이야기가 좀 다르다. 한 예를 들어서 설명을 해볼까 한다. https://www.acmicpc.net/problem/11004 백준 사이트의 11004번 : K번째 수라는 문제다.N개의 숫자들을 입력 받고 오름차순 정렬을 했을 때,K번째의 수를 출력하는 것이다. 문제는 되게 간단하다.입력 값이 5백만개에 이르며 숫자 중복도 ..

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

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

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