아무거나

백준의 11053과 같은 유형을 흔히 `최장 증가 부분 수열(Longest Increasing Subsequence,LIS)라 하는데 이를 구하는 방법은 크게 두가지가 존재한다. 1. DP를 이용한 풀이 (가장 기본적 간단, 시간복잡도:O(n^2)) 파이썬 import sys sys_input=sys.stdin.readline n=int(sys_input()) arr=list(map(int,sys_input().rstrip().split())) dp=[1] for i in range(1,n): find=0 for j in range(i): if arr[i]>arr[j]: find=max(find,dp[j]) dp.append(find+1) print(max(dp)) 자바 import java.io.*; ..

문제 내용 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 과정 -이분탐색으로 판단하고 문제풀이를 진행함. 풀이중 문제점 1.이분탐색 종료지점에 대한 불확실함. 문제점 해결 과정 1.start값의 변경을 통해 반복문을 탈출하였음. 해결 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 import sys sys_input=sys..