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

김영찬님의 프로필 이미지

작성한 질문수

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

for문 초기값 설정 방식에 대한 시간 초과 질문 있습니다.

24.09.16 16:16 작성

·

25

0

for문의 i값의 설정 방식만 다르게 했을 뿐인데 시간 초과가 나는 점이 이해가 가지 않아 질문 드립니다.

A 코드 (시간 초과가 나지 않는 코드)

int solution(int n) {
    int answer = 0;
    int t = 1;
    
    while(t <= n) {
        int test = 0;
        
        for(int i=t; i<=n; i++){
            test += i;
            if(test == n) {
                answer++;
                break;
            }
            if(test > n){
                break;
            }
        }
        t++;
    }
    return answer;
}

B 코드 (시간 초과가 발생하는 코드)

int solution(int n) {
    int answer = 0;
    int t = 0;
    
    while(t <= n) {
        int test = 0;
        
        for(int i=t+1; i<=n; i++){
            test += i;
            if(test == n) {
                answer++;
                break;
            }
            if(test > n){
                break;
            }
        }
        t++;
    }
    return answer;
}

해당 코드들은 프로그래머스 숫자의 표현에 대한 코드 입니다.

강의와 관련없는 문제에 대해 질문 드리는 점 정말 죄송합니다.

하지만 아무리 원인을 파악하려해도 파악되지 않아 부득이하게 질문 드립니다.

해당 코딩 테스트 문제는 프로그래머스 숫자의 표현(하단 링크) 입니다.
https://school.programmers.co.kr/learn/courses/30/lessons/12924

답변 2

1

큰돌님의 프로필 이미지
큰돌
지식공유자

2024. 09. 17. 13:46

안녕하세요 영찬님 ㅎㅎ

강의 외의 문제에 대한 질문은 받지 않습니다.

다만, 이 두개의 코드의 차이점은 있지만 사실 그렇게까지 시간초과가 차이나는 코드라고 볼 수 없다고 생각합니다. 제생각에는 이 경우 문제가 너무 타이트하게 주어져서 그런 것 같습니다.

 

감사합니다.

김영찬님의 프로필 이미지
김영찬
질문자

2024. 09. 19. 13:32

무리한 질문에도 정성어린 답변 감사드립니다!

0

인프런 AI 인턴님의 프로필 이미지

2024. 09. 16. 16:21

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

두 코드에서 t의 초기값이 0일 때와 1일 때의 차이가 있지만, 기본적으로는 같은 내용을 실행하고 있어 보입니다. 그러나 시간 초과가 발생하는 이유는 두 코드의 반복문 조건이 미묘하게 다르기 때문입니다.

먼저 오류가 생기는 B 코드에서 문제점을 분석하겠습니다.

B 코드 요약:
- t의 초기값이 0입니다.
- for문 내부에서 it+1에서 시작합니다.

이 변경은 사실 A 코드의 형태와 논리적으로 동일하게 만드는데, t0일 때, i1부터 시작하여 n까지의 합을 검사합니다. 그렇다면 다음 반복에서 t1이 되어도, i는 다시 2부터 시작하여 동일한 연산을 수행합니다. 이는 불필요한 반복을 통한 중복 연산을 초래하여 시간을 더 소모하게 만들 수 있습니다.

반면,

A 코드 요약:
- t의 초기값이 1이며, it에서 시작합니다.
- it부터 시작합니다.

이는 t가 커질수록 i도 더 큰 값에서 시작하게 하여 중복된 연산을 피하게 됩니다.

결론적으로, A 코드의 경우 불필요한 중복 계산을 하지 않는 점이 B 코드보다 효율적입니다.

다음은 두 코드의 상관관계와 성능 차이를 이해하는 데 도움이 될 링크입니다.

유사 질문 링크:

  • 8-H 문제 질문
    • 해당 링크에서는 배열의 인덱스 범위 설정에 대해 다룹니다. 여기에서도 초기값 설정이 중요한 원인 중 하나로 작용하고 있습니다.
  • 7-F 1로 만들기 2 질문
    • 시간 초과 문제에 대해 효율적인 코드 작성에 관한 사항이 포함되어 있습니다.

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