1주차 문제들의 시간 복잡도 확인

네 그렇습니다! 질문이 모호한 면이 있었군요. 댓글로도 남기겠지만, 질문도 다시 수정하겠습니다.

그리고, 강의 잘 듣고 있습니다. c++로 코테 준비가 처음이라 걱정이 많았지만, 좋은 코드이고, 좋은 문제들을 미리 뽑아주셨고, 미리 교안도 있어서 시간을 많이 아낄 수 있는 것 같습니다.
이걸로 작년 초에 코테 준비했었으면 헤매는 일이 없었을 것 같은데 많은 아쉬움이 있습니다.

답변 잘 부탁드립니다.

그렇다면 시간복잡도 작성 형식에 따라 작성하면 O(nCr)로 입력하면 되나요?

예를 들어 5_C_3 이라고 할 때 5! / (3! * 2!) = 10 이므로 O(10) 으로 생각하면 될까요?

그렇다면 시간복잡도 작성 형식에 따라 작성하면 O(nCr)로 입력하면 되나요?

>> 네 맞습니다.

예를 들어 5_C_3 이라고 할 때 5! / (3! * 2!) = 10 이므로 O(10)

>> 변수가 아니라 입력값으로 들어가게 되면 그렇게 되는게 맞습니다. 다만, 10이라고 하시면 됩니다. O(10)이라고 하지는 않습니다.

안녕하세요 제하님 ㅎㅎ

요청하신 해설코드의 시간복잡도입니다. O()는 중복되서 제외했으며 해당 부분 확인해보시고 궁금하신 부분이 있으시면 질문주세요.

A : max(nlogn, nPr)

B : n

C : 1

D : n

E : 1

F : n

G : n

H : n

I : m * logn

J : n

K : 1

L : n^2

M : n * s.size()

N : logb

O : 알 수 없음.(얼마나 나머지 연산을 해야 하는지는 미지수입니다. )

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

큰돌님 안녕하세요! 위 질문과 관련된 게 아닌 2주차 개념과 관련하여 질문을 남기고자 합니다.

저는 bfs는 queue를 사용하고, dfs는 stack을 사용한다고 이해해왔는데요.

2주차 개념 블로그 내용 정리를 보면 bfs에서만 queue를 사용하고, dfs에서는 사용안하시고 코드를 짜신 걸 이해했습니다.

그리하신 이유는 stack을 사용하지 않고 짜는게 더 코드가 짧아서 그리하신 건가요?

제가 stack을 사용하여 짠 dfs 코드는 다음과 같습니다.
종화는 방구쟁이야! 를 stack을 사용해서 해봤습니다.

```cpp

#include <bits/stdc++.h>
using namespace std;
const int max_n = 104;
int m, n, adj[max_n][max_n], visited[max_n][max_n], y, x, ans;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

void dfs(int y, int x)
{
    cout << y << " : " << x << '\n';
    visited[y][x] = 1;
    stack<pair<int, int>> s;
    s.push({y, x});
    while (s.size())
    {
        tie(y, x) = s.top();
        s.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n)
                continue;
            if (adj[ny][nx] && !visited[ny][nx])
            {
                visited[ny][nx] = 1;
                s.push({ny, nx});
            }
        }
    }

    return;
}

int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cin >> adj[i][j];
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            if (adj[i][j] && visited[i][j] == 0)
            {
                ans++;
                dfs(i, j);
            }
    }
    cout << ans << '\n';
    return 0;
}

```

안녕하세요 제하님 ㅎㅎ

2주차 개념 블로그 내용 정리를 보면 bfs에서만 queue를 사용하고, dfs에서는 사용안하시고 코드를 짜신 걸 이해했습니다.
그리하신 이유는 stack을 사용하지 않고 짜는게 더 코드가 짧아서 그리하신 건가요?

>> DFS + stack으로도 할 수 있지만 stack을 사용하지 않아도 해당 로직을 구현할 수 있기 때문에 stack을 사용하지 않는게 좋습니다. 네 맞습니다. 코드가 더 짧고 그럼으로써 복잡성도 낮아집니다.

그리고 탐색만 하는 알고리즘이라면 BFS보다는 stack을 사용하지 않은 dfs를 추천드립니다.

감사합니다.