자료구조론 알고리즘 질문입니다.

다음 문제들을 과정 포함해서 풀어주세요.

1. T(n)=3n^2+2√n-3log(n)-4 를 Big-O 표기법으로 표기하라.

2. f(n)=O(S(n)), g(n)=O(r(n)) 일때 각 관계가 성립함을 증명하고, 아니면 반례를 들어 설명하라.

f(n)-g(n)=O(S(n)-r(n))

f(n)/g(n)=O(S(n)/r(n))

3. 후위형 식을 전위형 식으로 변환하는 C함수를 작성하고 작성된 함수의 시간복잡도를 구하라.

4. 단순연결리스트의 각 노드를 역순으로 만드는 함수를 구현하라.

5. 다음 합을 구하라

∑i*2^i 단 i는 0에서 k까지, ∑i*2^(-i) 단 i는 0에서 k까지

문제가 많아서 죄송합니다. 이해할 수 있게 계산과정 포함해 주시고 급하니까 빨리 올려주세요.
-----------------------------------------------------------------------------------

1. 윗분이 잘 하셨네요. T(n) = O(n^2)

2. 첫번째 경우 예를 들어 f(n) = (n^2)+n, g(n) = (n^2) 이라 생각해 보면

s(n) = r(n) = n^2 이 되지요. 하지만 f(n) - g(n) = n 이기 때문에 n = O(0) 라는 잘못된 결과가 나오네요.

두번째는 맞는것 같네요. f(n)을 g(n)로 나눈 결과의 최고차 항은 f(n)의 최고차 항에서 g(n)의 최고차 항으로 나눈 것과 같습니다. 각각은 결국  s(n), r(n)을 나타내니깐 결과적으로 f(n)/g(n)=O(S(n)/r(n))이 성립하겠죠.

3. 우리가 쓰는 식은 일반적으로 중위형이죠. 후위형 식이란 연산자가 수식의 끝에 달라붙는 것입니다. a+b를 후휘형으로 나타내면 ab+가 됩니다. 전위형은 +ab가 되는 것을 말하겠지요. 후휘형을 전위형으로 바꾸는 과정은 윗분처럼 트리를 이용할 수 있습니다만.. 단지 후위형을 전휘형으로 바꾸기 위해 트리를 만들고 순회하는 것은 오히려 오버헤드가 생길 수 있습니다.

예를 들어 살펴보면.. ((A/B)*C+(D*E))-(A*C) 이런 수식을 후위형으로 표현하면 AB/C*DE*+AC*-이 됩니다. 이것을 전위형으로 바꾸는 과정은.. 먼저 알파벳(또는 숫자)가 들어오면 스택에 push합니다. 연산자가 들어온다면 스택에서 두개의 값을 pop한 후 두 값을 결합하고 맨 앞에 연산자를 붙여줍니다.  이 과정을 끝내게 되면 prefix의 결과는 stack의 맨 처음에 들어가 있게 됩니다. 스택을 구현하려면 코드가 길어지기 때문에 필요한 부분만 스택의 기능만 사용하여 아래와 같이 구현할 수 잇습니다..

#include < stdio.h >
#include < string.h >

void postfix_to_prefix(char* postfix, char* prefix);

void main() {
    char prefix[100];
    postfix_to_prefix("AB/C*DE*+AC*-", prefix);
    printf("%s\n", prefix);
}

void postfix_to_prefix(char* postfix, char* prefix) {
    int ptr = 0;
    char c;
    char stack[100][100], temp[100];
    while(c = *(postfix++)) {
        if(c=='+' || c=='-' || c=='*' || c=='/') {
            temp[0] = c;
            strcpy(temp+1, stack[ptr-2]);
            strcat(temp, stack[ptr-1]);
            strcpy(stack[ptr-2], temp);
            ptr--;
        }
        else {
            stack[ptr][0] = c;
            stack[ptr][1] = '\0';
            ptr++;
        }
    }
    strcpy(prefix, stack[0]);
}

postfix의 문자열을 linear하게 검사하면서 prefix로 만들기 때문에 time complexity는 n입니다. 하지만 문자열을 다루는 함수들의 경우 문자열의 길이에 비례하기 때문에 실제로는 n보다는 크게 되지요.

4. 방법이 몇가지 있겠지만.. 핵심적인 내용은 링크의 방향이 거꾸로 되게끔 바꿔줘야겠지요. 예를들어 A -> B과 같이 링크가 되어있을 경우 A <- B가 되도록 바꾸어주는 것을 기본으로 합니다. 이 과정을 모든 링크에 대해서 수행해 주면 되겠죠. 아래는 recursive call을 이용해서 구현해 보았는데.. 더 좋은 방법이 있을껀데 생각이 잘 안나네요..

node_ptr은 어떤 노드의 포인터를 뜻합니다. 첫번째와 두번째의 매개변수는 리스트의 헤드, 세번째는 헤드의 next를 넣어주면 됩니다. 리턴되는 값은 역방향으로 구성된 링크의 헤드가 되지요.(정방향 링크의 마지막 노드에 해당하지요.)

node_ptr reverse (node_ptr S, node_ptr p, node_ptr next) {
    if(p == NULL) return NULL;
    else if(next == NULL) return p;
    else {
        node_ptr temp = next->link;
        next->link = p;
        if(p == S) p->link = NULL;
        return reverse(S, next, temp);
    }
}

5. 위의 수식을 for문으로 그대로 구현하면 되네요..

#include < stdio.h >
#include < math.h >

void main() {
    int i, k;
    double sum1=0, sum2=0;
    printf("input k :");
    scanf("%d", &k);
    for(i=0; i <= k; i++) {
        sum1 += (double)i*pow(2, i);
        sum2 += (double)i*pow(2, -i);
    }
    printf("sum1 = %f\nsum2 = %f\n", sum1, sum2);
}

-----------------------------------------------------------------------------------
1. T(n)=3n^2+2√n-3log(n)-4 를 Big-O 표기법으로 표기하라.

음..big O 기법은 upper bound 로 가장 높은 차수만 생각하면 된다

T(n) = 3n^2 + ... < g(n) = cn^2 + N

이 되는 c 와 4가 존재함..

따라서 O (n^2)

2. f(n)=O(S(n)), g(n)=O(r(n)) 일때 각 관계가 성립함을 증명하고, 아니면 반례를 들어 설명하라.


음..문제를 다 적어 주시지 않으신듯..

f(n) 과 g(n) 의 관계나 S r 의 관계가 있어야 할듯 하네요

3. 후위형 식을 전위형 식으로 변환하는 C함수를 작성하고 작성된 함수의 시간복잡도를 구하라.


post order 방법을 써라..

책에 보면 있을꺼에요..Tree 부분에서..

주요 부분만 쓰자면..(Recursive로 짤수 있습니다)

postOrder (currentNode -> left);
postOrder (currentNode -> right);
cout << data;

--

제가 도울수 있는건 여기까지네요.ㅡ.ㅡ;;

3번의 경우는..저 idea 만 있으면..프로그램 짜는거는

List로 tree를 구현할수 있나 아니냐의 문제일 뿐이네요..

다만 4번의 idea만 말하자면..

4. currentNode -> link -> data;

지금 노드가 가리키는 노드의 링크가 지금 노드의 data를 가리키면 된다..

저도 linked list는 자주 안써봐서..^^;;

5. 음..ㅡㅡ; 못풀겠네요..ㅡㅡ; 다른분이 풀어주시면..^^ 저도 참고 하겠습니다.