3 - l 시간초과

작성자 없음

0

안녕하세요 ㅎㅎ

        for(char c : v){
            if(c == arr[ny][nx]){
                flag = 1;
            }
        }

지금 보시면 계속해서 v를 체크해야 되기 때문 이부분에서 O(N)의 시간복잡도가 발생합니다.

하지만 visited를 하게 되면 시간복잡도가 탐색이 아닌 참조이기 때문에 O(1)의 시간복잡도가 발생되므로 이 차이 때문에 시간초과가 해결되는 것입니다.

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

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

감사합니다.

강사 큰돌 올림. 

0

안녕하세요, 인프런 AI 인턴입니다.

kkim360님의 질문은 함수의 매개변수로 vector를 직접 넘길 때 발생하는 시간 초과 문제와 관련이 있습니다. 이러한 시간 초과는 주로 크기가 큰 데이터 구조를 값으로 넘길 때 복사 비용 때문에 발생할 수 있습니다.

vector를 함수 매개변수로 직접 넘길 경우, 함수를 호출할 때마다 해당 vector의 모든 원소가 복사되므로 시간 복잡도가 크게 증가할 수 있습니다. 이를 해결하기 위해서는 vector 대신 참조자(&)를 사용하여 vector를 넘겨주는 것이 일반적인 해결책입니다. 참조자를 사용하면 원본 데이터를 복사하지 않고 직접 참조하기 때문에 성능 문제를 효과적으로 감소시킬 수 있습니다.

비슷한 문제 상황과 그에 대한 해결 방법을 설명하는 기존 답변이 있어 링크를 참조해 드릴게요:
- 시간초과에서는 비트마스크와 dfs를 이용하여 비슷한 상황에서의 시간 초과 문제를 다룹니다. 여기서는 vector 대신 비트마스킹을 사용하여 해결책을 제공하고 있습니다.

비록 이 예시가 정확히 kkim360님의 경우와 일치하지는 않으나, 참조에 의한 호출(call by reference)과 값에 의한 호출(call by value)의 차이에 대해 이해하는 데 도움이 될 것입니다. 참조에 의한 매개변수 전달을 통해 성능 문제를 해결할 수 있는 경우가 많기 때문입니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.