분할 정복
0. 들어가며 분할 정복 유형의 알고리즘 주어진 문제를 작은 부분으로 나누고 나눠진 각 부분의 솔루션을 구하고 각 부분 문제의 솔루션을 합쳐서 전체 문제에 대한 솔루션을 구하는 방식 이진 검색, 퀵 정렬, 병합 정렬, 행렬 곱셈, 고속 푸리에 변환, 스카이라인 알고리즘 1. 이진 검색 1) 이진 검색 주어진 시퀀스가 정렬되어 있을 경우 N값이 있는 지 확인 전체 시퀀스 범위를 range로 설정 현재 range의 가운데 원소를 M이라고 하고 M과 N 비교 M=N이면 시퀀스에서 N을 찾았음 → 검색 종료 그렇지 않다면 2가지 규칙에 따라 range 수정 NM이면 range에서 M 왼쪽에 있는 모든 원소 제거 range에 한 개 보다 많은 원소가 남아있다면 2단계로 이동 그렇지 않으면 주어진 시퀀스에 N이 존..
- Computer Science/Data Structure & Algorithm
- · 2023. 7. 1.
해시 테이블과 블룸 필터
0. 들어가며 룩업(조회) : 특정 원소가 컨테이너에 있는지 확인하거나 또는 컨테이너에서 특정 키에 해당하는 값을 찾는 작업 해당 작업을 훨씬 빠르게 수행할 수 있는 해시 테이블과 블룸 필터 구현 1. 해시 테이블 선형 검색 O(N) / BST 검색 O(log N) 해시 테이블의 핵심은 해싱 1) 해싱 각각의 데이터를 가급적 고유한 숫자 값으로 표현, 같은 숫자 값을 사용하여 데이터의 유무를 확인하거나 원본 데이터를 추출하는 작업 가장 간단한 해시 함수는 나머지를 반환하는 모듈러함수(%)를 사용 x를 입력 → (x%n) 연산 결과 반환 (해시 값 반환) → (x%n)위치에 x 값 삽입 모듈러 함수의 문제점은 서로 다른 데이터에 대해 같은 해시 값 반환 가능 (충돌 가능) 충돌 : 해시 함수가 서로 다른 ..
- Computer Science/Data Structure & Algorithm
- · 2023. 6. 29.
트리/힙/그래프(2) - 힙&그래프
1. 힙 원소 삽입 삭제에 대한 O(log N)의 시간 복잡도를 만족하기 위해 완전 이진 트리 사용 힙 구현 시 항상 최대원소가 트리의 루트에 위치 1) 힙 연산 (1) 원소 삽입하기 완전 이진 트리를 유지 → 트리의 마지막 레벨, 마지막 노드 오른쪽에 원소 추가 최대 원소가 트리의 루트에 위치하기 위해 새로 삽입한 원소의 크기를 비교하여 swap하는 과정을 거침 (2) 원소 삭제하기 가장 큰 원소만 삭제 가능 루트 노드와 마지막 노드를 교환한 후 마지막 노드를 삭제 최대 원소가 트리의 루트에 위치하기 위해 다시 루트 노드와 자식 노드의 크기를 비교하여 swap (3) 힙 초기화하기 힙은 불변성을 유지해야함→ 힙 생성 알고리즘으로 업데이트 아래쪽 서브 트리부터 힙 불변 속성을 만족하도록 힙을 업데이트 2..
- Computer Science/Data Structure & Algorithm
- · 2023. 6. 28.
트리/힙/그래프(1) - 트리
비선형 자료 구조 사용해야 하는 경우 판별 데이터 표현과 문제 해결을 위해 트리 / 그래프 구조 구현하여 사용 다양한 방법으로 트리 순회 주어진 상황에 맞게 다양한 방법으로 그래프 표현 1. 비선형 문제 1) 계층적 문제 조직도와 같이 계층적 속성을 가지는 문제 트리라는 자료 구조를 사용 데이터가 저장된 노드와 노드와 노드를 잇는 엣지로 구성 2) 순환 종속성 친구관계도와 같이 그래프로 표현 노드와 엣지로 구성 2. 트리 1) 연습 문제 7: 조직도 구조 만들기 #include #include struct node { std::string position; node* first; node* second; }; struct org_tree { node* root; static org_tree create_..
- Computer Science/Data Structure & Algorithm
- · 2023. 6. 27.
리스트 / 스택 /큐
1. 리스트 / 스택 / 큐 1) 연속된 자료구조/연결된 자료구조 (1) 연속된 자료구조 모든 원소를 단일 메모리 청크에 저장 각각의 원소는 모두 같은 타입 사용 → 같은 크기의 메모리 사용 →sizeof(type) 으로 표시 시작주소(Base Address)에서 sizeof(type)을 사용하여 i번째 주소에 접근 가능 BA + i * sizeof(type) 배열의 유형 정적배열 : 선언된 블록이 끝나면 소멸, 스택 영역에 할당되어 자동으로 해제 동적배열 : 배열의 생성 시점과 소멸 시점을 자유롭게 결정, 힙 영역에 할당되어 직접 해제 전까지 유지 (2) 연결된 자료구조 노드를 사용하여 여러 개의 메모리 청크에 데이터를 저장 → 서로 다른 메모리 위치에 저장 연결리스트 각각의 노드는 저장할 데이터와 다..
- Computer Science/Data Structure & Algorithm
- · 2023. 6. 26.