LIS(Longest Increase Sequence)란? LIS 알고리즘은, 주어진 수열에서 숫자를 제외시켜 최장 길이의 오름차순 수열을 만드는 알고리즘이다. LIS 구현 1. 이중 반복문을 통한 구현 (O(N^2)) 해당 구간까지의 '최장 증가 부분수열'의 크기를 저장하는 별도의 list를 생성하고 이를 업데이트한다. array의 모든 값에 대해, 해당 값 이전까지(0 ~ i-1) 자신보다 큰 값들의(array[j] > array[i]) 개수를 dp[i]에 저장한다. 모든 과정이 끝나면, dp의 가장 큰 값이 array에서 만들 수 있는 '최장 증가 부분수열'의 크기 이다. array = [3,4,1,2,6,4,3,1] dp = [1] * len(array) for i in range(1, len(a..

시간복잡도란? : 문제를 해결하는데 걸리는 시간 시간복잡도 정리 메서드 시간복잡도 bisect_left() O(logN) collections.Counter() O(N) 선택정렬 (selection sort) O(N^2) 삽입정렬 (insertion sort) O(N^2) 퀵정렬 (quick sort) O(NlogN)

1. 소수 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 2. 소수를 판별하는 방법 1. 모든 수 확인 def isPrimeNum(n:int)->bool: for i in range(1, N+1): if N % i == 0: return False return True 2. $\sqrt{N}$ 까지 확인 $\sqrt{N}$까지 확인하면, 제곱근을 포함한 N을 나눌 수 있는 수 모두를 확인할 수 있다. def isPrimeNum(N:int)->bool: for i in range(2, int(N**0.5)+1): if N % i == 0: return False return True 3. 소수를 찾는 방법 - 에라토스테네스의 체 특정 범위 내의 소수를 전부 찾는 경우, 위 방법을 활용하..

1. 정규 표현식(regex)특정한 규칙의 문자열 집합을 표현하는 데 사용하는 형식 언어2. 정규 표현식 모듈import restring = "aaaa,b,c,e,d"a = re.search('a+', string)print(a.span())3. 정규 표현식 문법표현식의미표현식의미. 1개의 문자[a,b]a,b 중 하나a?0개 또는 1개의 문자 (a가 하나 있거나 없거나)[^ab]a,b 제외a*0개 이상의 문자 (a가 0개 이상)[a-z]a~z사이의 문자a+1개 이상의 문자 (a가 1개 이상)\다음 기호를 문자로 사용^a뒤의 문자로 시작하는 문자열 (a, ab, apple...)\b문자와 공백 사이$a앞의 문자로 끝나는 문자열 (bba, aaa, india...)\B문자와 공백 사이가 아닌 문자a|ba 또..

N진수에 N은 등장하지 않는다! 1. 2/8/16진법 -> 10진법 print(int('0b1010', 2)) # 10 print(int('0o')) 2. 10진법 -> 2/8/16진법 b = bin(10) # '0b1010' o = oct(18) # '0o22' h = hex(33) # '0x21' 3. 10진법 -> N진법 3-1. 재귀함수 import string def convert_notation(number:int, base:int)->int: base_num = string.digits + string.ascii_uppercase q, r = divmod(number, base) if q: return convert_notation(q, base) + number[r] else: number..

1. 중복을 허용하지 않는 경우 1 - 1. 순열 (permutations) $${}_n{\rm P}_r = \frac{n!}{(n-r)!}$$ - p개 중에서 중복을 허용하지 않고 r개를 뽑아 나열하는 경우의 수 - 나열하기 때문에 순서가 다르면 다른 경우로 취급한다. from itertools import permutations a = [1,2,3,4,5] b = list(permutations(a, 2)) # a에서 2개를 뽑아 나열하는 경우 print(b) [(1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 3), (2, 4), (2, 5), (3, 1), (3, 2), (3, 4), (3, 5), (4, 1), (4, 2), (4, 3), (4, 5), (5, 1),..