이 영역을 누르면 첫 페이지로 이동
쿄코코 블로그의 첫 페이지로 이동

쿄코코

페이지 맨 위로 올라가기

쿄코코

얼레벌레 생활🤯

99클럽 코테 스터디 27일차 TIL - DP(백준11722-가장 긴 감소하는 부분 수열 )

  • 2024.11.23 20:08
  • Python/😈 99클럽 코테 스터디 4기 TIL
    반응형

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

    • 오늘의 학습 키워드 : DP
    • 공부한 내용
    1. 입력받은 배열 A에 대해 dp 배열을 초기화: dp = [1] * N
    2. 이중 반복문으로 배열을 탐색:
     - 외부 반복문: i는 현재 비교 대상 원소를 가리킴.
     - 내부 반복문: j는 i 이전의 원소들을 탐색하며, A[i] < A[j] 조건을 만족할 때 dp[i]를 갱신.
    3. 모든 dp[i]를 계산한 후, dp 배열에서 최댓값을 출력.
    => 시간복잡도 N^2

     

    🎯 DP 풀이

    import sys
    
    # 입력 받기
    N = int(sys.stdin.readline().strip())  # 수열의 길이 N
    A = list(map(int, sys.stdin.readline().strip().split()))  # 수열 A
    
    # DP 배열 초기화: 각 원소는 자기 자신만으로 길이 1의 감소 수열을 가질 수 있음
    dp = [1] * N
    
    # 이중 반복문을 통해 DP 배열 갱신
    for i in range(len(A)):  # i: 기준이 되는 원소
        for j in range(i + 1, len(A)):  # j: i 이후의 원소
            # 감소 조건: 현재 원소 A[j]가 A[i]보다 작다면 갱신 가능
            if A[i] > A[j]:
                dp[j] = max(dp[j], dp[i] + 1)  # j번째 원소를 포함하는 감소 수열의 최댓값 갱신
    
    # DP 배열 중 최댓값이 가장 긴 감소 부분 수열의 길이
    print(max(dp))

     

    • 오늘의 공부 회고
      • 이진탐색으로 풀수있다는데... 일단 외면하고.. 스프링 부트를 공부하러 가야겠다..
      • 오늘은 피곤하니깐.. 알고리즘은 여기까지..

    반응형

    'Python > 😈 99클럽 코테 스터디 4기 TIL' 카테고리의 다른 글

    99클럽 코테 스터디 29일차 TIL - DP(백준9461-파도반 수열 )  (0) 2024.11.25
    99클럽 코테 스터디 28일차 TIL - DP(백준11055-가장 큰 증가하는 부분 수열 )  (0) 2024.11.24
    99클럽 코테 스터디 26일차 TIL - DP(백준-전력망을 둘로 나누기)  (0) 2024.11.22
    99클럽 코테 스터디 24일차 TIL - 완전탐색(프로그래머스-전력망을 둘로 나누기)  (0) 2024.11.20
    99클럽 코테 스터디 23일차 TIL - 완전탐색(프로그래머스- 소수찾기)  (0) 2024.11.20

    댓글

    이 글 공유하기

    • 구독하기

      구독하기

    • 카카오톡

      카카오톡

    • 라인

      라인

    • 트위터

      트위터

    • Facebook

      Facebook

    • 카카오스토리

      카카오스토리

    • 밴드

      밴드

    • 네이버 블로그

      네이버 블로그

    • Pocket

      Pocket

    • Evernote

      Evernote

    다른 글

    • 99클럽 코테 스터디 29일차 TIL - DP(백준9461-파도반 수열 )

      99클럽 코테 스터디 29일차 TIL - DP(백준9461-파도반 수열 )

      2024.11.25
    • 99클럽 코테 스터디 28일차 TIL - DP(백준11055-가장 큰 증가하는 부분 수열 )

      99클럽 코테 스터디 28일차 TIL - DP(백준11055-가장 큰 증가하는 부분 수열 )

      2024.11.24
    • 99클럽 코테 스터디 26일차 TIL - DP(백준-전력망을 둘로 나누기)

      99클럽 코테 스터디 26일차 TIL - DP(백준-전력망을 둘로 나누기)

      2024.11.22
    • 99클럽 코테 스터디 24일차 TIL - 완전탐색(프로그래머스-전력망을 둘로 나누기)

      99클럽 코테 스터디 24일차 TIL - 완전탐색(프로그래머스-전력망을 둘로 나누기)

      2024.11.20
    다른 글 더 둘러보기

    정보

    쿄코코 블로그의 첫 페이지로 이동

    쿄코코

    • 쿄코코의 첫 페이지로 이동

    검색

    메뉴

    • 홈

    카테고리

    • 분류 전체보기 (168)
      • Python (24)
        • 😈 99클럽 코테 스터디 4기 TIL (23)
        • 궁금한거 정리 (1)
      • SQL (16)
        • HackerRank (15)
      • [백준] Python,Java로 풀기📖 (71)
        • 정렬(Sorting) (6)
        • 그리디 (5)
        • 문자열 (7)
        • 수학 (3)
        • DFS&BFS (10)
        • 구현 (4)
        • 다이나믹 (17)
        • 이분탐색 (1)
        • 자료구조 (10)
        • 최단거리 (5)
        • 인덱스트리 (0)
      • [프로그래머스]Python,Java로 풀기 (6)
        • Level 1 (4)
        • Level 2 (2)
      • Study Platform📚 (25)
        • (운영체제) - 블로그 및 강의 참고 (0)
        • 김영한👨🏻‍🏫의 스프링 부트와 JPA 실무 완전 .. (5)
        • (알고리즘)- [이코테] 이것이 코딩테스트다 정리 (10)
        • 그림으로 배우는 Http&Network Basic (10)
      • 까먹을까봐 적는 것들 (4)
      • 테스트 보고 난 후..🤔 (0)
      • kt 에이블스쿨 (18)

    최근 글

    인기 글

    댓글

    공지사항

    아카이브

    태그

    • 오블완
    • 코딩테스트준비
    • 99클럽
    • 프로그래머스
    • 백준
    • 티스토리챌린지
    • TiL
    • 항해99

    나의 외부 링크

    정보

    쿄코코의 쿄코코

    쿄코코

    쿄코코

    블로그 구독하기

    • 구독하기
    • RSS 피드

    방문자

    • 전체 방문자
    • 오늘
    • 어제

    티스토리

    • 티스토리 홈
    • 이 블로그 관리하기
    • 글쓰기
    Powered by Tistory / Kakao. © 쿄코코. Designed by Fraccino.

    티스토리툴바