Koo's.Co

python에서 제공하는 itertools를 사용하면 효율적으로 순열과 조합을 구할 수 있습니다. 1. 조합(combinations) 첫번째 파라미터로 iterable 객체를 받고, 두번째 파라미터는 선택할 원소의 개수를 입력받습니다. from itertools import combinations A = [2, 1, 3] for i in combinations(A, 2): print(i) for i in combinations(A, 3): print(i) 2. combinations_with_replacement 중복을 허용하여 입력받은 iterable 객체 내 원소로 만들 수 있는 모든 조합을 구할 수 있습니다. from itertools import combinations_with_replacemen..

전에 파이썬의 bisect 라이브러리의 bisect_left와 bisect_right을 다룬 적이 있었습니다. 그 때는 기본적인 함수의 동작방식과 사용방법에 대해서만 공부해봤는데 최근에 LIS 문제를 다시 풀어보면서 lower bound를 다시 공부할 기회가 생겼었습니다. 오늘은 직접 bisect_left, bisect_right를 구현해보려 합니다. 오늘 게시물을 보기 전에 아래 게시물에서 lower bound와 upper bound에 대해 읽어보고 오시길 추천드립니다. 간단하게 lower bound: target "이상(target 포함o)"이 처음 나오는 위치 upper bound: target"보다 큰(target 포함x)" 값이 처음 나오는 위 [Python] bisect 라이브러리 (lower..

1. 피보나치 수열 피보나치 수는 첫째 항과 둘째 항이 1이고 뒤에 나오는 모든 항이 앞 두 항의 합인 수열이다. 앞의 두항의 합만 구하면 다음 항을 구할 수 있으므로 코드로 구현하면 다음과 같이 간단하게 표현할 수 있다. N = int(input()) def fibo(x): if x == 0: return 0 if x == 1: return 1 return fib(x - 1) + fib(x - 2) print(fibo(N)) 하지만 이 코드에는 큰 문제점이 있는데... 앞서 구했던 피보나치 수의 값을 기억하질 못한다... N=5라고 할 때 피보나치 수를 구하면 위와 같다. 동일한 계산을 여러 번하는데 전에 이미 값을 구했는데도 하위 연산을 하면서 값을 다시 구한다. 값이 하나 증가할 때마다 연산의 횟수..

bisect 라이브러리에 있는 bisect_left, bisect_right에 대해 공부하려 합니다. 1. bisect? - 정렬된 리스트에서 이진 탐색을 이용해 데이터를 찾는 메서드를 제공 - O(logN)의 시간 복잡도로 데이터를 찾을 수 있다 - bisect_left는 lower bound로, bisect_right는 upper_bound로 사용할 수 있다 2. lower bound와 upper bound bisect 라이브러리에서 제공하는 메서드는 이진 탐색과 완전히 일치하지는 않고 조금 차이점이 있다. 위에서 말한 것처럼 bisect_left는 lower bound 알고리즘을, bisect_right는 upper bound 알고리즘을 수행한다. - binary search: 찾고자 하는 값이 존..

1. 이진탐색? - 이진탐색은 정렬되어 있는 선형자료구조에서 사용할 수 있는 탐색 방법이다. - 정렬되지 않은 자료형의 경우 처음부터 차례대로 값을 비교해야하기 때문에 O(N)의 시간복잡도를 갖는다. - 반면 자료가 정렬되어 있는 경우 이진탐색을 통해 O(logN)의 시간복잡도로 값을 찾을 수 있다. - 이진탐색은 범위를 주면 해당 범위 중간값을 기준으로 찾고자 하는 값이 중간값보다 큰지 작은지를 판단하는 방법이다. - ex) 책에서 원하는 페이지 번호를 찾으려 할 때 일단 책을 펴고 찾고자 하는 페이지 번호가 더 작으면 앞부분을, 찾고자 하는 페이지 번호가 더 크면 뒷부분을 보는 것과 같다. 2. 이진탐색 알고리즘 - 찾고자 하는 값을 target이라 한다 - 리스트 nums가 주어지면 가장 작은 인덱..