9._.coding

T(n)의 복잡도를 추정하기 위해, 즉 알고리즘의 시간복잡도를 모델링하기 위해서 재귀트리를 사용합니다. 재귀트리를 이용해 시간복잡도를 구하기 위해서는 점화식이 필요한데, 점화식을 다양한 높이의 재귀호출에서 발생할 비용을 나타내는 노드가 있는 트리 구조로 변환합니다. 시간 복잡도를 구하기 위해 높이와 층별 노드합을 구해야 하는데, 높이는 n층에서의 일반항을 구해 나타내며(필기 참조), 노드합은 하나의 깊이에서 노드를 모두 더해 나타냅니다. 계수가 같고 합이 일정한 경우 점화식이 T(n) = 2T(n/2) + cn의 꼴이므로 T(n)은 호출 시마다 2개의 T(n/2)를 호출합니다. 따라서 트리가 그림과 같이 그려지게 되고, 각 층의 노드합은 cn이 되며, 그러므로 O(nlogn)의 시간복잡도를 가지게 됩니다..

동적 계획법, Dynamic Programming(DP)는 최적화 이론의 한 종류로, 특정 값을 구하기 위해서 다른 범위의 값을 이용해 효율적으로 값을 구하는 알고리즘으로, 쉽게 말해 답을 재활용하는 알고리즘이다. 답을 구하기 위한 계산을 반복하는 구조, 즉 같은 답을 계속 내서 다른 값을 이용해야 하는 문제(대표적으로 피보나치 수열)에 매우 뛰어난 방법이다. 분할 정복 기법 - 큰 문제를 작은 문제로 쪼개어 풀이하는 알고리즘에서 값을 저장하는 로직이 추가되었다고 할 수도 있다. 가장 중요한 아이디어는 문제를 재계산(예를 들어 재귀적으로 풀이하는 기법)하지 않는 것이고, 이를 막기 위해 값을 기억하거나 테이블을 만들어 해결한다. 그러므로, 최종 목표를 달성하기 위한 단계를 한 번 씩만 풀게 된다는 것을 ..

Problem I have some (say, n) marbles (small glass balls) and I am going to buy some boxes to store them. The boxes are of two types: T ype 1: each box costs c1 Taka and can hold exactly n1 marbles T ype 2: each box costs c2 Taka and can hold exactly n2 marbles I want each of the used boxes to be filled to its capacity and also to minimize the total cost of buying them. Since I find it difficult ..

Problem In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad’s back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley’s engagement falls through. Consider Dick’s back to be a plane with freckles at various (x, y) locations. Your job is to tell Richie how to connect the dots so as to minimize the amount of ink..

Problem Problems that require minimum paths through some domain appear in many different areas of computer science. For example, one of the constraints in VLSI routing problems is minimizing wire length. The Traveling Salesperson Problem (TSP) — finding whether all the cities in a salesperson’s route can be visited exactly once with a specified limit on travel time — is one of the canonical exam..

Problem A subsequence of a given sequence is just the given sequence with some elements (possibly none) left out. Formally, given a sequence X = x1x2 . . . xm, another sequence Z = z1z2 . . . zk is a subsequence of X if there exists a strictly increasing sequence of indices of X such that for all j = 1, 2, . . . , k, we have xij = zj . For example, Z = bcdb is a subsequenc..

점근 표기법, Asymptotic Notation을 활용해 우리는 극한(입력값 n이 충분히 클 때)에서 함수의 동작을 설명할 수 있습니다. 주로 시간 복잡도(Time Complexity)에서 사용합니다. 특정 함수를 다른 함수들을 통해 비교하여 그 특정 함수가 어느 정도 범위를 가질지 예측하는 것으로 이것을 통해, 알고리즘의 우열을 구할 수 있고 어떤 알고리즘이 더 효율적인지 분석할 수 있습니다. 예를 들어, T(n) = 10n^2 + 7n + 102라고 하면 낮은 차수의 항을 삭제하고, 최고차항의 계수를 지워 n^2으로 나타냅니다. Big-O Notation 가장 많이 사용되는 점근표기법, 빅 오 표기법(Big-O notation)입니다. 필기 사진에 나와있듯, 빅오 표기는 f(n) = O(g(n)) ..

Shoemaker has N jobs (orders from customers) which he must make. Shoemaker can work on only one job in each day. For each i-th job, it is known the integer Ti (1 ≤ Ti ≤ 1000), the time in days it takes the shoemaker to finish the job. For each day of delay before starting to work for the i-th job, shoemaker must pay a fine of Si (1 ≤ Si ≤ 10000) cents. Your task is to help the shoemaker, writing..

input 파일에 숫자가 무언가(공백, 콜론, 따옴표)로 구분되어 있고, 그 숫자를 함수에서 사용하고자 할 때 편하고 정확하게 변수에 저장할 수 있는 코드입니다. 전체코드는 아래에 있습니다. 코드를 설명하기에 앞서, atoi와 strtok이 무엇인지 간단하게 알아보도록 하겠습니다. atoi는 문자열을 정수로 변환해주는 함수로, 헤더파일 에 선언되어 있습니다. 함수 원형은 int atoi(const char *str) 이며, 문자열을 숫자열로 바꾸는 함수는 atoi() 말고도 atof(), atol()이 있으며, 각각 문자열을 double(실수)로, long으로 바꾸는 함수입니다. strtok는 문자열을 기준을 가지고 분리해주는 함수이고, 헤더파일을 사용합니다. 함수 원형은 char* strtok(char..

C언어를 이용한 기본 파일입출력 형식입니다. 다뤄야 하는 파일이 많을 때 유용하게 사용할 수 있습니다. 전체코드는 아래에 있습니다. void File_input(int i) { char Input[5][15] = { "Input_1.txt", "Input_2.txt", "Input_3.txt", "Input_4.txt", "Input_5.txt" }; FILE* input; input = fopen(Input[i], "r"); if (input != NULL) { //read function. } else { printf("Error."); exit(1); } fclose(input); } 파일 입력을 구현하는 함수입니다. input file들의 이름을 배열로 선언하고, main 함수에서 반복문을 돌림으..