알고리즘74 백준 13305번 : 주유소 그리디 개념 : 미래를 생각하지 않고 각 단계에서 최선의 선택을 했을 때 전체적으로도 최선이 되는 경우에 사용 문제 링크 : www.acmicpc.net/problem/13305 내 풀이(2021.1.6.) : #include using namespace std; long long dist[100000 - 1]; long long cost[100000]; int min_index; long long min_cost = 1000000000; long long total_cost = 0; long long remaining_dist = 0; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N;.. 2021. 1. 6. DP(Dynamic Programming, 동적 계획법) 기초 개념 및 소스 설명 종만북(프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 1, 구종만 지음)에 있는 자료를 사용하였습니다. 한글 자막 있습니다. 2021. 1. 6. 백준 15654번 : N과 M (5) 문제 링크 : www.acmicpc.net/problem/15654 내 풀이(2021.1.5.) : #include #include #include using namespace std; vector list; bool visit[8]; int N, M; void search(vector& v) { // 해를 찾음 if (v.size() == M) { for (int i = 0; i < v.size(); i++) { printf("%d ", v[i]); } printf("\n"); return; } // 탐색 for (int i = 0; i < list.size(); i++) { if (visit[i] == true) continue; visit[i] = true; v.push_back(list[i]); .. 2021. 1. 5. 백트래킹 개념 출처 : chanhuiseok.github.io/posts/algo-23/ * 백트래킹 = 되추적 = Backtracking - 유망(promising)하면 탐색을 계속 진행하고, 유망하지 않으면 부모 노드로 다시 돌아가(Backtracking)는 기법 (유망하다 = 해가 될 가능성이 있다) - 다시 말해, 탐색 중 유망성 검사를 통해 가지치기(pruning)를 하는 기법 - DFS는 모든 노드를 탐색하지만, 백트래킹은 모든 노드를 탐색하지 않을 수 있다는 점에서, 성능 차이가 있음 - 자식 노드로 내려갈 때는 방문 표시를 하고, 부모 노드로 올라갈 때는 방문 취소를 함으로써, 방문 여부를 마치 스택처럼 관리해야 하는데, 이는 주로 재귀 함수의 전후에 방문 여부를 변경해주는 식으로 구현한다. (아래와 같.. 2021. 1. 5. 이전 1 ··· 11 12 13 14 15 16 17 ··· 19 다음