Look-and-say sequence(개미수열)
개미 수열(정규표현식) Dev 코스 조그마한 과제였는데 처음에 정규표현식을 자유롭게 사용하지 못해 쉽게 풀지 못했습니다. 그러나 풀었습니다. :) 우선 개미 수열에 대해 알아야합니다. 영차 영차 1 -> 11 -> 21 -> 121 -> 111211 -> 311221 ... 다음과 같은 규칙을 가지는 데 처음에 이해를 잘 못했습니다. 힌트는 Run-length encoding입니다. 이해를 돕기위해 설명을 조금 더하자면 전 단계의 값에서 같은 수의 값 개수 + 값 을 구하는 것 ex) "1"에서 "11"이 나오기 위해 1개의 1을 붙여 쓴 것이 "11"입니다. "121"에서 "111211"이 나오기 위해 1개의 1 + 1개의 2 + 1개의 1을 숫자만 붙여써보면 "1111211"이 나옵니다. 즉, 현재 ..
레드 블랙 트리 삭제 삭제하는 node(x)가 Black일 때 실행 이중 흑색 노드일 경우 Case 파악 이중 흑색 노드: 검은색 node를 다시 검은색으로 칠하는 경우 그냥 삭제 합니다. (무조건 실행) 이진 검색 트리 삭제 이용 자리를 대체하는 node를 검정색으로 변환 Red -> Black : 괜찮다 Black -> Black : 이중 흑색 노드 Case change) x의 형제가 Red 1. x의 형제 Red -> Black 2. x의 부모 * -> Red 3. x의 부모를 기준으로 왼쪽 회전 4. 다른 Case 이동 Case 1) x의 형제가 Black x..
레드 블랙 트리 (Red-Black Tree) https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC 조건 1. Root는 Black이다 2. 모든 리프(NIL)는 Black이다. 3. node가 Red -> node의 자식은 반드시 Black 연속된 Red node X 4. Root에서 임의의 리프 node까지 만나는 Black node의 수는 같다. 레드 블랙 트리 삽입 삽입한 node는 무조건 Red node 입니다. Red node - Red node 겹칠 때 Case 파악 Red node의 부모 node도 Red일 경우 맨 밑의 Red node가 기준 입니다. Restructuring 삽입된 no..
점화식 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현 1. 반복 대치 더 작은 문제에 대한 함수로 반복해서 대치해가는 방법 점근적 복잡도 계산 용의 $$ n = c^k $$ $$ n , \le , c^k , < , cn , 인, c^k이 , 하나 존재한다. $$ $$ 만약,임의의,상수,r에,대해,T(n),=,O(n^r)이라면, $$ $$ T(cn) ,=,O((cn)^r),=,O(c^rn^r),=,O(n^r)이므로,T(cn),=,T(n)이,된다. $$ 입력의 크기가 두배가 되어도 다항식 범위 내에 있는 점근적 복잡도는 변하지 않는다. $$ T(n), \le , T(2^k), \le , T(2n) $$ 2. 추정 후 증명 결론을 추정하고 수학적 귀납법으로 이용하여 증명하는 방법 수학적 귀납..
알고리즘 점근적 표기 https://ko.wikipedia.org/wiki/%EC%9C%84%ED%82%A4%EB%B0%B1%EA%B3%BC:TeX_%EB%AC%B8%EB%B2%95 https://blog.naver.com/aureagenus/120113285536 https://jjycjnmath.tistory.com/117 O - 표기법 O(f(n))은 최고차항의 차수*가 f(n)과 *일치하거나 더 작은 함수의 집합 상한의 개념 포함 $$ f(n) \in , O(g(n))을 , f(n) = O(g(n)) $$ $$ f(n) = O(g(n)) => f는 , g보다 , 빠르게 , 증가하지 , 않는다. $$ $$ ex);5n^2 , + , 4n , = O(n^2) , or , 7n , = O(n^2) $$..
### 이진 탐색 ### : 데이터가 '정렬'된 상태에서 데이터를 반으로 나눠가며 특정 값을 찾는 방법 : 정렬된 데이터 O(logn) : 시작점(start), 끝점(end), 중간점(mid)를 가지고 범위를 좁혀가며 값을 찾는다. data = [1,2,3,4,5,6,7,8,9,10] target = 2 start = 1 end = 10 # 반복 사용 def binarySearch(start, end, target): while (start >= end): mid = (start+end) // 2 if (data[mid] == target): return mid elif (data[mid] < target): start = mid + 1 else: end = ..
### 파라메트릭 서치 ### : 원하는 조건(범위) 내에서 최대,최소 값을 찾는 문제 => 결정 문제 (이분 탐색으로 해결) (ex, ~한 것중에서 최대,최소 인 값을 찾으시오) 1. 위의 개념에 만족 2. 최댓값 -> 최댓값보다 작은 값들이 조건을 모두 만족 최솟값 -> 최솟값보다 큰 값들이 조건을 모두 만족 3. 정확한 값을 구할 수 있어야 한다. (무한대 x) O(조건함수(n) * logn) 1. 최댓/최솟값을 구하는 것을 기준으로 start, end(이분 탐색 기준)를 잡는다. (start = mid + 1, end = mid - 1이 값을 크/작 게 만드는 지 파악하기) 2. 함수를 만들어 범위를 줄여 나가며 답을 구한다. # 최댓..