컴퓨터 프로그래밍(암호학, 알고리즘)

문제 이차원 평면상에 위치한 많은 점들이 있다. 두 점 P(x1,y1) Q(x2,y2)의 사이의 거리는 SQRT[(x1-x2)^2 + (y1-y2)^2]로 정의한다면, 모든 점들 사이에서, 가장 가까운 거리를 찾아내시오. 제약조건 각 문제에 대해 답을 찾아내는 시간은 0.5초(500ms 이내)일 것 입력 입력문제는 텍스트파일로 주어지..

문제 an을 구하는 함수인 power(a,n)을, O(log(n))의 실행시간을 갖도록 구현하시오. 풀이 an은 직관적으로 풀면 O(n)이다. private long power_naive(int a, int n){ if(a==0) return 0; long result=1; for(int i=0;i<n;i++){ result = result * a; } return result; } 근데, 이것을 실행시간이 O(log(n))이 되게, Divide and Conquer를 이용해..

문제 배열 A는 1,2,3,...n 의 수가 무작위 순서로 들어 있다. 이 수들에서 두개의 무작위 수를 생각했을 때, 그 순서 대비 크기가 역전되어 있는 두 수의 쌍이 몇개가 되는 지를 구하시오. Number of inversions = Number of pairs(i,j) when i<j and A[i] > A[j] 예를 들어, A={2,3,6,4,1,7}일 때, 크기가 역전된 쌍..

앞에서 분할정복(Divide And Conquer) 방식을 이용한 MergeSort를 알아봤다. 되새겨 보면, - 정렬한 대상이 되는 수 전체를, 1개 또는 2개의 수로 구성된 작은 블럭들이 될 때까지 나누고, - 나눠진 블럭들을 소팅하면서, - 조금씩 옆에 있는 블럭들을 합쳐서(merge), 수 전체가 소팅되게 하는 것 이처..

분할정복(Divide And Conquer)은, 문제를 작게 쪼게서 각각 해결한 후, 다시 전체가 되게 합쳐서 문제를 해결하는 알고리즘이다. 기본 프로세스는 다음과 같다. 1. Divide: 문제를 여러개의 작은 문제로 나누다. 2. Conquer: 각 문제를 재귀적으로 호출하면서 푼다. 작게 나누다가, 직관적인 방법으로 ..

문제 여러 행렬들이 주어졌을 때, 이 행렬들을 모두 곱한 값을 구하시오. 여기서, 여러 행렬들은 행렬곱이 가능하다는 것이 보장되고, 두 행렬의 곱은 아래와 같이 정의된다. 행렬 A가 n행 m열이고[n , m], 행렬B가 m행 p열일 때[m , p], 행렬 A와 B의 곱행렬 C는 [n , p] 행렬이 되고, i행 j열일 때의..

문제 공장에 제품을 생산하는 두 조립라인이 있다. 조립 라인은 아래 그림처럼, 처음에 부품을 준비하는 준비단계를 거쳐(s0,s1), 자신의 조립라인 단계를 통과하거나(a0,0~a0,n, a1,0~a1,n), 혹은 다른 조립라인으로 이동해서(t0,1 등) 단계를 마친 후, 마지막에 최종점검 단계를 거쳐서(e0,e1) 조립..

문제 옷을 정가 이하로 바겐세일 하는 가게에 갔다. 그 가게에서, 현재 가지고 있는 현금(P) 이내에서, 최대 가치가되게(=정가 기준 합이 가장 크게) 옷을 구매하는 방법을 제시하시오. 단, 구매할 수 있는 옷의 수량 한도내에서 구매해야 함(L) - 가치: 옷의 정가 (values) - 판매가격: 현재 옷..

문제 n개의 보석이 있다. 각 보석은 자신의 고유 무게와 가치가 있다. 배낭에 이 보석들을 담는데, 보석들의 가치 총계가 최대가 되게끔 담아라. 단, 배낭에 담을 수 있는 최대무게는 제한되어있다. 즉, 제한된 무게내에서 최대가치가 되게 보석들을 담아야 한다. (담을 수 있는 개수는 제..

[문제] N개의 작업공정이 있다. 공정마다 소요되는 시간이 존재하고, 각 공정들 끼리 관계가 존재할 때는 선행 공정이 끝나야만 다음공정으로 넘어갈 수 있다. 예를 들어 아래 공정을 보면, A공정에 10이 소요되고 난 후, B와 C가 동시에 진행이 된다. 그렇게되면 B공정이 끝나는 시점은 30이..