TIL 0318, 더더덜 쉬운 문제와 이론 공부

간단한 문제 풀기를 했다. 오답노트 겸 적으려고 정리 :

파이썬 출력 순서에 대한 내용

굳이 언급 할 것도 없어서 넘어가겠다.

재귀함수의 장단점

예제 :

• 장점, 코드가 더 깔끔하고 이해하기 쉬울 수 있다.
• 단점, 함수 호출 시 메모리가 추가적으로 사용돼 메모리 소비가 많으며,
  잘못 사용 하면 스택 오버플로우를 일으킬 수 있다.
  또 반복문에 비해 빈번한 스택 메모리 할당/해제로 실행 속도가 더 느릴 수 있다.

나의 답 :

• 장점, 반복되는 내용에 대해 코드를 간결하게 작성 할 수 있다.
• 단점, 처음 작성 때 올바르게 설계하지 않으면 무한루프에 빠질 수 있다.

전체적으로 결이 비슷하니 맞다고 생각하겠다.

n을 입력받으면 1 - n까지의 피보나치 수열을 작성하기, 반복문으로, 재귀 방식으로

예제 :

# for 문을 사용한 피보나치 수열
def fibo(n):
    if n <= 0:
        return []
    elif n == 1:
        return [1]
    elif n == 2:
        return [1, 1]

    fib_seq = [1, 1]
       for i in range(2, n):
        fib_seq.append(fib_seq[i - 1] + fib_seq[i - 2])
    return fib_seq

 # 재귀를 사용한 피보나치 수열
     def fibo(n):
        if n <= 0:
            return []
        elif n == 1:
            return [1]
        elif n == 2:
            return [1, 1]
        else:
            seq = fibo(n-1)
            seq.append(seq[-1] + seq[-2])
            return seq

나의 답 :

 # for 문을 사용한 피보나치 수열
 def fibo(n):
     numA = 0 numB = 0 total = 0
    for i in range(n):
        total = numA + numB
        tmp = numA
        numA = numB
        numB = tmp + numB
    return total

# 재귀를 사용한 피보나치 수열
def fibo(n):
    if n <= 1:
        return n
    return fibo(n-1) + fibo(n-2)

대충 보면 출력하는게 내 답과 예제가 다르다.
안그래도 할 말이 있는게 수열을 만들라는걸 알고도 굳이굳이 n번째를 출력하는 걸로 생각한 내가 화난다.
안그래도 시간이 조금 남았을 때 생각 할 걸..

4. [3 1 2 5 3 1] 배열이 주어지면, 이에 대한 Quick Sort 수행 과정을 단계로 설명하기

이건 맞췄다. 넘어감

5. 프로세서 내의 PC와 ALU가 각각 수행하는 역할에 대해 설명하기
   예제 :

• 프로그램 카운터(PC)는 다음에 실행 할 명령어의 주소를 지정하는 역할을 하며, ALU는 산술 및 논리 연산을 처리 한다.

나의 답 :

• PC는 프로그램 카운터의 약자로, 주로 메모리의 특정한 명령어를 가리키는데 필요하다.
  가리키는 명령어는 메모리 상에서 연속적일수도 있고 그렇지 않을 수도 있다.
• ALU는 간단한 명령어 인스트럭션을 수행하며 레지스터 유닛과 연결 되어 있다.

파일럿 코는 결은 같지만 내용이 약간 다르단다. 다르게 설명하는 방법이었겠거니 생각하고 마무리 하기

여기까지가 오후 4시까지 한 일이다!!!!!!!!!!!!!!!!!!

이후에 코치진이랑 상담을 했는데.. 자세하게 쓸 수도 있지만 일단 극단적으로 요약하면

"책상 앞에서 주어진 것만 생각해라"

어차피 이 결론에 도달 할 걸 알았지만 오히려 이런 답으로 도달 할 것 같다면 물어보지 않아도 될 질문들을 없애는 확실한 트리거가 되었다.

그래서 오후에 생각했던게.. 알고리즘 영역으로는 바킹독 처음부터, 홍박사 강의 재숙지 할 생각을 하는 중.
남은 시간은 키워드에 대한 공부를 조 ㅁ했다.

반복문과 재귀함수

모든 반복문을 재귀함수로 나타낼 수 있는 것은 아니다. (그래도, 대부분은 가능하다고 설명한다)
하지만 그 반대로 모든 재귀함수는 반복문으로 나타 낼 수 있다. (물론 현실적으론 다사다난 할 것이다)

C++ 기준으로 for, while, do-while 정도만 알면 되겠고,
Python 기준으로는 해괴망측한 while-else문 정도를 알고 있어야한다.

나머지는 심심했다하면 쓰는것들 천지니 넘어가기

복잡도 (BigO, 시간, 공간)

honglab 강의에서도 정리했던 내용인데 거기에 기반해서 살을 붙이려고 한다.

표기법 | 읽는법 | 의미
O | 빅 오 | 위쪽 한계, 상한
Ω | 빅 오메가 | 아래 쪽 한계, 하한
θ | 쎄타 | 딱 맞는 경계, 동일

O(빅 오)의 점근적 상한 예시

7n^3 + 100n^2 - 20n + 6에 대한 내용은
O(n^3)이다.

** 가장 가파르게 증가하는 것을 선택하고 앞에 붙은 상수를 제거한다.**
상한이라는 단어의 의미는 위에서 언급된 식의 실행시간 함수가 아무리 최악의 경우에도 점근적으로 n^3 이하이다 라는 의미를 가진다.

O(빅 오)의 수학적인 정의

O(g(n))은 n0 이상인 모든 n에 대해서 O <= f(n) <= c * g(n)을 만족하는 양의 상수 C와 n0을 찾을 수 있는 f(n)의 집합을 말한다.
(여기서 f(n)은 c * g(n) 이하일 것. g 를 이용해서 f의 상한을 간접적으로 정할 수 있다.)

Copilot에게 해당 내용에 대한 좀 더 쉬운 코멘트를 요청 했다 :
어떤 특정 함수 𝑔(𝑛) 을 사용해서, 우리가 알고 있는 𝑓(𝑛) 보다 크거나 같은 값을 만들 수 있다면,
그리고 그 크기가 𝑛이 충분히 커지면서 항상 유지된다면, 우리는 𝑓(𝑛)을 𝑂(𝑔(𝑛)) 이라고 말할 수 있어요.

f(n)은 알고리즘의 실제 "시간"을 나타내는 함수입니다.
예를 들어, 반복문이 10번 돌았다면, f(n)은 10 같은 느낌이죠. g(n)은 그 시간의 "최대 성능 예측"입니다.
즉, 이 알고리즘이 아무리 복잡해도 이 정도 속도 안에서는 끝날 거야! 라고 "최대치"를 잡는 거예요.
수학적으로, f(n)이 C⋅g(n)을 넘지 않게 하는 상수 C와 n이 커질 때 해당 조건이 성립하는 시점인 n0를 찾는 게 핵심이에요.

O(빅 오)의 상한 예시

빅오는 한 개가 아니고 집합이기 때문에, 조건을 만족하는 것은 여러 개가 될 수 있다. 즉 빅 오의 정의는 "상한"이었으니 낮은 것 들을 전부 포함 할 수 있다는 이야기가 된다.

n, n^2, n^3 모두 빅 오의 n^3 이라고 할 수 있겠지만 가급적이면 딱 맞는 차수를 표기 해야한다.

저는 키가 2m 이하입니다.

맞는 말이지만 이게 일반적인 발언은 아니니까..

Ω(빅 오메가)의 수학적인 정의

O(g(n))은 n0 이상인 모든 n에 대해서 O <= c * g(n) <= f(n) 을 만족하는 양의 상수 C와 n0을 찾을 수 있는 f(n)의 집합을 말한다.
(c와 g가 f의 하한 정의로 사용된다.)

즉 종합하면 이 알고리즘은 아무리 빨라도 이정도는 걸린다! 를 정의하기 위해 만들어졌다.
데이터 크기 n이 아무리 작더라도, f(n)이 g(n)보다 작은 속도로 작동 할 수 는 없다는 것을 보장하는 식이다.

Ω(빅 오메가)의 점근적 하한 예시

빅 오메가는 하한이기 때문에 더 낮은 차수로 표기가 가능하다, 하지만 빅 오의 내용처럼 상식적인 선에서의 차수 표기가 필요하다.

θ(쎄타)에 대한 점근적 동일 예시

적은 식이 영어인데다가 특수기호가 너무 많아서 옮길 수가 없다. 대신에 나의 조수 파일럿 코가 조금 도와줄 것이다..

θ(빅 세타)는 알고리즘의 시간복잡도가 특정 함수와 정확히 일치하는 수준에서
상한과 하한을 동시에 만족할 때를 나타냅니다.
쉽게 말해, 이 알고리즘은 이 정도 시간이 걸리며, 이것보다 빠르거나 느리진 않아!라고 정확히 정의하는 거예요.

공간 복잡도에 대해 논하기

얼마나 많은 메모리를 사용하는지를 측정하는 개념이다.

공간 복잡도의 정의

1. 고정 공간(Fixed Space) : 입력 크기와 상관 없이 항상 필요한 메모리를 말합니다. (상수와 같은 개념)
2. 가변 공간(Variable Space) : 입력 크기에 따라 변하는 메모리를 말합니다. (배열, 재귀 호출 스택 등)

상수 공간 𝑂(1) : 작은 가방 하나에 모든 짐을 넣는 것처럼, 필요한 메모리가 고정됨.
선형 공간 𝑂(𝑛) : 손님 수에 따라 필요한 의자를 준비하는 것처럼, 입력 크기에 비례해서 공간 필요.
로그 공간 𝑂(log⁡𝑛) : 큰 트리의 한쪽 끝까지 올라갔다 내려오는 계단처럼, 높이에 비례한 공간 사용.
이차 공간 𝑂(𝑛^2) : 큰 정사각형 테이블에 모든 것을 채우는 것처럼, 입력 크기의 제곱만큼 공간 필요.

예제: 재귀 알고리즘에서 공간복잡도

_병합 정렬(Merge Sort)의 경우:
상한 (빅오): 병합 정렬에서 임시 배열을 사용하여 정렬하므로,
입력 크기 𝑛에 비례하는 추가 메모리가 필요합니다. 𝑂(𝑛).
하한 (빅 오메가): 최소한 입력 데이터 자체를 저장하는 메모리가 필요하므로, Ω(𝑛)입니다.
점근적 동일성 (빅 세타): 상한과 하한이 같으므로, 병합 정렬의 공간복잡도는 Θ(𝑛)로 표현됩니다._

빅오, 빅오메가, 세타 모두 사용 의도는 같기 때문에 공간 복잡도에서는 생략한다.

정렬

정렬을 통짜로 외우겠다고 신경쓰던 옛날이 생각나지만 알고보면 Merge Sort와 Quick Sort가 주력인 세상인지라 시간복잡도가 제곱으로 나오는 것들은 그런가보다 하고 넘어갈 필요가 있다.

버블 정렬 :
인접한 두 개의 데이터를 비교하여 정렬하는 방식이다. 아주 간단하게 구현 할 수 있지만 매우 비효율적이다.

선택 정렬 :
전체 데이터 중 가장 작은 값을 선택해 맨 앞의 위치로 보낸다. 맨 앞의 정의는 진행되면서 점점 달라진다. 이 또한 간단하게 구현 할 수 있지만 비효율적이다.

삽입 정렬 :
데이터를 하나씩 삽입 하며 정렬한다. 정렬된 상태의 배열에서 새로운 데이터를 적절한 위치에 삽입한다. 최선의 경우에는 O(n)에 해결 할 수 있어서 효율적 일수도 있다. 안정성이 특징이지만 이 경우에도 최악의 경우 버블, 선택 정렬과 동일한 시간복잡도O(n^2)가 발생한다.

퀵 정렬 :
기준 값(pivot)을 정한 뒤, 작은 값과 큰 값을 나누어 정렬한다. 분할 정복의 대표적인 예이며, 시간 복잡도가 O(nlogn)으로 정렬 중에선 빠른 편에 속한다. 다만 최악의 경우 O(n^2)이 된다. 최선의 경우를 포기하면서 최악의 경우를 피하기 위해 피벗 선택을 랜덤 함수에 맡기는 경우도 있다.

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 피벗을 배열의 마지막 요소로 설정
    int i = low - 1; // 작은 요소의 위치를 추적

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]); // 작은 값을 왼쪽으로 이동
        }
    }
    std::swap(arr[i + 1], arr[high]); // 피벗을 올바른 위치로 이동
    return i + 1; // 피벗의 인덱스를 반환

병합 정렬 :
데이터의 배치를 반으로 나누어, 나눌 수 없을 때까지 나눈 후 각각 정렬 후 병합한다. 최악의 경우에도 O(nlogn)이 보장되나, 추가 메모리 사용이 요구 되는 단점이 있다.

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1; // 왼쪽 하위 배열 크기
    int n2 = right - mid;    // 오른쪽 하위 배열 크기

    // 임시 배열 생성
    int leftArr[n1], rightArr[n2];

    // 데이터 복사
    for (int i = 0; i < n1; i++)
        leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        rightArr[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left; // 초기 인덱스 설정

    // 병합
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    // 남은 요소 처리
    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}