[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.
[Python(파이썬)] for문(반복문), if문(조건문)
for문(반복문) 명령이 반복 될 수 있게 하는 문법 특정 조건을 만족할 때까지 반복하는 while과 달리 원하는 횟수, 범위만큼 반복한다. for문 기본 구조 for [변수명] in [문자열, 리스트, 튜플] : [반복하여 실행할 명령] for [변수명] in range([반복 횟수]) : [반복하여 실행할 명령] for문을 사용하여 리스트 출력 >>> nlist = ['a','b','c','d','e','f'] >>> for i in nlist: print(i) for문으로 리스트 인덱스 2부터 4까지 내용 출력 >>> nlist = ['a','b','c','d','e','f'] >>> for i in range(2,5): print(nlist[i]) for문으로 0-4 반복하여 출력하기 >>> fo..
2022. 3. 10.
[Python(파이썬)] 다양하게 입력받기 [input(), sys.stdin.readline(), strip()]
1. input() input()은 기본적인 파이썬 입력 방법이다. input으로 입력받으면 기본적으로 str 타입으로 저장된다. 또한 list()를 사용하면 문자열을 하나하나 분리해 리스트로 만들어준다. >>> a = input() abcde >>> a 'abcde' >>> list(a) ['a', 'b', 'c', 'd', 'e'] >>> test = input() Hello Hi >>> test 'Hello Hi' >>> list(test) ['H', 'e', 'l', 'l', 'o', ' ', 'H', 'i'] 나머지 input에 대한 설명은 아래 링크에 있다. [Python(파이썬)] 입력, 출력 (input(), print()) 입력 - input() 파이썬에서는 기본적으로 input()을 사..
2021. 12. 1.
