[CodeTree] Ch5.시뮬레이션 2 - 최장 연속 부분 수열

 

DP(Dynamic Programming)의 유형인 LCS(Longest Common Subsequence) 최장 공통 부분 수열과 다른 유형입니다.

최장 연속 부분 수열은 구현 시뮬레이션 문제입니다. 

 

개념 : 숫자가 동일한 연속 부분 수열

수열이 (2, 2, 7, 7, 7, 7, 5, 7, 7) 다음과 같이 주어졌을 때, 연속해서 나오는 같은 숫자를 한 묶음이라 보면, 

(2, 2), (7, 7, 7, 7), (5), (7, 7) 총 4개 묶음이 나옵니다.

 

새로운 묶음이 생겨나는 순간에 개수를 세줍니다.

새로운 묶음이 생겨나는 기준은 이웃한 이전 원소의 값과 현재의 값이 다를 때입니다. a[i] != a[i -1] 

 

|| OR 연산자

if( A || B)에서 A가 true이면 뒤의 B는 계산하지 않고 바로 {} 명령문들을 실행합니다. 따라서 A 에는 에러가 발생하지 않을 조건을 두어야합니다.

 

Warmup : 연속되는 수 2 

Warmup 연속되는 수 2

입출력 및 복잡도

https://www.codetree.ai/ko/trails/complete/curated-cards/intro-continuous-number2/description

연속되는 수 2 설명 | 코드트리

 

내풀이

풀이 1 : 배열 인덱스 1번째부터 탐색

놓친 부분 

• 모든 숫자가 같을 때, 연속된 개수를 ret(최종값)에 업데이트를 하지 않음
• 숫자의 개수가 최소 1개일 때 예외케이스 누락 -> 1일 때는 for반복문으로 이웃 비교를 하면 인덱스 에러가 발생함. 

해설코드와 다른점 

• 해설 코드는 수열의 0번째부터 시작하여 if문에 i == 0일 때 a[i-1] 이전값을 참조하는 것을 막음. (인덱스 에러 방지) 

 

 

풀이 2 : 배열 인덱스 0번째부터 탐색

#include<bits/stdc++.h>
using namespace std;
int n, ret = -1e9, arr[1004], cnt=1;
int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    for(int i = 0; i < n; i++) {
        if(i == 0 || arr[i] != arr[i - 1]) {
            ret = max(ret, cnt); cnt = 0;
        }
        cnt++; // 연속으로 같은 숫자를 더한다 
    }
    // 모두 다 같을 때 처리하는 방법 
    ret = max(ret, cnt);
    cout << ret << '\n';
    return 0;
}

 

해설코드 

#include <iostream>
#include <algorithm>

#define MAX_N 1000

using namespace std;

int n;
int arr[MAX_N];

int main() {
    // 입력
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    
    // 연속하여 동일한 숫자가 나오는 횟수를 구해보며,
    // 그 중 최댓값을 갱신합니다.
    int ans = 0, cnt = 0;
    for(int i = 0; i < n; i++) {
		// Case 1
        if(i >= 1 && arr[i] == arr[i - 1])
            cnt++;
		// Case 2
        else
            cnt = 1;
        
        ans = max(ans, cnt);
    }
    
    cout << ans;
    return 0;
}

 

 

 

Challenge : 연속되는 수 3

Challenge 연속되는 수3

입출력 및 복잡도

 

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-continuous-number3/description

연속되는 수 3 설명 | 코드트리

 

`증가하는 연속 부분 수열`

연속하는 부분 수열 중 원소의 숫자가 계속 증가하는 수열

 

내풀이

앞에서 배운 틀을 유지하되, "원소의 숫자가 증가하는 수열"만 적용해 코드를 작성했더니 해설코드와 똑같이 나왔습니다.

개념설명과 쌍을 이루는 기본문제와 여러 Challenge문제가 변형이 잘 되는 것 같습니다.

#include<bits/stdc++.h>
using namespace std;
int n, arr[1004], cnt, ret = -1e9;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >>  n; 
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    for(int i = 0; i < n; i++) {
        if(i >= 1 && arr[i] > arr[i-1]) cnt++;
        else cnt = 1;
        ret = max(ret, cnt);
    }
    cout << ret;
    return 0;
}

 

Challenge : 연속되는 수 4

Challenge : 연속되는 수 4

입출력 및 복잡도

 

내풀이

#include<bits/stdc++.h>
using namespace std;
int n, arr[1004], cnt, ret = -1e9;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >>  n; 
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    for(int i = 0; i < n; i++) {
        if(i >= 1 && arr[i] > arr[i-1]) cnt++;
        else cnt = 1;
        ret = max(ret, cnt);
    }
    cout << ret;
    return 0;
}

해설코드 

#include <iostream>
#include <algorithm>

#define MAX_N 1000

using namespace std;

int n;
int arr[MAX_N];

int main() {
    // 입력
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    
    // 연속하여 동일한 숫자가 나오는 횟수를 구해보며,
    // 그 중 최댓값을 갱신합니다.
    int ans = 0, cnt = 0;
    for(int i = 0; i < n; i++) {
		// Case 1
        if(i >= 1 && arr[i] > arr[i - 1])
            cnt++;
		// Case 2
        else
            cnt = 1;
        
        ans = max(ans, cnt);
    }
    
    cout << ans;
    return 0;
}

 

Test : T를 초과하는 연속 부분 수열

 

Test: T를 초과하는 연속 부분 수열

입출력 및 복잡도

내풀이

풀이시간 1시간

 

접근 방법

현재 탐색하는 원소가 T보다 큰 경우와 T보다 작거나 같은 경우로 나눠 연속 부분 수열을 구한다

 

막힌 지점 

• 이전 문제들처럼 이전 요소간의 비교가 필요하다고 생각해, arr[i] > t && arr[i-1] > t 일 때 cnt++ 하는 코드 작성. 이는 이전 요소가 arr[i] 현재 탐색하는 시점일 때 cnt++한 것을 중복으로 세어 정답보다 많은 값이 나오게 됨 
• 현재 탐색하는 원소가 t 보다 큰 것을 카운팅하는 것이 목적이고, 이전 요소가 t보다 큰 것은 확인할 필요가 없음. 현재 탐색하는 원소가 t보다 작거나 같을 때 카운팅을 초기화 하면 됨

놓친 지점 

• 테스트 케이스 `4 1 3 3 3 3` 일 때, 이전 문제처럼 첫 카운트 변수 (cnt )를 1로 초기화 하면 안됨.
  • 이전에는 조건이 숫자이기만 하면 1개는 카운팅 되었고, 이 문제는 T보다 클 때만, 연속 부분 수열이 되기 때문

#include <bits/stdc++.h>
using namespace std;
int n, t, arr[1004], cnt , ret= -1e9;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> t; 
    for(int i = 0; i< n; i++) cin >> arr[i];

    for(int i = 0; i < n; i++) {
        if(arr[i] > t) {
            cnt++;
        }
        else cnt = 0;
        ret = max(ret, cnt);
    }

    cout << ret << '\n';
    return 0;
}

 

해설코드

#include <iostream>
#include <algorithm>

#define MAX_N 1000

using namespace std;

int n, t;
int arr[MAX_N];

int main() {
    // 입력
    cin >> n >> t;
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    
    // 연속하여 t보다 큰 숫자가 나오는 횟수를 구해보며,
    // 그 중 최댓값을 갱신합니다.
    int ans = 0, cnt = 0;
    for(int i = 0; i < n; i++) {
		// Case 1
        if(arr[i] > t)
            cnt++;
		// Case 2
        else
            cnt = 0;
        
        ans = max(ans, cnt);
    }
    
    cout << ans;
    return 0;
}

코드트리 청약 챌린지 진행중입니다!

같이 코테 꾸준히 공부해봅시다

https://www.codetree.ai/ko/no-free-lunch-2026/?ref=T38PMZ

3년 만에 돌아온, 코드트리 청약 통장 챌린지 | 코드트리