순열과 조합 공식 이해
조합개념은 순열개념과 연결되기때문에 순열을 먼저 이해하면 조합의 이해가 쉽다 순열: n개에서 r개를 뽑는 경우의 수, 순서 영향o 조합: n개에서 r개를 뽑는 경우의 수, 순서 영향x (a,b,c)에서 두개를 뽑아 만들수있는 순열은 (a,b) (a,c) (b,a) (b,c) (c,a) (c,b) 총 6개이다 (a,b,c)에서 두개를 뽑아 만들수있는 조합은 (a,b) (a,c) (b,c) 총 3개이다 순열 공식의 이해 이제 순열을 계산해보자 n개에서 r개를 뽑아 만들수있는 경우의 수는 몇가지일까? 처음에는 n개중에 하나를 고르면 되니까 n가지방법 두번째는 아까 고른것을 빼고 (n-1)개중에 하나를 고르면 되니까 (n-1)가지 방법 세번째는 ... 이런식으로 r개까지 뽑으면된다 팩토리얼로도 표현할수있다 조합..
2023. 6. 18.
LIS길이를 이분탐색으로 구해보자(python)
가장 긴 증가하는 부분수열(LIS)의 길이를 이분탐색을 이용해 구해보자 먼저 가장 긴 증가하는 부분 수열이 뭔지 이해해보자 수열: 숫자들의 나열 ex) [5,3,8,2] 부분수열: 수열안에서 몇몇 숫자들을 골라서 만든 새로운 수열 ex) [5,8,3,2] => [5,8,2] 따라서 수열 [10, 20, 10, 30, 20, 50]이 있을때 따라서 가장 긴 증가하는 부분 수열은 [10, 20, 10, 30, 20, 50]이고 길이는 4이다 이분탐색을 이용한 풀이 주어진 수열의 각 원소를 순회하면서 이분탐색을 적용해나간다 따라서 시간복잡도는 O(nlogn) 이된다 세부적인 이진탐색 과정은 아래와 같다 현재 원소를 이진 탐색을 통해 LIS 배열에 삽입할 위치를 찾는다 (LIS배열은 항상 정렬된 상태를 유지한다..
2023. 6. 6.
