너비우선탐색
-
알고리즘: 분기한정법(Branch-and-bound)을 이용한 0-1 배낭채우기문제 (0-1 knapsack problem) 공부하기!알고리즘 2020. 11. 15. 21:31
이번 포스팅은 분기한정법(branch-and-bound)을 이용한 0-1 배낭채우기 문제에 대해서 알아본다. 이전의 포스팅에서는 동적계획법(Dynamic programming)과 되추적(Backtracking)을 이용한 0-1 배낭채우기에 대해서 알아봤었다. 알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem) 탐욕 알고리즘과 동적계획법은 최적화 문제를 푸는 두가지 방법이다. 둘 중 어떤 방법을 사용해도 문제를 풀 수 있다. 단일 출발점 최단경로 문제에서는 동적계획법은 모든 마디를 출발점으로 seungjuitmemo.tistory.com 알고리즘: 되추적(BackTracking)을 이용한 0 - 1 배낭채우기 문제(0- 1 knapsack problem)..
-
알고리즘: 백준 1697번 숨바꼭질 (feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 23. 14:40
백준 1697번 링크입니다. 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net bfs를 이용하면 문제가 생각보다 쉽게 풀린다. 최대 가능 인풋이 100000이기 때문에 시간복잡도가 최대 n^2 까지 가능하다고 생각하였다. 최단거리 문제이기도 해서 bfs를 선택하였다. #include #include using namespace std; int visit[100001]; bool check(int x) { //check 함수가 중요한듯! if (x 100001) ret..