4-P질문입니다

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

4-P

해결된 질문

작성

수정됨

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int n,ret;

vector<int> v;
stack<int> st;
         
int check(int i,vector<int> &v){
   int cnt=0;
   int mx =0;
   for(int j = i+1; j<n; j++){
      if(v[j]<= v[i]){
         if(v[j]>=mx && v[i]>=mx)
         {  cnt++;                         
            if(j ==  i+1) mx = v[j];  
            else mx = max(mx,v[j]);
         }
         else{
            break;
         }
      }
      else if(v[j]>v[i]){   
         cnt++;
         break;
      }
   }
   return cnt;
}

int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
   cin>>n;
   for(int i =0; i<n;i++){
      int num;
      cin>>num;
      v.push_back(num);
   }
   for(int i=0;i<n-1;i++){
      ret  += check(i,v);
   }
   cout<<ret;
   return 0;
}

이 코드에서 예제는 통과하지만 틀리는 이유를 잘 모르겠습니다.
처음에는 스택을 하려고 했다가 매번 특정한 위치에 접근하는 것이 스택은 안되기에

무식한 방법으로 풀어보는 시도를 위해 vector를 이용해 보았습니다

(번외 질문

반례는 순수 노가다를 통해서 찾는건가요? 아님 다른 방법이 있을까요?

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 ㅎㅎ

이 문제 지문을 보시면

첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)

-> n의 최대 수가 50만입니다. 수강생님 코드는 50만 * 50만 짜리 큰 시간복잡도를 가지는 코드가 되서 -> 통과가 안되는 것 같습니다. 좀 더 효율적인 방법을 고려해주셔야 합니다.

반례는 순수 노가다를 통해서 찾는건가요? 아님 다른 방법이 있을까요?

-> 음... 노가다긴 하지만... 팁을 드리자면 다음과 같습니다.

주어진 예제로부터 보다 끝점, 극한, 극저점 등을 생각하면서 반례를 뽑으시면 됩니다.

예를 들어 1, 2, 3, 4, 5 가 예시라면 1, 1, 1, 1, 1 또는 5, 5, 5, 5, 5 이렇게 가거나 문제 범위가 0 ~ 10000이라면 0, 0, 0, 0, 0 이렇게 -> 10000, 10000, 10000, 1000 ... 이런식으로 문제범위로 봤을 때 보다 끝점을 기반으로 진행해주시면 그래도 반례의 80%정도는 먹고 들어가는 것 같습니다.

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

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

감사합니다.

강사 큰돌 올림.

인프런 AI 인턴

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

제공해주신 코드에서 발생할 수 있는 문제와 개선 방안을 설명드리겠습니다. 현재 코드는 특정한 위치에서부터 시작해 오른쪽으로 탐색하면서 조건에 맞는 요소를 세는 방식으로 작성되어 있습니다.

문제 분석

시간 복잡도: 현재 코드의 시간 복잡도는 O(n^2)로, n의 크기가 커질 경우 시간이 많이 소요될 수 있습니다. 각 원소마다 check 함수를 호출하여 전체 벡터를 탐색하기 때문입니다.
논리적인 오류: mx와 cnt를 설정하고 업데이트하는 부분에서 논리적인 오류가 있을 수 있습니다. 조건( v[j] <= v[i]와 v[j] >= mx && v[i] >= mx)이 잘못 설정되었거나 중복 체크할 수 있는 경우가 있을지 고려해 보셔야 합니다.
중복된 증가 및 감소에 대한 검토: 조건에 따라 cnt 가 증가하는 동안 중복 요소가 포함될 가능성이 있습니다. 이 경우 중복 계산을 피할 수 있도록 로직을 다듬어야 합니다.

개선 방안

효율적인 자료구조 사용: 문제가 더 쉽게 해결될 수 있는 다른 자료구조를 사용해볼 수 있습니다. 스택의 사용을 고려하셨다고 하셨지만, 현재 상황에서는 슬라이딩 윈도우나 투 포인터 기법이 유효할 수 있습니다.
최적화된 접근법 고려: 각 위치에서 탐색을 시작할 때, 예를 들어 배열을 오른쪽에서 왼쪽으로 패스하여 업데이트하는 방식으로 이미 계산된 정보를 재활용하는 것이 필요할 수도 있습니다.

반례 찾기

반례는 문제의 조건과 예제 케이스로 로그에서 드러나지 않는 특이 패턴을 찾는 과정입니다. 이를 위해:

경계값 검토 및 다양한 입력 크기 활용: 최소값, 최대값 그리고 변화가 많은 경우를 다 고려하며 테스트합니다.
분할 및 정복: 각 부분을 단계별로 출력하여 현재 체크한 패스가 어디서 제대로 작동하지 않는지 확인합니다.

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