그래프 알고리즘(2) - 벨만포드, 존슨, 코사리주 알고리즘
1. 최단 경로 문제 다시 살펴보기 다익스트라 알고리즘은 성능 면에서 우수하나, 모든 그래프에 적용 불가능 그래프에 음수 가중치가 있을 경우 최적의 경로를 찾지 못하는 경우 발생 2. 벨만-포드 알고리즘 그래프의 모든 엣지에 대해 다익스트라의 그리디 선택 방법을 반복하여 점진적인 최단 거리 탐색 1) 연습 문제 32: 벨만-포드 알고리즘 구현하기 #include #include #include using namespace std; struct Edge { int src; int dst; int weight; }; const int UNKNOWN = INT_MAX; vector BellmanFord(vector edges, int V, int start) { vector distance(V, UNKNOWN..
- Computer Science/Data Structure & Algorithm
- · 2023. 7. 4.
그래프 알고리즘 (1) - BFS, DFS, 다익스트라 알고리즘
0. 들어가며 그래프는 정점의 집합과 정점들을 서로 잇는 에지의 집합으로 구성 그래프는 매우 유연한 자료구조 객체와 객체 사이의 관계를 표현 두 정점 사이에 여러 엣지를 가지기도 하고 하나의 엣지에 여러 가중치 부여하기도 하며 자신을 가르키는 셀프 엣지도 존재 주로 다루는 것은 방향 가중 그래프 1. 그래프 순회 문제 그래프의 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제 그래프 탐색 문제로도 불림 1) 너비 우선 탐색 (BFS, Breadth-First Search) 시작 정점을 경계에 추가하는 것으로 시작 경계는 이전에 방문했던 정점들에 의해 구성 현재 경계에 인접한 정점을 반복적으로 탐색 2) 연습 문제 28: BFS 구현하기 #include #include #include #includ..
- Computer Science/Data Structure & Algorithm
- · 2023. 7. 3.
그리디 알고리즘
0. 들어가며 매 단계에서 ‘가장 좋아 보이는’ 해답을 선택하는 알고리즘 지역적인 최적의 해결 방법 → 전역적인 최적의 해결 방법 1. 기본적인 그리디 알고리즘 1) 최단 작업 우선 스케줄링 평균 대기 시간을 줄이기 위해 일 처리가 가장 빠른 사람을 맨 앞으로 가장 빠른 사람을 선택→그리디 알고리즘 2) 연습 문제 24: 최단 작업 우선 스케줄링 #include #include #include #include template auto compute_waiting_times(std::vector& service_times) { std::vector W(service_times.size()); W[0] = 0; for(auto i=1; i
- Computer Science/Data Structure & Algorithm
- · 2023. 7. 2.
분할 정복
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.