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

2023-05-30T04:58:24.923Z

0

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

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

답변 잘 부탁드립니다.

0

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

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

1

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

>> 네 맞습니다.

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

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

1

안녕하세요 제하님 ㅎㅎ

요청하신 해설코드의 시간복잡도입니다. 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점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

0

큰돌님 안녕하세요! 위 질문과 관련된 게 아닌 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;
}

```

1

안녕하세요 제하님 ㅎㅎ

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

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

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

감사합니다.