TIL # 32 : [Algorithm] 백준 / DP / LIS

새해 알고리즘 스터디(1.1~7)

3일차

백준 문제 :
11053, 11055, 11054, 11722

DP 빡공 +3👩‍💻

LIS 문제 유형을 처음 접해서 (많이) 방황했다. 풀이를 이해하는 시간도 꽤 걸렸다. 문제와 풀이를 다 이해하고 나서보니.. 고통스럽고 뿌듯하다.. (내 5시간 눈감아)

{복습 1일차 : 1/5} LIS 문제와 친해지려면 시간이 필요할 것 같다

DP 공부를 시작하는 마음가짐 🐳

◻️ 내 것이 될 때까지 물어보고 공부하고 정리하자
◻️ 파이써닉한 코드를 많이 보고 연구하자
◻️ 조급해 말고 나만 꽉 채우자

A) 11053번

소스코드:

n = int(input())

n_list = list(map(int, input().split()))

ans = n_list[0]

for i in range(1,len(n_list)):
    if ans[-1]< n_list[i]:
        ans.append(n_list[i])
    else:
        if n_list[i] in ans:
            continue
        ans_len = len(ans)
        for j in range(0, ans_len):
            if ans[j] > n_list[i]:
                ans[j] = n_list[i]
                break

출처 - soojong

풀이:

1. n_list 변수를 선언해 수를 입력 받는다.
2. 순열 중에서 가장 죄측값을 ans안에 넣는다.
3. n_list[1] ~ [마지막 인덱스]까지 순회한다.
4. ans의 마지막 값보다 n_list[i]값이 더 크면 ans에 n_list[i]를 추가한다.
5. ans의 마지막 값보다 n_list[i]값이 더 작은 경우:
   5.1. n_list[i]가 이미 ans에 있다면 continue
   5.2. ans를 순회하면서:
   --> n_list[i] 보다 더 큰 값이 나오면 n_list[i]를 ans[j]로 바꾸고 break한다.

예시 풀이:

[10, 20, 5, 30, 20, 50]을 예시로 풀어보겠다.

** 최종적으로 출력되는 수열은 [5, 20, 30, 50]이며 4가 나올 것이다.

문제풀이 체크리스트

◼️ 시간 제한 지났음에도 문제 터치 못함
◻️ 시간 제한 후 코드 완성
◻️ 코드 미완성
◻️ 코드 완성 - 에러
◻️ 코드 완성 - 정답

B) 11055번

소스코드:

n = int(input())
num = list(map(int, input().split()))
dp = [0 for i in range(n)]
for i in range(n):
    dp[i] = num[i]
    for j in range(i):
        if num[i] > num[j]:
            dp[i] = max(dp[i], dp[j] + num[i])

print(max(dp))

출처 - dontdiethere

터미널 출력:

# n = 6
# num = 1 100 2 50 60 3 5 6 7 8
# [1, 0, 0, 0, 0, 0]
# [1, 101, 0, 0, 0, 0]
# [1, 101, 3, 0, 0, 0]
# [1, 101, 3, 53, 0, 0]
# [1, 101, 3, 53, 113, 0]
# [1, 101, 3, 53, 113, 6]

풀이:

1. 수열 크기 변수 n 선언
   --> n = 6
2. 수열 변수 num 리스트 선언
   --> num = 1 100 2 50 60 3 5 6 7 8
3. dp테이블 변수 선언
   --> dp = [0, 0, 0, 0, 0, 0]
4. n 수 만큼 순회
   --> range(10) 순회 / 돌면서 dp 리스트에 값을 대입할 예정
5. dp[i] 에 num[i] 값을 넣기
   --> dp[0]같은 경우 num[0] 즉 1을 넣기
6. range(i)만큼 순회
   --> dp리스트를 돌기
7. 만약 순회하다 num[i]가 num[j]보다 클 경우
   --> num[i]값이 dp리스트 요 값보다 클 경우
   --> dp[i] 값을 dp[i], dp[j] + num[i] 중 최댓값으로 재설정
   --> dp[3]값은 num[3] + num[2] 🔹53🔹
   --> dp[5]값은 num[5]에서 받은 값 그대로 🔹6🔹

문제풀이 체크리스트

◼️ 시간 제한 지났음에도 문제 터치 못함
◻️ 시간 제한 후 코드 완성
◻️ 코드 미완성
◻️ 코드 완성 - 에러
◻️ 코드 완성 - 정답

C) 11054번

바이토닉 수열: 한 값을 기준으로 왼쪽은 증가하는 수열, 오른쪽은 감소하는 수열을 이루는 형태

증가아 감소를 나눠서 생각해야하는 문제다.

TIP:

1. 주어진 수열을 입력받고 수열의 첫번째 원소부터 돌면서 그 원소에서 가능한 가장 긴 바이토닉 수열의 개수를 dp 배열에 저장한다.
2. dp 배열에 가장 긴 수열의 개수를 넣어서 저장하고, 인덱스 값을 이용한다.
3. 이때 dp 배열은 2개로 설정한다. 왼쪽에서 최대 증가 수열 dp 배열 하나, 오른쪽에서 최대 증가 수열 dp 배열 하나를 만들어 둘을 합친다.
4. 이 때 기준으로 설정한 값은 2번 포함되므로 합친 값에서 -1을 뺀다.

소스코드:

n = int(input())
lst = list(map(int, input().split()))
dp_left = [1] * n
dp_right = [1] * n


for i in range(n):
    for j in range(i):
        if lst[j] < lst[i]:
            if dp_left[i] < dp_left[j] + 1:
                dp_left[i] = dp_left[j] + 1

for i in range(n - 1, -1, -1):
    for j in range(n - 1, i, -1):
        if lst[j] < lst[i]:
            if dp_right[i] < dp_right[j] + 1:
                dp_right[i] = dp_right[j] + 1

dp = [dp_left[i] + dp_right[i] for i in range(n)]

print(max(dp) - 1)

출처 - hip845

풀이:

1. 수열 크기 변수 n 선언
   --> n = 10
2. 수열 변수 lst 리스트 선언
   --> num = 1 5 2 1 4 3 4 5 2 1
3. 왼쪽 최대 증가 수열 dp_left 변수 선언
4. 오른쪽 최대 증가 수열 dp_right 변수 선언
5. n 수 만큼 순회
   --> range(10) 순회
6. range(i)로 순회
7. 왼쪽부터 하나씩 인덱스를 늘려가며 이전에 자기보다 value는 작으면서 수열의 길이가 긴 경우 그 길이에 +1을 시킨 다음 저장

터미널 출력:

10
1 5 2 1 4 3 4 5 2 1

dp_left: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
dp_left: [1, 2, 1, 1, 1, 1, 1, 1, 1, 1]
dp_left: [1, 2, 2, 1, 1, 1, 1, 1, 1, 1]
dp_left: [1, 2, 2, 1, 1, 1, 1, 1, 1, 1]
dp_left: [1, 2, 2, 1, 3, 1, 1, 1, 1, 1]
dp_left: [1, 2, 2, 1, 3, 3, 1, 1, 1, 1]
dp_left: [1, 2, 2, 1, 3, 3, 4, 1, 1, 1]
dp_left: [1, 2, 2, 1, 3, 3, 4, 5, 1, 1]
dp_left: [1, 2, 2, 1, 3, 3, 4, 5, 2, 1]
dp_left: [1, 2, 2, 1, 3, 3, 4, 5, 2, 1]

dp_right: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
dp_right: [1, 1, 1, 1, 1, 1, 1, 1, 2, 1]
dp_right: [1, 1, 1, 1, 1, 1, 1, 3, 2, 1]
dp_right: [1, 1, 1, 1, 1, 1, 3, 3, 2, 1]
dp_right: [1, 1, 1, 1, 1, 3, 3, 3, 2, 1]
dp_right: [1, 1, 1, 1, 4, 3, 3, 3, 2, 1]
dp_right: [1, 1, 1, 1, 4, 3, 3, 3, 2, 1]
dp_right: [1, 1, 2, 1, 4, 3, 3, 3, 2, 1]
dp_right: [1, 5, 2, 1, 4, 3, 3, 3, 2, 1]
dp_right: [1, 5, 2, 1, 4, 3, 3, 3, 2, 1]

7

다른 소스코드:

import sys

N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

ldp = [1 for _ in range(N)]
rdp = [1 for _ in range(N)]

# 왼쪽으로 돌면서 가장 긴 증가하는 부분수열의 길이를 구한다.
for i in range(1, len(arr)):
    for j in range(i):
        if arr[i] > arr[j]:
            ldp[i] = max(ldp[i], ldp[j] + 1)

# 오른쪽으로 돌면서 가장 긴 증가하는 부분수열의 길이를 구한다.
for i in range(len(arr) - 2, -1, -1):
    for j in range(len(arr) - 1, i, -1):
        if arr[i] > arr[j]:
            rdp[i] = max(rdp[i], rdp[j] + 1)

# 왼쪽과 오른쪽 두개를 더한 것중 max 값을 구한다.
ans = 0
for i in range(N):
    tmp = ldp[i] + rdp[i] - 1
    if ans < tmp:
        ans = tmp

print(ans)

출처 - kyun2da

max()함수를 활용하면 if문을 하나 줄일 수 있다!

문제풀이 체크리스트

◼️ 시간 제한 지났음에도 문제 터치 못함
◻️ 시간 제한 후 코드 완성
◻️ 코드 미완성
◻️ 코드 완성 - 에러
◻️ 코드 완성 - 정답

D) 11722번

1차 시도(성공):

# 입력 개수
n = int(input()) 
# 숫자 입력
arr= list(map(int, input().split()))
# 최솟값은 1이니까 1로 테이블 세팅
d = [1 for _ in range(n)]

# 입력 개수만큼 돌기
for i in range(n):
    # arr를 순회하면서 이전값(arr[j])보다 현재값(arr[i])이 작은지 확인 -> 작으면 감소했다는 뜻임
    for j in range(i):
        if arr[i] < arr[j]:
            # 작으면 현재값을 d리스트의 최댓값+1로 업데이트 
            d[i] = max(d[i], d[j]+1)
            print(d)
# d리스트 중 최댓값 추출 -> 정답
max_n = max(d)
print(max_n)

터미널 출력:

터미널
6
10 30 10 20 20 10
[1, 1, 2, 1, 1, 1]
[1, 1, 2, 2, 1, 1]
[1, 1, 2, 2, 2, 1]
[1, 1, 2, 2, 2, 2]
[1, 1, 2, 2, 2, 3]
[1, 1, 2, 2, 2, 3]
정답 : 3

4 문제 중 1개 풀었다...!😢 연습 많이 하자!

문제풀이 체크리스트

◻️ 시간 제한 지났음에도 문제 터치 못함
◻️ 시간 제한 후 코드 완성
◻️ 코드 미완성
◻️ 코드 완성 - 에러
◼️ 코드 완성 - 정답

Reference
https://www.acmicpc.net/
https://suri78.tistory.com/7
https://kyun2da.github.io/2020/09/22/longestBitonicSubsequence/
https://soojong.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EB%B0%B1%EC%A4%80-11053%EB%B2%88-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4
https://hjp845.tistory.com/27
https://huiung.tistory.com/74#:~:text=%EB%B0%94%EC%9D%B4%ED%86%A0%EB%8B%89%20%EC%88%98%EC%97%B4%EC%9D%B4%EB%9E%80%20%ED%95%9C,%EC%9D%84%20%EC%9D%B4%EB%A3%A8%EB%8A%94%20%ED%98%95%ED%83%9C%EB%A5%BC%20%EB%A7%90%ED%95%A9%EB%8B%88%EB%8B%A4