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

셀레스틴 허·2021년 1월 5일

DP LIS TIL algorithm python 백준 코테

ALGORITHM

목록 보기

5/18

새해 알고리즘 스터디(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

풀이:

n_list 변수를 선언해 수를 입력 받는다.
순열 중에서 가장 죄측값을 ans안에 넣는다.
n_list[1] ~ [마지막 인덱스]까지 순회한다.
ans의 마지막 값보다 n_list[i]값이 더 크면 ans에 n_list[i]를 추가한다.
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]

풀이:

수열 크기 변수 n 선언
--> n = 6
수열 변수 num 리스트 선언
--> num = 1 100 2 50 60 3 5 6 7 8
dp테이블 변수 선언
--> dp = [0, 0, 0, 0, 0, 0]
n 수 만큼 순회
--> range(10) 순회 / 돌면서 dp 리스트에 값을 대입할 예정
dp[i] 에 num[i] 값을 넣기
--> dp[0]같은 경우 num[0] 즉 1을 넣기
range(i)만큼 순회
--> dp리스트를 돌기
만약 순회하다 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:

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

풀이:

수열 크기 변수 n 선언
--> n = 10
수열 변수 lst 리스트 선언
--> num = 1 5 2 1 4 3 4 5 2 1
왼쪽 최대 증가 수열 dp_left 변수 선언
오른쪽 최대 증가 수열 dp_right 변수 선언
n 수 만큼 순회
--> range(10) 순회
range(i)로 순회
왼쪽부터 하나씩 인덱스를 늘려가며 이전에 자기보다 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

셀레스틴 허

Software Developer / 고통은 필연, 괴로움은 선택

이전 포스트

TIL # 31 : [Algorithm] 백준 / DP / Tiling

다음 포스트

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

ALGORITHM

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

3일차

DP 빡공 +3👩‍💻

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

A) 11053번

소스코드:

풀이:

예시 풀이:

문제풀이 체크리스트

B) 11055번

소스코드:

터미널 출력:

풀이:

문제풀이 체크리스트

C) 11054번

TIP:

소스코드:

풀이:

터미널 출력:

다른 소스코드:

문제풀이 체크리스트

D) 11722번

1차 시도(성공):

터미널 출력:

문제풀이 체크리스트

TIL # 31 : [Algorithm] 백준 / DP / Tiling

TIL # 33 : [Algorithm] 백준 / DP / Ascending Patterns

0개의 댓글