Maintenance script: Table transclusion repair v1

2026-03-27T12:46:17Z

Table transclusion repair v1

imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:28Z

New page

== 소감 ==
단순히 Greedy 알고리즘으로 접근. 실패. Dynamic Programming 이 필요함을 테스트 케이스로써 확인했다. Dynamic Programming 을 실제로 해본 경험이 없기 때문에 감이 잡히지 않았다. Introduction To Algorithm에서 Dynamic Programing 부분을 읽어 공부한 후 문제분석을 다시 시도했다. 이 문제를 쉽게 풀기 위해 Weight를 정렬한 배열과 IQ를 정렬한 배열을 하나의 문자열로 보았다. 그렇다면 문제에서 원하는 "가장 긴 시퀀스" 는 Longest Common Subsequence가 되고, LCS는 Dynamic Algorithm으로 쉽게 풀리는 문제중 하나였다. 무게가 같거나, IQ가 같을수도 있기 때문에 LCS에서 오류가 나는 것을 피하기 위해 소트함수를 처리해 주는 과정에서 약간의 어려움을 겪었다.

{{| 2005/07/09 Accepted 0:00.035 64 |}}

lcs_length함수에서 cost table을 만들어주는 과정의 running time은 O(n*n), memory cost는 O(n*n)이다. 그리고 print_lcs 함수에서 longest path를 거슬러 올라가는 running time은 O(n + n) = O(n)이다.

무엇보다 몇일동안 고생해서 푼 보람이 있어 좋다.

== 코드 ==
==== ver1 (Greedy Algorithm) ====
이 알고리즘은 답을 산출해 내지 못한다.
//no 10131
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

fstream fin("input.txt");

const int MAX_ELEPHANT = 1100;

struct Elephant
{
int index;
int weight;
int IQ;
bool operator () (const Elephant & a, const Elephant & b)
{
if (a.weight < b.weight)
return true;
else if (a.weight == b.weight)
{
if (a.IQ > b.IQ)
return true;
}
return false;
}
};

int input_elephant_info(Elephant * e);
void count_elephant(Elephant * elephant, int num_elephant);

int main()
{
Elephant elephant[MAX_ELEPHANT];
int num_elephant = input_elephant_info(elephant);
sort(&elephant[0], &elephant[num_elephant], Elephant());
count_elephant(elephant, num_elephant);
return 0;
}

int input_elephant_info(Elephant * e)
{
int count = 0;
while (fin >> e[count].weight >> e[count].IQ)
{
e[count].index = count + 1;
count++;
fin.get();
if (fin.peek() == EOF)
break;
}
return count;
}

void count_elephant(Elephant * e, int num)
{
// test
// for (int t = 0; t < num; t++)
// {
// cout << e[t].index << " " << e[t].weight << " " << e[t].IQ << endl;
// }
// end

int max_count = 0;
int count;
vector<int> v_temp;
vector<int> result;
result.reserve(MAX_ELEPHANT);
v_temp.reserve(MAX_ELEPHANT);
Elephant temp;
int i;

for (int k = 0; k < num - 1; k++)
{
temp.weight = e[k].weight;
temp.IQ = e[k].IQ;
v_temp.push_back(e[k].index);
count = 1;

for (i = k + 1; i < num; i++)
{
if (temp.weight >= e[i].weight || temp.IQ <= e[i].IQ)
continue;
temp.weight = e[i].weight;
temp.IQ = e[i].IQ;
count++;
v_temp.push_back(e[i].index);
}

if (count > max_count)
{
max_count = count;
result = v_temp;
}
v_temp.clear();
}

cout << max_count << endl;

for (i = 0; i < max_count; i++)
cout << result[i] << endl;
}

==== ver2. Dynamic Algorithm ====
//no 10131
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

const int MAX_ELEPHANT = 1010;
const int WEIGHT = 1;
const int IQ = 2;
int TYPE_SORT;

struct Elephant
{
short index;
short weight;
short IQ;
bool operator () (const Elephant & a, const Elephant & b)
{
if (TYPE_SORT == WEIGHT)
{
if (a.weight < b.weight)
return true;
else if (a.weight == b.weight && a.IQ <= b.IQ)
return true;
return false;
}
else
{
if (a.IQ > b.IQ)
return true;
else if (a.IQ == b.IQ && a.weight > b.weight)
return true;
return false;
}
}
};

Elephant elephant_weight[MAX_ELEPHANT];
Elephant elephant_IQ[MAX_ELEPHANT];
int num_elephant;
vector <int> result;

int input_elephant_info();
void sort_elephant();
int lcs_length(unsigned char t[][MAX_ELEPHANT]);
void print_lcs(int i, int j, unsigned char t[][MAX_ELEPHANT]);
void print_route(int len);

int main()
{
unsigned char table[MAX_ELEPHANT][MAX_ELEPHANT];
num_elephant = input_elephant_info();
sort_elephant();

int len = lcs_length(table);

print_lcs(num_elephant, num_elephant, table);

print_route(len);
return 0;
}

int input_elephant_info()
{
int count = 0;
while (cin.peek() != EOF)
{
count++;
cin >> elephant_weight[count].weight >> elephant_weight[count].IQ;
elephant_weight[count].index = count;
elephant_IQ[count] = elephant_weight[count];
cin.get();
}
return count;
}

void sort_elephant()
{
TYPE_SORT = WEIGHT;
sort(&elephant_weight[1], &elephant_weight[num_elephant+1], Elephant());
TYPE_SORT = IQ;
sort(&elephant_IQ[1], &elephant_IQ[num_elephant+1], Elephant());
}

int lcs_length(unsigned char t[][MAX_ELEPHANT])
{
int i, j;
for (i = 0; i <= num_elephant; i++)
t[0][i] = t[i][0] = 0;
for (i = 1; i <= num_elephant; i++)
{
for (j = 1; j <= num_elephant; j++)
{
if (elephant_weight[i].index == elephant_IQ[j].index)
t[i][j] = t[i-1][j-1] + 1;
else if (t[i-1][j] >= t[i][j-1])
t[i][j] = t[i-1][j];
else
t[i][j] = t[i][j-1];
}
}
return t[i-1][j-1];
}

void print_lcs(int i, int j, unsigned char t[][MAX_ELEPHANT])
{
if (i == 0 || j == 0)
return;
if (elephant_weight[i].index == elephant_IQ[j].index)
{
print_lcs(i-1, j-1, t);
result.push_back(elephant_weight[i].index);
}
else if (t[i-1][j] >= t[i][j-1])
print_lcs(i-1, j, t);
else
print_lcs(i, j-1, t);
}

void print_route(int len)
{
cout << len << endl;
for (int i = 0; i < len; i++)
cout << result[i] << endl;
}
== 나한테 할 말 ==
----
[[IsBiggerSmarter？]] [[AOI]]

IsBiggerSmarter？/문보창 - Revision history

Maintenance script: Table transclusion repair v1

imported>Unknown at 05:23, 7 February 2021