안녕하세요.
프로그래머 학부생입니다
이번에 문자열소팅에 관한 과재가 나와서 sorting알고리즘을 짰는데요.(divide and qonquer)
되는데로 수정해가며,,, 구글링(...ㅠㅠ)....해가며 디버깅(으아아악)해가며 어찌저찌 짰는데
문제는 재가 알고리즘 개강 초반에 시간복잡도 계산하는 부분에서 졸음을 이기지못하여(오열...)
알고리즘 강의를 배웠다면 개나 소나(전 아직 사람이 아니에요 ㅠㅠ)한다는 time complexity를 계산을 못한다는겁니다...(개멍청, 말미잘)
그래서 오유 프로그래머 게시판에 상주하시고 계신 프로그래머 형님들꼐 댓글로 커피를 나눔함(이라고 쓰고 뇌물이라고 읽어요..)과 동시에
질문합니다
재가 짠 알고리즘의 시간복잡도는 B(O) = ? 인가요....(쭈글쭈글)
----------------------------------------------------------------------
void StrInfo::Merge(int s, int m, int e, string &str)
{
int cntLeft = m - s + 1;
int cntRight = e - m;
char* pLeft = new char[cntLeft + 1];
char* pRight = new char[cntRight + 1];
int x = 0, y = 0;
for (int i = s; i < m + 1; i++)
{
pLeft[x] = str[i];
x++;
}
for (int i = m + 1; i <= e; i++)
{
pRight[y] = str[i];
y++;
}
x = 0, y = 0; //x, y 초기화
for (int i = s; i <= e; i++)
{
if (x < cntLeft && y < cntRight)
{
if (pLeft[x] - '0' > pRight[y] - '0') //문자를 int형으로 바꿔서 비교한다.
{
str[i] = pRight[y];
y++;
}
else {
str[i] = pLeft[x];
x++;
}
}
else if (x == cntLeft)
{
str[i] = pRight[y];
y++;
}
else if (y == cntRight)
{
str[i] = pLeft[x];
x++;
}
}
}
void StrInfo::M_Sort(int s, int e, string &str)
{
if (s == e)
return;
int m = (s + e) / 2;
M_Sort(s, m, str);
M_Sort(m + 1, e, str);
Merge(s, m, e, str);
}
bool StrInfo::Str_Check(int s, int m, int e)
{
string first_1 = ""; //문자열 a1
string first_2 = ""; //문자열 a2
string second_1 = ""; //문자열 b1
string second_2 = ""; //문자열 b2
for (int i = s; i < m + 1; i++)
{
first_1 = first_1 + first[i];
second_1 = second_1 + second[i];
}
for (int i = m + 1; i < e + 1; i++)
{
first_2 = first_2 + first[i];
second_2 = second_2 + second[i];
}
//문자열을 정렬(알파벳순으로 오름차순)
M_Sort(0, (e - s) / 2, first_1);
M_Sort(0, (e - s) / 2, first_2);
M_Sort(0, (e - s) / 2, second_1);
M_Sort(0, (e - s) / 2, second_2);
if ((first_1 == second_1) && (first_2 == second_2)) //a1 == b1 & a2 == b2
return true;
else if ((first_1 == second_2) && (first_2 == second_1)) //a1 == b2 & a2 == b1
return true;
else
return false;
}
void StrInfo::DivideQonquer(int s, int e)
{
if (e - s + 1 == 2) //비교하려는 문자열의 길이가 2일때까지 Divide and Conquer
{
return;
}
int m = (s + e) / 2;
if (!Str_Check(s, m, e)) //성립하는 조건이 없으면
{
result = false;
return;
}
DivideQonquer(s, m);
DivideQonquer(m + 1, e);
}
