알고리즘 (8) 썸네일형 리스트형 알고리즘 스터디 Week9 이진 검색 트리 검색트리 자료를 정렬된 상태로 저장하여 검색에 사용할 수 있는 트리 이진 검색 트리 검색 트리 중 가장 흔하게 사용됨 최대 2개의 자식 노드만을 가질 수 있음 (이진 트리의 정의) 왼쪽 자식을 루트로 하는 서브트리의 모든 노드들의 key값은 현재 노드의 key값보다 작음 반대로, 오른쪽 자식의 모든 노드들은 현재 노드의 key값들은 현재 노드의 key값보다 큼 탐색에서는 이진 탐색(binary search)의 아이디어를 위 특성에서 활용함 순회 중위 순회를 통해 정렬된 노드들을 접근할 수 있음 조작 정렬된 데이터를 사용하지 않고, 트리를 사용할 때 가장 큰 이점을 가지는 부분 삽입: 해당하는 leaf 노드를 생성 삭제: 해당하는 노드를 삭제하고 왼쪽 자식 서브트리의 가장 오른쪽 노드나 오.. 알고리즘 스터디 Week8 트리의 구현과 순회 트리(tree)란? - 정의: 자료구조의 일종이며, 사이클이 없이 모든 정점이 연결되어있는 그래프이다. 사이클이 없는 그래프이므로 정점의 개수가 V개이면 간선의 개수는 V-1개이다. (출처) - 정의를 통해, 계층적 구조를 필연적으로 가지게 된다. 루트 노드를 제외한 노드들의 부모 노드는 한 개이다. 트리 구성, 특징 - 노드(node), 엣지(edge) - 연결된 노드들은 상하관계를 가짐, 그 중 상위 노드를 부모(parent), 하위 노드를 자식(child)라 함 - 모든 상위 노드들을 선조(ancestor)라 부르고, 모든 자식 노드를 자손(descendant)라고 함 - 최상위 노드를 루트(root), 자식이 없는 최하위 노드들은 리프(leaf) - 루트에서부터 몇 번을 거쳐야.. Codeforces 769(Div2, 1632)-C "Strange Test" https://codeforces.com/problemset/problem/1632/C - DP로 풀려 했는데, 상태 정의가 어려워 보인다. - 비트와이즈 OR 연산이 매우 중요해보인다. $a := a | b$의 연산은 $a >= b$의 상태로 만들어 준다. 총 매칭에서 이 연산을 두 번 하는 것이 의미가 없는 건 아닐까? - "어느 상태에서든 OR 연산을 한 번 진행하면 다시 OR 연산을 하는 것은 불필요한 일이다"라는 걸 증명해야함 - 복잡하게 증명할 필요없이 위에서 말한 것 하나로도 증명이 된다. 문제에서 $a$가 커질 수 있는 방법은 두 가지이지만, $b$가 커지는 방법은 한 가지 방법 밖에 없다. 그렇다면 결국 $a >= b$ 상태가 되었을 때는, $a - b$의 횟수로만 서로 같은 값에 도달할.. 알고리즘 스터디 Week5 문자열 문자열 용어 - 문자열의 크기 표현: 문자열 $S$= "avada"이라 하면, $|S|=\ 5$ - 문자열의 $i$번째 문자: $0 \le i \lt |S|$인 $i$에 대해 $S[i]$는 $i$번째 문자. $S$="avada"이라 하면, $S[3]$ = 'd' - 부분문자열(substring): 문자열 $S$에 대해서 $i$번째 문자부터 $j$번째 문자까지로 구성한 문자열을 말한다. - 접두어(prefix): 부분문자열 중 0번째 문자부터 구성한 문자열 - 접미어(suffix): 부분문자열 중 $|S| - 1$번째 문자로 끝나게 구성한 문자열 문자열 검색 문제 - 문자열 $H$의 부분문자열 중 $N$와 같은 부분문자열들의 모든 위치를 구하는 문제 - $H$= "abbabba", $N$="bba".. 알고리즘 스터디 Week4 알고리즘 문재해결전략 리뷰 20. 문자열 문자열의 검색 짚더미(haystack) 문자열 $H$가 바늘(needle) 문자열 $N$을 부분 문자열로 가지는 부분 문자열 $N$의 $H$에서의 시작위치들을 찾아내는 것을 문자열의 검색 문제라고 한다. 가장 먼저 생각나는 방법은 $H$의 모든 위치에서 $N$을 비교하는 방법이다. std::vector NaiveSearch(const std::string& H, const std::string& N) { std::vector found; for (int begin = 0; begin + N.size() $(N-K)K$가 승부의 개수이므로 최대일 때는 $K$가 $[ {N \over 2} ]$일 때이다. - 그러면 일단, 절반($[ {N \over 2} ])으로 나누.. 알고리즘 스터디 Week3 18. 선형 자료 구조 1) 동적 배열 - 원소들은 메모리의 연속된 위치에 저장함 - 주어진 위치의 원소를 반환하거나 변경할 때 $O(1)$의 상수시간이 필요 - 배열의 크기를 변경하는 $resize()$ 연산이 가능하며, 배열의 크기 N에 대해 $O(N)$의 시간이 필요 - 주어진 원소를 배열의 맨 끝에 추가할 수 있으며, 이 때 $O(1)$의 상수시간이 필요 어떻게 구현할 지를 정리해보자. 1, 2, 3번의 조건을 달성하기 위해선 밑 코드에서 첫번째 $append()$ 함수로 가능하지만, 상수시간으로 append를 처리할 수 없게 된다. 항상, 배열의 크기 $O(N)$의 시간이 필요하다. 매번 원소를 추가할 때마다 복사를 하지 않기 위해서 두번째 $append()$와 같이 $capacity$라는 변수.. 알고리즘 스터디 Week2 부분합 0번째 원소부터 i번째 원소까지 더한 값을 저장한 배열 $$psum[i] = \sum_{j=0}^{i} elements[j]$$ $elements$ 배열의 크기 $n$에 대해서 $O(n)$의 수행시간으로 계산이 가능하다. (밑의 식을 n번 반복하면 된다) $$psum[i+1] = psum[i] + elements[i+1]$$ 부분합 배열 $psum$을 통해 $\sum_{i=a}^{b} elements[i]$를 O(1)로 계산할 수 있다. $$\sum_{i=a}^{b} elements[i] = psum[b] - psum[i-1]$$ 이 특징들을 통해, 반복적으로 원소의 범위합에 접근하는 문제에서 부분합을 활용하면 매우 시간을 절약할 수 있다. $elements$의 크기 n, 원소의 범위합 접근 m번.. 알고리즘 스터디 Week1 비트마스크 N개의 boolean(flag)를 표현하고 싶을 때 bool[N]을 사용하지 않고 int와 같은 정수형을 이용해 표현함 1bit 당 1개의 boolean을 배정하면 int의 경우 32개의 boolean list를 표현할 수 있음 (상황에 따라서, 꼭 boolean이 아니여도 된다. 데이터의 범위가 자료형에 딱 맞지 않는 경우에도 사용될 수 있다. 예시로는 4bit의 데이터 범위를 char에 저장할 경우에도 비트마스킹을 하면 효율적으로 관리할 수 있다) 참고한 책에서 피자 토핑을 표현하는 비트마스크를 예로 들었는데 좋은 예시로 보여 이를 따르려고 한다. 총 토핑의 가짓수는 20개라고 하자. 모든 토핑을 올린 피자는 다음과 같이 표현할 수 있다. int fullPizza = (1 이전 1 다음
