다이나믹 프로그래밍 (2) - P/NP,플로이드-워셜 알고리즘
1. P와 NP 입력 데이터 크기가 증가함에 따라 문제 해결의 복잡도가 어느 정도까지 향상되는지 파악 P 문제 : 다항 시간내에 해답을 구할 수 있음을 의미 시간 복잡도가 $O(n), O(n^2), O(log n)$ NP 문제 : 비결정적 다항 시간문제 주어진 문제의 솔루션을 검증하는 것은 쉬우나 실제 솔루션을 만드는 일은 매우 어려움 NP의 많은 문제들은 NP-완전으로 알려져 있음 특별한 특성을 공유 다항 시간처럼 효율적으로 해결하는 솔루션이 발견 → 다른 문제에도 적용 가능 2. 부분집합의 합 문제 다시보기 특정 부분집합에 대한 유효성 검증은 각 부분집합의 원소를 모두 더하여 목표치와 같은지를 검사하는 방식 검증에 대한 복잡도는 부분집합 크기에 대해 선형 관계 만족 부분집합의 합 문제를 O(n*m) ..
- Computer Science/Data Structure & Algorithm
- · 2023. 7. 6.
다이나믹 프로그래밍 (1) - 부분집합의 합 / 문자열 시퀀스
0. 들어가며 분할 정복 패러다임 개념을 확장 매우 복합적이며 창의력과 인내심, 추상적 개념을 시각화하는 능력을 요구하는 경우가 많음 다이나믹 프로그래밍이 자주 사용되는 몇 가지 예 조합 (특정 기준을 만족하는 시퀀스의 조합 또는 순열의 개수 구하기) 문자열과 시퀀스 (편집 거리, 최장 공통 부분 시퀀스, 최장 증가 부분 시퀀스) 그래프 (최단 경로 문제) 머신러닝 (음성/얼굴인식) 1. 동적 계획법(Dynamic programming)이란? 피보나치 수열을 통한 동적 계획법 설명 피보나치의 재귀조건 : $F(n) = F(n-1) + F(n-2)$ 피보나치의 기저조건 : $F(0) , F(1)$ 하향식 방법 : 재귀 트리의 맨 꼭대기서 시작하여 기저 조건에 닿을 때까지 이동 피보나치의 경우 여러 개의 부..
- Computer Science/Data Structure & Algorithm
- · 2023. 7. 5.
그래프 알고리즘(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.