인구 이동 문제 시간복잡도 질문

작성한 질문수 29

0

안녕하세요 재윤님 ㅎㅎ

네 맞습니다. 정확합니다. 다음 코드 처럼 되는거니까요.

    // 2000
    while(true){
        bool flag =0;
        fill(&visited[0][0], &visited[0][0] + 54 * 54, 0);
        // 50 * 50
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){

다만 2500부분이요. 최악의 경우의 수를 생각해 볼 필요는 있습니다.

자 이중 for문으로 2500번 순회합니다. 이 때 dfs가 작동이 되죠? 최악의 경우의 수 : dfs로 처음에 모든 정점을 간다고 하고 그 다음부터는 visited로 색칠되어 if문에 안걸린다고 해볼게요.

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(!visited[i][j]){

그렇게 되면

2500 + 1 + 1 + ...... 가 되어

2500 + 1 * 2499 가 되겠죠?

즉, 약 5000이 됩니다.

아무리 if문으로 걸러서 dfs가 작동이 안된다고 한들. 해당 부분의 로직은 계산에 들어가게 됩니다.

시간복잡도를 따질 때 if continue를 해도 시간복잡도 계산에 들어가는 것을 알려드리기 위해 말씀을 드려봤습니다.

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

또한 강의가 맘에 드셨다면 좋은 수강평과 별점 5점 꾹 부탁드립니다. 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.