[Python] 백준 11053번: 가장 긴 증가하는 부분 수열

SeungHyun·2023년 8월 30일
코딩테스트

coding test

목록 보기
1/16

0. 기본 정보

0-A. 개요

백준 - 11053번 문제가 어려워서 이리저리 해결법을 탐색해봄.

0-B. 문제 정보

백준 - 11053번 - 가장 긴 증가하는 부분 수열

1. 내 제출

  • 내가 생각한 문제 포인트: list의 모든 요소를 조사하여 이전 요소보다 숫자가 크면 수열 길이를 1을 더하고 가장 긴 숫자를 반환함.
    ex) 10 20 30 20 20 50
    초기 길이값 1
    20은 10보다 크므로 길이 +1
    30은 20보다 크므로 길이 +1
    20은 30보다 작으므로 pass
    20은 30보다 작으므로 pass
    50은 30보다 크므로 길이 +1
    return 4
# list를 입력받고 0번째 요소부터 마지막 요소까지 오름차순이 최대 몇개 있는지 조사하여 
최대 오름차순 횟수를 반환해줌.

def func(t:list):
    cnt = 1
    point = t[0]

    for i in range(1,len(t)):
        if point < t[i]:
            cnt += 1
            point = t[i]

    return cnt


n = int(input())
l = list(map(int, input().split()))

answer = []


# 최대 오름차순이 0번째부터 시작하지 않을 수도 있으니 모든 index부터 조사하여 최대 index

min_num = l[0]
answer.append(func(l[0:]))
for i in range(len(l)):
    if min_num>l[i]:
        answer.append(func(l[i:]))

print(max(answer))

1-A. 결과: 오답

2. 인터넷에서 찾은 정답

n = int(input())
arr = list(map(int, input().split()))
dp = [1 for _ in range(n)]

for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

3. 두 코드가 얼마나 다를까?

def my_result(m, l):
    def func(t:list):
        cnt = 1
        point = t[0]

        for i in range(1,len(t)):
            if point < t[i]:
                cnt += 1
                point = t[i]

        return cnt



    answer = []

    min_num = l[0]
    answer.append(func(l[0:]))
    for i in range(len(l)):
        if min_num>l[i]:
            answer.append(func(l[i:]))

    return max(answer)

def your_result(n, arr):
    dp = [1 for _ in range(n)]

    for i in range(n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j]+1)

    return max(dp)


import random

if __name__=="__main__":
    cnt = 0
    
    for num in range(1,1000+1):
        rand_list = [random.choice(range(1,1000+1)) for _ in range(num)]
        if my_result(num, rand_list)!=your_result(num, rand_list):
            cnt += 1

    print(cnt)

내 코드(my_result)와 인터넷에서 찾은 정답 코드(your_result) 두가지를
문제에서 제시된 기준 (1 ≤\leq N ≤\leq 1,000) / 수열 (1 ≤\leq AiA_i ≤\leq 1,000)을 적용하여
random 모듈로 조사해봄.

3-A .결과

=> 1,000번 시행 중 991번이 서로 다른 답을 내놓고 있음.
사실상 내 코드는 예제 입력 코드만 맞추는 수준

4. 어디가 틀린걸까? (반례 찾기)

4-A. 반례 찾기 코드

def my_result(m, l):
    def func(t:list):
        cnt = 1
        point = t[0]

        for i in range(1,len(t)):
            if point < t[i]:
                cnt += 1
                point = t[i]

        return cnt



    answer = []

    min_num = l[0]
    answer.append(func(l[0:]))
    for i in range(len(l)):
        if min_num>l[i]:
            answer.append(func(l[i:]))

    return max(answer)

def your_result(n, arr):
    dp = [1 for _ in range(n)]

    for i in range(n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j]+1)

    return max(dp)


import random

if __name__=="__main__":
    cnt = 0
    
    for num in range(1,1000+1):
        rand_list = [random.choice(range(1,1000+1)) for _ in range(num)]

        my_code = my_result(num, rand_list)
        your_code = your_result(num, rand_list)
        
        if my_code != your_code:
            print(f"num: {num} \n rand_list:{rand_list}")
            print(f"my_code: {my_code} \n your_code: {your_code}")
            break

3번 코드에서 마지막 부분만 조금 수정해줬다.
만약 내 코드와 정답 코드가 다를 경우 각각 num과 rand_list
그리고 내 코드와 정답 코드의 값을 출력하도록 만들었다.
너무 많은 시행을 할까봐
1개만 찾아도 바로 반복을 중단하도록 하였다.

4-B. 반례값

num: 8
rand_list:[952, 8, 961, 550, 681, 226, 934, 672]
my_code: 3
your_code: 4

정답은 8 -> 550 -> 681 -> 934 로 4가 나와야하는데 내가 작성한 코드는 3이 나왔다.

나의 코드는
8 다음으로 나온 961을 point 변수에 담고
그 다음 요소들을 각각 961과 비교 했기 때문에 최대 길이인 4가 나오지 않았던것!

5. 그럼 정답 코드는 뭐가 다른가?

n = int(input())
arr = list(map(int, input().split()))


dp = [1 for _ in range(n)]

for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

위 코드에서 핵심은 아래 부분인데

for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+1)

arr[i]와 arr[j]를 비교하여 arr[i]가 클 경우
dp[i]에 dp[i]와 dp[j]+1 중 큰 수를 입력함.

  • i=1일때 / arr[i] > arr[j] 성립 안됨.
idx01234567
i▲
j▲
arr9528961550681226934672
dp11111111
  • i=2일때 / arr[i] > arr[j] 성립 됨. (j=0,1)
idx01234567
i▲
j▲▲
arr9528961550681226934672
dp11211111

(arr[j==0], arr[j==1] 두 요소보다 크다고 해서 dp[2]가 3이 되는게 아님!)

  • i=3일때 / arr[i] > arr[j] 성립 됨 (j=1)
idx01234567
i▲
j▲▲▲
arr9528961550681226934672
dp11221111

(dp[2]가 2라고 해서 dp[3]에 3을 입력하는게 아님!)

  • i=4일때 / arr[i] > arr[j] 성립 됨 (j=1,3)
idx01234567
i▲
j▲▲▲▲
arr9528961550681226934672
dp11223111
  • i=5일때 / arr[i] > arr[j] 성립 됨 (j=1)
idx01234567
i▲
j▲▲▲▲▲
arr9528961550681226934672
dp11223211
  • i=6일때 / arr[i] > arr[j] 성립 됨 (j=1,3,4,5)
idx01234567
i▲
j▲▲▲▲▲▲
arr9528961550681226934672
dp11223241
  • i=7일때 / arr[i] > arr[j] 성립 됨 (j=1,3,5)
idx01234567
i▲
j▲▲▲▲▲▲▲
arr9528961550681226934672
dp11223243

정답: max(dp) = 4

6. 마무리

문제에 제출한 코드가 오답이고 아무리 생각해봐도 정답이 뭔지 모르겠음.
=> 검색을 통해 정답 코드를 확인함. 그래도 어떤 구조인지 모르겠음.
=> 내 코드와 정답 코드를 random 모듈을 통해 문제 조건에 맞게 랜덤한 값을 입력하여 반례를 찾음.
=> 반례를 통해 내 코드에 어떤 부분이 틀렸는지 확인함.
=> 반례를 통해 정답 코드가 어떤 구조로 돌아가는지 확인함.

이렇게 아무리 생각해도 정답 원리가 떠오르지 않는 문제를
하나하나 차근차근 분석해봤다.
비록 실버2 문제긴 하지만
이를 발판으로 조금 더 고수준의 문제도 풀며 효율적인 코드를 짜는
개발자가 되었으면 좋겠다.

ref

profile
SeungHyun
어디로 가야하오
다음 포스트

[Python] 백준 10815번: 숫자 카드

0개의 댓글