전체 글
데이터 엔지니어를 희망하는 개발자 지망생엄청 큰 거듭제곱 : 지수 분할
1. 지수가 홀수면 ans = ans * base (%c) 2. 지수가 짝수면 base = base*base (%c) exp = exp/2 이걸 계속 반복해서 지수가 0이 될때 까지 반복
최장 증가 부분 수열 (LIS) : 수열 길이마다 최대값 갱신
https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4 백준 #11053 - 가장 긴 증가하는 부분 수열 응용버전 백준 #11054 - 가장 긴 바이토닉 부분 수열
n, m 수열 만들기
기본 아이디어 인덱스 0~M-1까지 각각 인덱스마다 재귀로 돌리고, 각각 인덱스마다 for문 돌려가면서 숫자를 넣음. M에 도달하면 출력하기 1. 한번씩 선택 check 배열로 해결 2. 사전순 오름차순 입력 배열 sort 3. 오로지 오름차순 수열 바로 앞에 담은 수의 인덱스 저장 4. 수열 중복 안되게 for 반복문에서 직전에 출력에 사용했던 숫자를 저장해서 같은 경우 패스
Union Find 와 서로소 집합(Disjoint Set)
https://twpower.github.io/115-union-find-disjoint-set 서로소 집합을 빠르게 병합하고, 같은 집합에 속한 요소들인지 아닌지를 빠르게 판별할 수 있는 자료구조. 배열로 구현 가능. 각 배열에는 각 집합의 대표자를 저장한다. 크게 두개의 함수를 필요로 한다. int Find(a) 함수 : a가 속한 집합의 대표자를 구하는 함수. 재귀를 통해 대표자를 구하고, uf[a] 도 그 대표자로 수정하면 된다. 최종 대표자는 uf[T] == T 를 만족한다. Union(a,b) 함수 : a와 b 가 서로 다른 집합에 속해있다면, b의 대표자의 대표를 a의 대표자로 변경하는것 만으로 두 집합을 병합할 수 있다. wow! 최단 스패닝트리를 구하는 크루스칼 알고리즘에서 유용하..