GitHub ID : soohyun-dev
윤수현의 개발 공간
GitHub ID : soohyun-dev
전체 방문자
오늘
어제
  • 분류 전체보기 (918)
    • 성장기록 (49)
      • 성장기록 (3)
      • 우아한테크코스 (16)
      • 프로젝트 (15)
      • TIL (14)
      • 테오의 스프린트 (1)
    • 프로그래밍언어 (88)
      • C언어 (14)
      • HTML\CSS (12)
      • JavaScript (7)
      • React (23)
      • Python (11)
      • JAVA (14)
      • TypeScript (6)
    • 알고리즘 공부 (736)
      • 코드업 - 파이썬 (108)
      • 백준 - 파이썬 (468)
      • 백준 - 자바스크립트 (125)
      • 프로그래머스 - 파이썬 (1)
      • 프로그래머스 - 자바스크립트 (34)
    • 책 리뷰 (9)
      • 프로그래밍 (3)
      • 독서 (6)
    • 전자기기 (1)
    • 일상, 일기 (18)
    • 기술 세미나 (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 자바스크립트
  • javascript
  • 코딩
  • 프로그래머스풀이
  • 백준
  • 파이썬
  • 코딩테스트
  • 영어
  • PYTHON
  • 영어독해
  • 프로그래머스자바스크립트
  • 코드업
  • 프론트엔드
  • 코테
  • 독해
  • 코드업파이썬
  • 백준풀이
  • 프로그래밍언어
  • 백준파이썬
  • 프로그래머스

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
GitHub ID : soohyun-dev

윤수현의 개발 공간

백준/ Silver 2 문제 , 백준 파이썬 11053 , 가장 긴 증가하는 부분 수열
알고리즘 공부/백준 - 파이썬

백준/ Silver 2 문제 , 백준 파이썬 11053 , 가장 긴 증가하는 부분 수열

2022. 2. 4. 11:53

백준/ Silver 2 문제 , 백준 파이썬 11053 , 가장 긴 증가하는 부분 수열

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>

 

<문제 출처>

 

https://www.acmicpc.net/problem/11053

 

11053번: 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

 

------------------------------------------------------------------------------------------------------------------------------

 

dp 문제이다.

 

dp=[0 for _ in range(N)]

 

dp 를 선언해주고 for 중첩을 통해 체크를 해줄거다.

 

 

 

if A[i] > A[j] and dp[i] < dp[j]:
            dp[i]=dp[j]

 

이 코드를 이해해보자.

 

예시는 10 20 10 30 20 50 이다.

 

 

i=0

 

첫번째 10 은 dp 가 아직 0 이므로 if 조건에 해당하지 않는다.

 

이후

 

dp[i]+=1

를 통해 dp[0]은 1이 된다.

 

 

dp=[1, 0, 0, 0, 0, 0]

 

 

 

 

i=1

 

두번째 20으로 넘어오면 dp[0]=1 인 상태

 

if 조건문이 성립하므로

 

dp[1]에 dp[0]=1 의 값을 부여한다.

 

 

 

최종 dp는 dp=[1, 2, 0, 0, 0, 0]

 

 

 

 

i=2

 

값이 다시 작아져 10을 만났다.

 

if 문에 해당하지 않으므로 dp는 그냥 1만 부여된다.

 

 

dp=[1, 2, 1, 0, 0, 0]

 

 

 

 

i=3

 

30을 만났다. for 문을 돌면서 dp[i] < dp[j] 인 부분에서 if 문 내로 들어간다.

 

dp[3] 에는 d[1] 의값 2 가 부여되고 최종 dp는

 

 

dp=[1, 2, 1, 3, 0, 0]

 

 

 

 

i=4

 

10이므로 건너간다.

 

 

dp=[1, 2, 1, 3, 1, 0]

 

 

 

 

 

i=5

 

50을 만났다. for 문을 돌면서 dp[5] 에 dp[3] 의 값 3이 부여되고

 

최종 dp는 

 

dp=[1, 2, 1, 3, 1, 4]

 

 

 

 

여기까지하면 루프를 다 돈 것이다. 이제 제일 큰 숫자를 출력해줘야하므로 max 를 사용해 4를 꺼내준다.

 

 

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

 

 

import sys
input=sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
dp=[0 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if A[i] > A[j] and dp[i] < dp[j]:
            dp[i]=dp[j]
    dp[i]+=1   
print(max(dp))

 

 

 

 

 

 

반응형

'알고리즘 공부 > 백준 - 파이썬' 카테고리의 다른 글

백준/ Silver 2 문제 , 백준 파이썬 11722, 가장 긴 감소하는 부분 수열  (0) 2022.02.04
백준/ Silver 2 문제 , 백준 파이썬 11055 , 가장 큰 증가 부분 수열  (0) 2022.02.04
백준/ Gold 5 문제 , 백준 파이썬 2110 , 공유기 설치  (0) 2022.02.04
백준/ Silver 3 문제 , 백준 파이썬 2512 , 예산  (0) 2022.02.03
백준/ Silver 3 문제 , 백준 파이썬 1654 , 랜선 자르기  (0) 2022.02.03
    '알고리즘 공부/백준 - 파이썬' 카테고리의 다른 글
    • 백준/ Silver 2 문제 , 백준 파이썬 11722, 가장 긴 감소하는 부분 수열
    • 백준/ Silver 2 문제 , 백준 파이썬 11055 , 가장 큰 증가 부분 수열
    • 백준/ Gold 5 문제 , 백준 파이썬 2110 , 공유기 설치
    • 백준/ Silver 3 문제 , 백준 파이썬 2512 , 예산
    GitHub ID : soohyun-dev
    GitHub ID : soohyun-dev
    환영합니다!😊 이곳은 저의 개발에 관한 내용들을 정리하는 공간입니다. 알고리즘 풀이에도 관심이 많아요. 좋은 하루 되세요~! github : soohyun_dev

    티스토리툴바