[알고리즘실습] 2주차 실습과제

경북대학교 배준현교수님의 알고리즘실습 수업시간 실습과제를 이해하기 위한 포스팅입니다. 저의 코드는 정답이 아니며 참고만 해주시면 감사하겠습니다.

저도 배우는 입장이고 아직 대학생이므로, 간혹 설명을 잘못 드리는 경우가 있습니다. 댓글로 오류를 지적해주시면 감사하겠습니다.

 

AP.2.1 - 시간 복잡도 분석 1

함수의 시간 복잡도를 분석하는 문제입니다.

 

시간 초과에 걸리지 않기 위해 반복문을 몇 번 반복하는지 시간복잡도(점화식)를 구해야 합니다. 그래서 input 값을 넣으면 바로 결과가 나올 수 있도록 계산만 하면 일일히 반복문을 돌지 않으므로 시간 초과에 걸리지 않습니다.

 

#include <bits/stdc++.h>
using namespace std;

typedef long long long_t;

int main() {
    long_t n;
    cout << 2 * n * n;
}

 

AP.2.2 - 시간 복잡도 분석 2

이 문제에서 제가 생각하는 key point는 두 가지 입니다.

1. 값을 하나 받으면 log 값으로 변경하는 것
2. 받는 값에 따라 시간 복잡도가 달라짐을 계산하는 것

 

가장 바깥에 있는 for문은 값이 홀수이냐 짝수이냐에 따라 몇 번 돌지 달라집니다. 그 부분을 유의하시고 나머지 반복문들은 $log$ 값을 반환해서 사용하면 됩니다.

#include <bits/stdc++.h>
using namespace std;

typedef long long long_t;

long_t logB(long_t x, long_t base) {
    return log(x) / log(base);
}

int main() {
    long_t n, m, p;
    cin >> n >> m >> p;
    if(n % 2 == 0) {
        cout << (logB(p, 2) + 3) * (logB(m, 2) + 2) * (n / 2);
    } else {
        cout << (logB(p, 2) + 3) * (logB(m, 2) + 2) * ((n / 2) + 1);
    }
}

 

AP.2.3 - 시간 복잡도 분석 3

$n$의 값에 따라 식이 어떻게 구성되는지 확인하면 시간복잡도를 구할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

typedef long long long_t;

int main() {
    long_t n;
    cin >> n;
    cout << 4 * n * n;
}

 

AP.2.4 - 시간 복잡도 분석 4

$n$의 값이 4의 지수 값에 따라 시간복잡도가 정해집니다. 밑이 4인 $log$를 사용해서 식을 구하면 됩니다. 그래서 4번인가

#include <bits/stdc++.h>
using namespace std;

typedef long long long_t;

long_t logB(long_t x, long_t base) {
    return log(x) / log(base);
}

long_t pow_long_t(int n, long_t m) {
    long_t temp = 1;
    for(long_t i = 0; i < m; i++) {
        temp *= n;
    }
    return temp;
}

int main() {
    long_t n;
    cin >> n;
    cout << pow_long_t(8, logB(n, 4) + 1);
}

 

AP.2.5 - 콜라츠 수열 출력하기

콜라츠 수열은 값에 따라 특정 수식에 의해 항상 1로 수렴하는 수열을 말합니다. 증명되진 않았지만 현재까지 1로 수렴하지 못하는 수를 찾지 못해 아직 추측으로 남아있습니다.

 

콜라츠 수열은 다음과 같은 알고리즘으로 수열을 만듭니다.

• 짝수: 2로 나눔
• 홀수: 3을 곱하고 1을 더함

 

이 알고리즘을 재귀로 수행할 수 있도록 짜주면 다음과 같습니다.

#include <bits/stdc++.h>

using namespace std;

int collatz(int n) {
    cout << n << " ";
    if(n == 1) return 1;
    else if (n % 2 == 0) return collatz(n / 2);
    else return collatz(3 * n + 1);
}

int main() {
    int n;
    cin >> n;
    collatz(n);
}

 

AP.2.6 - 가장 긴 콜라츠 수열

콜라츠 수열을 찾으면서 호출하는 collatz() 함수에 count++을 넣어주어 몇 번 도는지 세주면 됩니다. 그 중 가장 큰 count가 나오면 count값과 index 값을 갱신해주는 식으로 짜주면 됩니다.

#include <bits/stdc++.h>

using namespace std;

int cnt;
int collatz(int n) {
    if(n == 1) return 1;
    else if (n % 2 == 0) {
        cnt++;
        return collatz(n / 2);
    }
    else {
        cnt++;
        return collatz(3 * n + 1);
    }
}

int collatz_print(int n) {
    cout << n << " ";
    if(n == 1) return 1;
    else if (n % 2 == 0) return collatz_print(n / 2);
    else return collatz_print(3 * n + 1);
}

int main() {
    int n, m, max = -1, idx = -1;
    cin >> n >> m;

    for(int i = n; i <= m; i++) {
        collatz(i);
        if(max < cnt) {
            max = cnt;
            idx = i;
        }
        cnt = 0;
    }

    cout << idx << " " << max << '\n';
    collatz_print(idx);
}

 

 

AP.2.7 - 하노이의 탑

하노이 함수를 몇 번 호출하는지 세는 call_hanoi 변수와 이동횟수를 저장하는 flag 변수를 0으로 초기화합니다.

hanoi()에서 각각의 변수들을 세면서 원반의 이동 횟수와 함수 호출 횟수를 각각 세면 됩니다.

 

원반의 이동 횟수 != 함수 호출 횟수

 

 

 

#include <bits/stdc++.h>
using namespace std;

int cnt = 0, call_hanoi = 0;
int flag;

void hanoi(int n, char src, char via, char dst) {
    call_hanoi++;
    if (n == 1) {
        cnt++;
        if (flag == cnt) {
            cout << src << " -> " << dst << '\n';
        }
    }
    else {
        hanoi(n-1, src, dst, via);
        hanoi(1, src, via, dst);
        hanoi(n-1, via, src, dst);
    }
}

int main() {
    int n;
    cin >> n >> flag;
    hanoi(n, 'A', 'B', 'C');
    cout << call_hanoi;
}