3-K 시간 초과ㅜㅜ

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-K와 문제의 단순화

해결된 질문

작성

수정됨

http://boj.kr/f99ceee53c3244798a75cdf977eaa63b

메모리 초과를 해결하니 시간초과가 뜨는데 어디가 문제인 걸까요ㅠㅠ 중복 탐색이 이루어지는 걸까요??

강의를 보고도 풀기가 어렵네요ㅜㅜ

도와주시면 감사하겠습니다ㅠ

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 LK님 ㅎㅎ

먼저 이문제는 타이트한 문제입니다. 하나라도 비효율적인 부분이 있으면 안되는 문제라는것을 말씀드립니다.

그렇다면, 비효율적인 부분만 볼게요

            if(lake[i][j] == '.' || lake[i][j] == 'L')
            {
                for(int d = 0; d < 4; d++)
                {
                    int ni = i + dy[d];
                    int nj = j + dx[d];
                    if(ni >= 0 && ni < N && nj >= 0 && nj < M && lake[ni][nj] == 'X')
                    {
                        water.push_back({i, j});
                        break;
                    }

먼저 물을 찾는데 왜 ni, nj가 필요한가요?

        while(!water.empty())
        {
            int y = water.back().first;
            int x = water.back().second;
            water.pop_back();
           // cout << "water = " << y << ", " << x << "\n";

            for(int i = 0; i < 4; i++)
            {
                int ny = y + dy[i];

지금 보시면 물의 정점들을 기반으로 4방향으로 모두 다 탐색하고 있는데요. ㅎㅎ

정점 a마다 4방향 순회가 도니까 비효율적이라고 볼 수 있습니다.

이 부분들을 고쳐보시겠어요?

감사합니다.

인프런 AI 인턴

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

시간 초과 문제는 보통 프로그램이 작성된 알고리즘이 효율적이지 않아서 허용된 시간 내에 작업을 완료하지 못할 때 발생합니다. 이는 주로 반복문이 너무 많이 돌거나, 알고리즘의 시간 복잡도가 높을 때 문제가 될 수 있습니다.

시간 초과와 관련된 유사한 문제 해결 사례를 몇 가지 소개해드리겠습니다:

3-K 메모리 초과: 이전에 메모리 초과 문제로 지적되었던 답변에서 메모리 관리 방법을 최적화하는 방법을 언급하고 있습니다. 메모리 최적화가 시간에도 영향을 미칠 수 있으므로 참고하시면 좋습니다.
3-I 메모리 초과나는 이유를 모르겠습니다.: 이 질문에서 강사님은 정점을 방문할 때의 처리가 미흡함을 지적하며 방문 처리를 하지 않을 경우 큐에 불필요한 정점이 계속해서 쌓이게 되어 시간 및 메모리 문제가 발생할 수 있다고 설명하셨습니다. 방문 처리를 철저히 하여 불필요한 연산이 발생하지 않도록 주의하세요.
2-C 메모리 초과 이슈: 이 질문에서는 DFS와 BFS를 사용할 때 재귀 깊이 관리에 대한 언급이 있습니다. 특정 알고리즘에서는 단순 반복보다 이런 기본적인 자료 구조의 효율적인 사용이 해결의 열쇠가 될 수도 있습니다.

시간을 절약하기 위해, 중복 연산이나 필요 이상으로 많은 데이터를 저장하지 않도록 최적화하는 것이 중요합니다. 특히, 알고리즘이 중복 계산하는 부분이 있는지 확인하고, 불필요한 루프를 제거하는 것이 좋습니다.

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

인프런 커뮤니티 질문&답변

3-K 시간 초과ㅜㅜ