[COS Pro 1급 Python] 2차 기출문제 5) 언제까지 오르막길이야..?!

정은·2023년 8월 10일

COS Pro 1급 Python python 자격증

COS Pro 1급

목록 보기

16/26

문제 5)

자연수가 들어있는 리스트가 있습니다. 이 리스트에서, 숫자가 연속해서 증가하는 가장 긴 구간의 길이를 구하려 합니다. 단, 바로 전 숫자와 현재 숫자가 같은 경우는 증가한 것으로 보지 않습니다.

예를 들어 리스트에 순서대로 [3, 1, 2, 4, 5, 1, 2, 2, 3, 4]가 들어있는 경우, [1, 2, 4, 5]가 들어있는 구간이 숫자가 연속해서 증가한 가장 긴 구간이며, 길이는 4입니다.

자연수가 들어있는 리스트 arr가 매개변수로 주어질 때, 숫자가 연속해서 증가하는 가장 긴 구간의 길이를 return 하도록 solution 함수를 완성해주세요.

매개변수 설명

자연수가 들어있는 리스트 arr가 solution 함수의 매개변수로 주어집니다.

arr의 길이는 2 이상 200,000 이하입니다.
arr의 원소는 1 이상 1,000,000 이하의 자연수입니다.

return 값 설명

숫자가 연속해서 증가하는 가장 긴 구간의 길이를 return 해주세요.

길이가 2 이상인 증가하는 구간이 없다면 1을 return 해주세요.

예시

arr	return
[3, 1, 2, 4, 5, 1, 2, 2, 3, 4]	4

예시 설명

숫자 [1, 2, 4, 5]가 들어있는 구간이 숫자가 연속해서 증가하는 가장 긴 구간이며, 길이는 4입니다.

현재 숫자가 바로 이전 숫자와 같은 경우에는 증가했다고 보지 않습니다. [1, 2, 2, 3, 4]가 들어있는 구간은 [2, 2]가 연속해서 증가한 부분이 아니므로, [1, 2]가 들어있는 구간과 [2, 3, 4]가 들어있는 구간으로 나누어야 합니다.

주어진 문제 5) 코드

#다음과 같이 import를 사용할 수 있습니다.
#import math

def solution(arr):
    #여기에 코드를 작성해주세요.
    answer = 0
    return answer

#아래는 테스트케이스 출력을 해보기 위한 코드입니다.
arr = [3, 1, 2, 4, 5, 1, 2, 2, 3, 4]
ret = solution(arr)


#[실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
print("solution 함수의 반환 값은", ret, "입니다.")

Solution

주어진 문제 5) Solution 코드

이번엔 빈칸 채우기 문제가 아니라 함수 전체를 작성하는 문제이다.

#다음과 같이 import를 사용할 수 있습니다.
#import math

def solution(arr):
    #여기에 코드를 작성해주세요.
    answer = 0
    count = 1
    for index in range(1, len(arr)):
        if arr[index - 1] < arr[index]:
            count += 1
        else:
            count = 1

        answer = max(answer, count)
    return answer

#아래는 테스트케이스 출력을 해보기 위한 코드입니다.
arr = [3, 1, 2, 4, 5, 1, 2, 2, 3, 4]
ret = solution(arr)


#[실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
print("solution 함수의 반환 값은", ret, "입니다.")

for문을 이용해서 arr 리스트의 항목을 1번 인덱스부터 가져와 이전 항목과 비교
현재 항목이 이전 항목보다 크면 증가 구간의 크기를 나타내는 count 변수에 1을 더하고 그렇지 않으면 1로 저장
count와 answer중 큰 값을 answer에 할당시켜 계속 갱신

해당 문제는 매개변수로 전달된 리스트에서 연속해서 값이 증가하는 구간 중 가장 긴 구간을 찾아 그 길이를 출력하는 프로그램을 작성하는 문제이다. (full code)

내가 작성한 문제 방식은 브루트 포스 (Brute-Force) 방식이므로 완전 탐색하는 방법이다. 그나마 최악의 시간 복잡도는 피했지만 다른 방법으로도 풀 수 있다.

다른 문제 풀이 방식

1. 브루트 포스 (Brute-Force) 방식 : $O(n²)$

브루트 포스(Brute-Force 방식) : 모든 경우를 무조건 대입하는 방식 (시간 복잡도 : $O(n²)$ )

내가 작성한 방식보다 조금 더 시간 복잡도가 발생한다.

#다음과 같이 import를 사용할 수 있습니다.
#import math

def solution(arr):
    answer = 0
    cnt=1

    for i in range(len(arr)-1):
        for j in range(i+1,len(arr)):
            if arr[j-1]<arr[j]:
                cnt+=1
            else:
                break
        answer=max(answer,cnt)
        cnt=1
    return answer

#아래는 테스트케이스 출력을 해보기 위한 코드입니다.
arr = [3, 1, 2, 4, 5, 1, 2, 2, 3, 4]
ret = solution(arr)

#[실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
print("solution 함수의 반환 값은", ret, "입니다.")

arr 리스트에서 한 항목을 가져온 후, 가져온 항목 이후에 위치한 항목을 중첩 for 문을 이용하여 가져옴.
안쪽 for문을 이용해 가져온 항목이 이전 항목값보다 크면 증가 구간을 세는 변수 cnt를 +1하고, 그렇지 않으면 break 명령문을 이용하여 안쪽 for문을 빠져나감.
answer와 count중 큰 값을 answer에 할당한 후 cnt를 1로 초기화함.

2. 동적 계획법 (Dynamic Programming) 방식 : $O(n)$

우선, 동적 계획법의 정의부터 알아보자.

1) 동적 계획법 (Dynamic Programming) 정의

복잡한 문제를 작은 문제로 나누어 해결하는 방법으로 하위 문제를 풀어서 상위 문제의 답을 구하는 방식이다.
문제를 분할한다는 점에서 분할 정복법 (divide & conquer)와 유사하지만 분할 정복법은 하위 문제의 답이 상위 문제의 답에 영향을 미치지 않으나 동적 계획법은 영향을 미친다.
이전 단계의 최적값을 이용하여 다음 단계에 이용하는 방식이다.
하위 문제를 풀고 그 결과를 저장해 재사용한다.
동적 프로그래밍은 최적화 문제를 푸는데 효과적이다.

최적화 문제 : 하나의 문제에 답이 여러 개가 존재하는 문제, 최적해를 찾을 때 유용 (최단경로 문제, 최소비용 문제)

2) 동적 계획법 (Dynamic Programming) 방식 특징

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다.
부분 문제 반복 (recursive)과 최적 부분 구조 (optimal substructure)를 가지고 있는 알고리즘을 일반적인 방법에 비해 적은 시간내에 풀 때 사용한다.
다이나믹 프로그래밍은 중복된 하위 문제들 (overlapping subproblem)의 결과를 저장해 뒀다가 풀이한다.

최적 부분 구조 : 하위 단계에서 최선의 선택 → 전체 최선

3) 동적 계획법 (Dynamic Programming) 방식 특징

상향식 (Bottom-up) :

더 작은 하위 문제의 정답을 이용해 큰 문제의 정답을 풀어나감.
타블레이션 (tabulation) 방식

하향식 (Top-down) :

기존 재귀호출의 형식을 사용하나, 계산한 하위 문제의 결과를 메모리에 저장한 후 사용하여 속도를 개선함.
메모이제이션 (memoization) 방식

4) 동적 계획법 (Dynamic Programming) 적용 사례 : 피보나치 수열

피보나치 수열이란 첫 번째 항 = 1, 두 번째 항 = 1, 세 번째 항부터 그 이전에 있는 두 항을 더한 값으로 구성된 수열

재귀 호출 방식으로 구한 피보나치 수열

#피보나치 수열- 재귀함수 recursion

def fibo_r(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibo_r(n - 1) + fibo_r(n - 2)

상위 문제에서 하위 문제를 재귀적으로 호출함.
같은 계산을 반복 수행하는 경우가 발생함으로 비효율적임.

동적 계획법 - 메모이제이션 (memoization)으로 구한 피보나치 수열

메모이제이션 (memoizatioon) : 동일한 계산을 반복하지 않도록 이전 계산 결과를 저장해 놓고 필요한 경우에만 재귀 호출을 사용함으로써 프로그램 실행 속도를 높이는 기술이다.

#피보나치 수열- 동적 계획법 (메모이제이션)
dp=[0 for _ in range(500)] # (1)

def fibo_dp(n):
    if n<=2:
        return 1

    if dp[n]!=0: # (2)
        return dp[n] 
    else:
        dp[n]=fibo_dp(n-1) + fibo_dp(n-2) # (3)
        return dp[n]

결과 저장 공간을 0으로 초기화 한다. (1)
계산한 값이 있으면 그 값을 다시 계산하지 않고 반환한다. (2)
계산한 값이 없으면 재귀호출을 통해 계산하고 그 결과를 저장공간에 저장한 후 반환한다. (3)

동적 계획법 - 타블레이션 (tabulation)으로 구한 피보나치 수열

타블레이션 (tabulation) : 결과를 저장할 공간이 필요하며, 재귀호출 하지 않아 시간과 메모리 사용량을 줄일 수 있음. (하위 문제를 모두 해결해야 상위 문제 해결 가능)

#피보나치 수열- 동적 계획법 (타블레이션)
dp=[1,1]

def fibo_dp(n):
    for i in range(2,n):
        dp.append(dp[i-1] + dp[i-2])
    return dp[n-1]

결과 저장 공간을 dp로 정의하고 첫 번째, 두 번째 항목에 대한 값을 지정한다.
피보나치 수열의 항목 값을 얻기 위해 세 번째 항목부터 원하는 순번의 항목까지 결과를 산출해서 저장한다.

그럼, 동적 계획법 (Dynamic Programming) 방식을 적용하여 문제를 풀어보자❗

#다음과 같이 import를 사용할 수 있습니다.
#import math

def solution(arr):
    #여기에 코드를 작성해주세요.
    answer = 0
    dp = [1 for _ in range(len(arr))] # 1. 새로운 리스트(dp)에 전부 1로 초기화
    for i in range(1, len(arr)):
        if arr[i] > arr[i-1]: # 2. arr : 현재 인덱스 값 > 이전 인덱스 값, dp : 이전 인덱스의 값에 +1
            dp[i] = dp[i-1] + 1
    answer = max(dp) # 3. dp에 들어 있는 값 중 가장 큰 것

    return answer

#아래는 테스트케이스 출력을 해보기 위한 코드입니다.
arr = [3, 1, 2, 4, 5, 1, 2, 2, 3, 4]
ret = solution(arr)


#[실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
print("solution 함수의 반환 값은", ret, "입니다.")

arr와 같은 길이를 갖는 새로운 리스트 dp를 생성하여 각 항목을 1로 초기화한다.
- 리스트 dp는 arr의 각 항목별 연속된 증가 구간 값을 저장하기 위해 사용한다.
arr의 현재 항목 값이 이전 항목값 보다 크면, 이전 항목값과 동일한 인덱스의 dp 항목값에 +1 한 것을 현재 항목 값과 동일한 인덱스 dp 항목에 저장한다.
dp리스트에 있는 값 중 가장 큰 값을 answer에 저장 후 return한다.