CS 스터디 12 주차

빅오 표기법에 대해서 설명해주세요

: 빅오 표기법(Big O Notation)은 알고리즘의 시간 복잡도를 나타내는 수학적인 표기법 중 하나로, 알고리즘의 성능을 분석하고 비교하기 위해 사용됩니다.

특징

시간복잡도에 미미한 영향을 주는 것들은 배제하고 표기된다.

• 상수항을 무시
  : 어떤 알고리즘이 O(N+5)의 복잡도를 가졌으면 상수를 생략해 O(N)으로 표기한다.

• 계수도 무시
  : 어떤 알고리즘이 O(3N)의 복잡도를 가졌으면 계수를 생략해 O(N)으로 표기한다.

• 최고차항만 표기
  : 어떤 알고리즘이 O(3N^3+2N^2+N+5)의 복잡도를 가졌으면 O(N^3)으로 표기한다.

int a = 0;
for (i = 0; i < N; i++) {
    for (j = N; j > i; j--) {
        a = a + i + j;
    }
} 
// N^2

int a = 0, i = N;
while (i > 0) {
    a += i;
    i /= 2;
}
// log N

int count = 0;
for (int i = N; i > 0; i /= 2) {
    for (int j = 0; j < i; j++) {
        count += 1;
    }
}
// N (첫 루프에서 덜 돌아가는 만큼, 두 번째 루프에서 반복됩니다.)


int i, j, k = 0;
for (i  = n/2; i <= n; i++) {
    for (j = 2; j <= n; j = j * 2) {
        k = k + n/2;
    }
}
// NLogN

int gcd(int n, int m) {
        if (n%m ==0) return m;
        if (n < m) swap(n, m);
        while (m > 0) {
            n = n%m;
            swap(n, m);
        }
        return n;
}

# 조건 : n 은 m 보다 항상 큽니다.
// LogN


int j = 0;
for(int i = 0; i < n; ++i) {
    while(j < n && arr[i] < arr[j]) {
        j++;
    }
}
// N

피보나치 수열 구현 방식 세 가지를 말해보시고, 시간복잡도와 공간복잡도를 설명해 주세요.

재귀(Recursive) 방식

• 시간복잡도: O(2^n)
  : 재귀적으로 호출되는 함수가 중복되기 때문에 지수적으로 증가합니다.
• 공간복잡도: O(n)
  : 재귀 호출 스택에 n개의 호출 프레임이 쌓이게 되므로 공간복잡도는 O(n)입니다.

반복문(Iterative) 방식

• 시간복잡도: O(n)
  : 반복문을 사용하여 모든 피보나치 수를 계산하기 때문에 입력 크기 n에 선형적으로 비례합니다.
• 공간복잡도: O(n)
  : 피보나치 수를 저장하기 위한 배열이 필요하므로 공간복잡도도 O(n)입니다.

메모이제이션(Dynamic Programming) 방식:

• 시간복잡도: O(n)
  : 중복 계산을 피하기 위해 이전에 계산한 값을 메모이제이션하여 효율적으로 계산합니다.
• 공간복잡도: O(n)
  : 메모이제이션을 위한 딕셔너리에 n개의 값이 저장되므로 공간복잡도는 O(n)입니다.

BFS/DFS 차이는 무엇인가요?

탐색 순서

• BFS
  : 너비 우선 탐색은 루트(시작) 노드에서 시작하여 현재 노드와 인접한 모든 노드를 우선 탐색한 후, 그 다음 레벨의 노드들을 탐색합니다. 즉, 레벨 단위로 탐색을 진행하며, 가까운 노드부터 순서대로 탐색합니다.
• DFS
  : 깊이 우선 탐색은 현재 노드에서 시작하여 다음으로 이동할 노드를 선택하고, 선택한 노드에 대해 계속해서 깊이 탐색을 진행합니다. 이는 특정 경로를 완전히 탐색한 후 다른 경로로 이동하는 방식입니다.

데이터 구조

• BFS
  : 큐(Queue) 자료 구조를 사용합니다. 먼저 들어온 요소를 먼저 처리하기 때문에 너비 우선이라고 부릅니다.
• DFS
  : 스택(Stack) 자료 구조나 재귀 함수 호출을 사용합니다. 깊이 우선이라고 부르는 이유는 한 경로를 따라 최대한 깊게 파고들어가기 때문입니다.

완전 탐색

• BFS
  : 너비 우선 탐색은 최단 경로를 찾는데 유용합니다. 그리고 모든 노드를 탐색하는 완전 탐색에도 적합합니다.
• DFS
  : 깊이 우선 탐색은 모든 경로를 탐색하는 완전 탐색에 유용합니다. 또한, 특정 조건에 따라 경로를 찾거나 그래프의 구조를 조사하는 데도 사용됩니다.

프림 알고리즘에 대해서 설명해 주세요.

프림(Prim) 알고리즘은 그래프 이론에서 최소 신장 트리(Minimum Spanning Tree)를 구성하는 데 사용되는 그리디 알고리즘 중 하나입니다. 최소 신장 트리는 연결된 그래프에서 모든 노드를 연결하는 트리 중 가중치의 합이 최소인 트리를 말합니다.

프림 알고리즘의 동작 방식은 다음과 같습니다:

• 임의의 시작 노드를 선택하여 최소 신장 트리를 초기화합니다.

• 선택된 노드로부터 다른 노드로 향하는 간선 중에서 가장 작은 가중치를 가진 간선을 선택합니다.

• 선택한 간선으로 연결된 노드를 최소 신장 트리에 추가합니다.

• 반복해서 최소 가중치 간선을 선택하고 해당 간선으로 연결된 노드를 최소 신장 트리에 추가합니다.
  이 과정은 모든 노드가 최소 신장 트리에 포함될 때까지 반복합니다.

프림 알고리즘의 특징 및 시간복잡도:

프림 알고리즘은 그리디 알고리즘으로, 각 단계에서 현재의 최소 신장 트리에 가장 가까운 노드를 선택합니다.
프림 알고리즘은 우선순위 큐(Priority Queue)를 사용하여 현재 최소 가중치 간선을 효율적으로 선택합니다.
시간복잡도는 일반적으로 O(V^2)이지만, 우선순위 큐를 사용하면 O(E + V log V)로 최적화할 수 있습니다. 여기서 V는 노드의 수, E는 간선의 수를 나타냅니다.
프림 알고리즘은 밀집 그래프(간선의 수가 많은 경우)에서 효과적이며, 크루스칼 알고리즘과 함께 최소 신장 트리를 구성하는 데 사용됩니다.
프림 알고리즘은 최소 신장 트리를 찾는 효율적인 방법 중 하나이며, 가중치가 있는 그래프에서 연결된 모든 노드를 연결하는 데 사용됩니다.

다익스트라 알고리즘에 대해서 설명해 주세요.

다익스트라 알고리즘(Dijkstra's Algorithm)은 하나의 출발 노드에서 다른 모든 노드로 가는 최단 경로를 찾는 그래프 알고리즘 중 하나입니다. 주로 가중치가 있는 그래프에서 사용되며, 음수 가중치를 포함하지 않는 경우에만 적용 가능합니다. 다익스트라 알고리즘은 그리디 알고리즘의 한 종류로, 각 단계에서 현재까지 발견된 최단 경로를 가진 노드를 선택하여 새로운 노드로부터의 최단 경로를 계산합니다.

다익스트라 알고리즘의 동작 방식은 다음과 같습니다:

• 출발 노드에서부터의 거리를 초기화합니다. 출발 노드의 거리는 0으로 설정하고,
  다른 모든 노드의 거리는 무한대로 설정합니다.

• 현재까지 발견된 최단 경로를 가진 노드를 선택합니다. 초기에는 출발 노드가 선택됩니다.

• 선택된 노드로부터 인접한 노드들로 가는 간선을 검사하고,
  현재까지의 거리와 새로운 간선의 가중치를 고려하여 더 짧은 거리를 찾으면 해당 노드의 거리를 업데이트합니다.

• 모든 노드를 방문할 때까지 2단계와 3단계를 반복합니다.

다익스트라 알고리즘의 특징 및 시간복잡도:

다익스트라 알고리즘은 음수 가중치를 포함하지 않는 경우에 사용 가능합니다. 음수 가중치를 가진 간선이 있을 경우 벨만-포드 알고리즘이나 다른 알고리즘을 사용해야 합니다.
다익스트라 알고리즘은 간선의 수(E)와 노드의 수(V)에 비례하는 시간복잡도를 가집니다. 일반적으로 우선순위 큐(Priority Queue)를 사용하여 최적화하면 시간복잡도는 O((E + V)logV)가 됩니다.
다익스트라 알고리즘은 최단 경로를 찾는 데 사용되며, 네트워크 라우팅, GPS 경로 탐색, 네트워크 최적화 등 다양한 응용 분야에서 활용됩니다.
다익스트라 알고리즘은 출발 노드로부터의 최단 경로를 찾는 것이 목표이므로, 모든 노드 사이의 최단 경로를 계산하려면 출발 노드를 각각 변경하여 실행해야 합니다.
다익스트라 알고리즘은 가중치가 있는 그래프에서 최단 경로 문제를 효과적으로 해결하는 중요한 알고리즘 중 하나이며, 실제로 네트워크 및 경로 계획에 많이 활용됩니다.

은행원 알고리즘에 대해서 설명해 주세요.

은행원 알고리즘(Banker's Algorithm)은 운영체제와 컴퓨터 시스템에서 프로세스의 자원 할당과 관련된 안전한 방법을 찾는 데 사용되는 알고리즘입니다. 이 알고리즘은 다중 프로세스 시스템에서 교착상태(Deadlock)를 방지하고자 개발되었습니다. 교착상태는 둘 이상의 프로세스가 서로의 자원을 기다리며 진행하지 못하는 상태를 말합니다.

은행원 알고리즘은 다음과 같은 원칙에 기반하여 동작합니다:

• 시스템은 모든 프로세스에 대한 최대 필요 자원을 알고 있어야 합니다.
  즉, 각 프로세스가 최대로 요청할 수 있는 자원의 수를 미리 정의해야 합니다.

• 시스템은 현재 사용 중인 자원과 남아 있는 자원을 추적합니다.

• 프로세스가 자원을 요청할 때, 시스템은 해당 요청이 안전한지를 검사합니다.
  안전한 요청인 경우에만 자원을 할당합니다.

• 안전한 요청을 판단하기 위해, 은행원 알고리즘은 두 가지 중요한 데이터 구조를 사용합니다:

• 최대 필요 자원(Maximum Need)
  : 각 프로세스마다 최대로 필요한 자원의 수를 저장합니다. 이 정보는 시스템이 어떤 프로세스에게 자원을 할당해도 교착상태를 방지하기 위해 사용됩니다.

• 사용 가능한 자원(Available Resources)
  : 현재 시스템에서 사용 가능한 자원의 수를 나타냅니다. 이 정보를 통해 시스템은 안전한 자원 할당을 판단합니다.

은행원 알고리즘의 동작 단계는 다음과 같습니다:

• 프로세스가 자원을 요청하면 요청한 자원의 수를 확인하고 최대 필요 자원과 비교합니다.

• 요청한 자원이 최대 필요 자원보다 작거나 같고,
  요청한 자원과 사용 가능한 자원의 합이 안전 상태를 유지한다면,
  자원을 할당하고 안전한 상태로 간주합니다.

• 프로세스가 자원을 사용을 마치면, 사용한 자원을 반환하고 사용 가능한 자원을 증가시킵니다.

• 교착 상태가 발생하지 않도록 안전한 자원 할당이 계속 가능한지 확인하고,
  가능하다면 자원을 할당하고 아니면 대기합니다.

제한사항

• 가장 중요한 제한사항은 모든 프로세스의 최대 필요 자원을 사전에 알아야 한다

• 자원의 요청과 반환이 정확하게 추적되어야 한다