[Algorithm] LIS(Longest Increasing Subsequence; 최장 증가 부분 수열)
LIS(Longest Increasing Subsequence; 최장 증가 부분 수열) 어떠한 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 문제 이때, 부분 수열은 서로 연속할 필요는 없다. 어떠한 수열에서 일부 원소를 선택해 새로 만든 수열은 '부분 수열'이며 그 수열이 오름차순으로 정렬되어 있으면 '증가하는 부분 수열'이다. ex) 수열 [10, 20, 10, 30, 20, 50] 해당 수열에서 [10, 20, 30, 50], [10, 20, 50], [10, 50],... 등 많은 증가 부분 수열이 있지만 많은 증가 부분 수열 中 가장 길이가 긴 수열은 4개의 원소를 가진 [10, 20, 30, 50]이다. 따라서 [10, 20, 30, 50] 최장 증가 부분 수열이다. LIS는 DP(D..
2022. 3. 14.
[Python(파이썬)]컴프리헨션(Comprehension), for문, if문 한 줄로 만들기
for문, if문 [Python] for문(반복문), if문(조건문) for문(반복문) 명령이 반복 될 수 있게 하는 문법 특정 조건을 만족할 때까지 반복하는 while과 달리 원하는 횟수, 범위만큼 반복한다. for문 기본 구조 for [변수명] in [문자열, 리스트, 튜플] : [반 young-library.tistory.com 컴프리헨션(Comprehension) 파이썬 컨테이너 자료형(리스트, 딕셔너리, 세트)에 데이터를 좀 더 쉽고 간결하게 담기 위한 문법 '반복문과 조건문을 결합하여 하나의 구문으로 만들어 담는 것' 리스트 컴프리헨션, 딕셔너리 컴프리헨션, 세트 컴프리헨션, 제너레이터 컴프리헨션이 있다. 컴프리헨션 기본 구조 리스트 컴프리헨션 : [반복 실행문 for 변수 in 순회 가능 객..
2022. 3. 11.