본문 바로가기

Algorithms135

알고리즘 문제 해결 전략 2 6장 트리 (6) 24 구간 트리 24.1 구간 트리: 구간에 대한 질문 대답하기 segment tree는 저장된 자료들을 적절히 전처리해 그들에 대한 질의들을 빠르게 대답할 수 있도록 함. 해당 배열을 전처리해 구간 트리를 생성하면 같은 연산을 빠르게 구현할 수 있음. 구간 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진 트리를 만드는 것임. 구간 트리의 표현 꽉 찬 이진 트리는 이진 검색 트리처럼 포인터로 연결된 객체로 표현하기보다 배열로 표현하는 것이 메모리를 더 절약할 수 있음. 구간 트리의 초기화 구간 트리의 각 노드에 대해 위치 등을 저장해 두지 않는 것을 유의함. 해당 노드를 찾아가는 과정에서 표현하는 구간을 동적으로 계산할 수 있기 때문에 따로 저장해 둘 필요가 없음. struct RMQ {.. 2021. 7. 5.
알고리즘 문제 해결 전략 2 6장 트리 (5) 22.7 문제: 삽입 정렬 뒤집기 삽입 정렬은 A가 정렬된 배열일 때, A[i]를 적절한 위치를 만날 때까지 왼쪽으로 한 칸씩 움직임. 예제에서 각 위치에 있는 값들이 움직인 칸수를 표현하면 {0, 1, 1, 2, 3}이 됨. 이때 원래 수열을 찾아내는 프로그램을 작성하시오. 22.8 풀이: 삽입 정렬 뒤집기 이 알고리즘을 구현하기 위해서는 후보들의 집합 중 k번째 원소가 무엇인지를 찾고, 삭제하는 작업을 빠르게 수행할 수 있어야 함. 이진 검색 트리를 사용하면 이런 일을 O(lgN) 시간에 할 수 있음. void solve() { Node* candidates = NULL; for (int i = 0; i < n; ++i) candidates = insert(candidates, new Node(i +.. 2021. 7. 5.
알고리즘 문제 해결 전략 2 6장 트리 (4) 22.6 균형 잡힌 이진 검색 트리 직접 구현하기:트립 문제는 AVL트리나 레드 블랙 트리 등 교과서에 실리는 대부분의 균형 잡힌 이진 검색 트리들은 구현이 매우 까다로움. 구현이 간단한 이진 검색 트리를 사용함. 대표적인 것은 트립(treap). 트립의 정의 트립은 입력이 특정 순서로 주어질 때 그 성능이 떨어진다는 이진 검색 트리의 단점을 해결하기 위해 고안된 일종의 랜덤화 된 이진 검색 트리임. 트리의 형태가 원소들의 추가 순서에 따라 결정되지 않고 난수에 의해 임의대로 결정됨. 이와 같은 속성을 유지하기 위해 트립은 새 노드를 추가될 때마다 해당 노드에 우선순위를 부여함. 트립은 항상 부모의 우선순위가 자식의 우선순위보다 높은 이진 검색 트리를 만듭니다. 트립의 조건을 다음 두 가지로 정리할 수 .. 2021. 7. 3.
알고리즘 문제 해결 전략 2 06장 트리 (3) 22. 이진 검색 트리 22.1 도입 자료들을 일정한 순서에 따라 정렬한 상태로 저장해 둠. 검색 트리는 이 점을 이용해 원소의 추가와 삭제만이 아니라 특정 원소의 존재 여부 확인 등의 다양한 연산을 빠르게 할 수 있음. 검색 트리 중 가장 흔하게 사용되는 것이 바로 이 장에서 소개할 이진 검색트리와 그 변종들임. 이진 검색 트리들은 아주 널리 사용됨. 22.2 이진 검색 트리의 정의와 조작 정의 이진 트리란 각 노드가 왼쪽과 오른쪽, 최대 두 개의 자식 노드만을 가질 수 있는 트리를 의미함. 이진 검색트리에서 원하는 값을 찾는 과정은 배열에서의 이진 탐색과 비슷함. 순회 이진 검색 트리를 중위 순회하면 크기 순서로 정렬된 원소의 목록을 얻을 수 있음. 자료의 검색 한 번 원소를 비교하는 것 만으로도 찾.. 2021. 7. 3.
알고리즘 문제 해결 전략 2 06장 트리 (2) 21.5 문제 요새 성벽들의 정보가 주어질 때 임의의 두 지점 간을 이동하기 위해 최대 몇 번이나 성벽을 넘어야 하는지 계산하는 프로그램을 작성하시오. 21.6 풀이: 요새 성벽들은 서로 닿거나 겹치지 않는다는 조건에 주목하면 성이 계층적 구조로 구성되어 있음을 알 수 있음. 따라서 성벽들 간의 포함 관계를 트리로 나타내서 문제를 풀어낼 수 있음. 이렇게 트리를 구성하고 나면, 한 구역에서 인접한 다른 구역으로 가기 위해 성벽을 넘는 일은 이 트리에서 간선을 따라 다른 노드로 옮겨가는 것으로 대응됨. 따라서 두 지점을 왕래하기 위해 성벽을 가장 많이 넘어야 하는 경우를 찾는 문제는 트리에서 가장 멀리 떨어진 두 노드를 찾는 문제가 됨. 트리에서 가장 긴 경로 찾기 이와 같은 모델링 과정을 거치면 이 문제.. 2021. 7. 3.
알고리즘 문제 해결 전략 2 06장 트리 (1) void printPostOrder(const vector& preorder, const vector& inorder) { const int N = preorder.size(); if (preorder.empty()) return; const int root = preorder[0]; const int L = find(inorder.begin(), inorder.end(), root) - inorder.begin(); const int R = N - 1 - L; printPostOrder(slice(preorder, 1, L + 1), slice(inorder, 0, L)); printPostOrder(slice(preorder, L + 1, N), slice(inorder, L + 1, N)); cou.. 2021. 7. 1.
알고리즘 문제 해결 전략2 19장 큐와 스택, 데크 (2) 19.4 문제:짝이 맞지 않는 괄호 모든 괄호는 짝이 있어야 함. 모든 괄호 쌍은 먼저 열린 뒤 닫힘 한 괄호 쌍이 다른 괄호쌍과 서로 교차해 있으면 안됨. 19.5 풀이:짝이 맞지 않는 괄호 두 가지 예외를 추가로 처리하는 것을 눈여겨봅시다. 스택에서 여는 괄호를 꺼내려고 하는데 스택이 비어 있는 경우, 그리고 전부 다 잘 처리하고 마지막에 열린 괄호가 남아 있는지 확인하는 것 모두 이 문제를 처음 작성하는 사람이 간과하기 쉬운 부분임. bool wellMAtched(const string& formula) { const string opening("({["), closing(")}]"); stack openStack; for (int i = 0; i < formula.size(); ++i) { if .. 2021. 7. 1.
큰 수의 덧셈, 뺄셈 - 그럼 이것이 일반 long long int를 넘어가는 숫자에 대해서 확인을 해봐야겠음. - 일단 이렇게 정리한다는 것은 알겠음 개괄적으로 - 캐리될 수도 있으므로 그것의 버퍼를 남겨두고 저장해야 할 것 같은데 - M을 어떻게 처리하고 있는지 이것이 핵심인것 같음 => 내가 아직 모르는 부분 - 캐리가 발생할 때 처리하고 있는데, 왜 M이 10^15 일까 - 담을 수 있는 것이 long long int 이므로 8byte인데, 범위가 –9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 - 10^19까지 담을 수 있는데 왜 10^15까지만 담았을까. - 밀리고 밀려서 앞에까지 carry가 넘어오는 경우가 생길 텐데 최악의 경우 5자리가 넘어올 수 있는 것인가?.. 2021. 6. 24.
알고리즘 문제 해결 전략2 19장 큐와 스택, 데크 (1) 19.1 도입 현실 세계의 규칙을 추상화하는 추상화 자료 구조의 대표적인 예로 큐와 스택, 데크가 있음. 큐와 스택, 데크가 중요한 이유는 흔히 사용하게 되는 자료 구조의 형태에 이름을 붙였다는 데 있음. 큐와 스택, 데크 큐와 스택, 데크는 일렬로 늘어선 같은 형태의 자료들을 저장함. 이때 세 자료 구조들을 구분하는 것은 어느 쪽 끝에서 자료를 넣고 뺄 수 있는가입니다. 컴퓨터는 내부적으로 스택을 사용해 함수들의 문맥을 관리함. 데크는 양쪽 끝에서 자료들을 넣고 뺄 수 있는 자료 구조를 말함. 데크를 이용하면 스택과 큐를 모두 구현할 수 있음. 19.2 큐와 스택, 데크의 구현 연결리스트의 경우 노드의 할당과 삭제 그리고 포인터를 따라가는 데 드는 데 시간이 걸리기 떄문에 여결 리스트가 가장 효율적인 .. 2021. 6. 22.

티스토리툴바