깊이우선탐색
-
알고리즘: 분기한정법(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)..
-
알고리즘: 되추적(Backtracking) 공부하기! (N-Queens problem을 풀어보자)알고리즘 2020. 11. 9. 20:11
되추적은 임의의 집합에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는데 사용한다. 전형적인 사례로 체스의 n-Queens Problem이 있다. 이 문제의 목표는 n x n 크기의 서양 장기판에 서로 잡아먹히지 않도록 n개의 여왕말을 위치시키는 것이다. 즉, 어떤 여왕말끼리도 같은 행이나 열, 대각선상에 위치할 수 없다. 이 문제에서 순서는 여왕말을 둘 n개의 각각 다른 위치이고, 집합은 서양 장기판에서 말을 둘 수 있는 n제곱개의 위치들이 되고, 기준은 어떤 여왕말도 서로 잡아 먹히지 말아야 한다는 것이다. 되추적은 트리의 변형된 깊이우선탐색(DFS)이다. DFS에 대해 간단히 설명하면 부모의 노드에서 내려갈 수 있는 자식노드까지 내려가고 그 이후의 자식 노드가 없다면 다시 부모노드로 돌아가면서..
-
알고리즘: 백준 11048번 이동하기 (feat. python)알고리즘/백준(BaekJoon) 2020. 8. 27. 22:42
백준 11048번 링크입니다. 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net DFS 인줄 알았지만 시간초과가 나길래 다시 보니 다이나믹프로그래밍이였던 문제 dp를 이차원 리스트로 만들어서 dp[N][M] = (N, M)까지 오기까지의 합이라고 한다면 dp[N][M] = max(dp[N - 1][M], dp[N][M - 1], dp[N - 1][M - 1]) + maze[N][M] 라고 할 수 있다. import sys input = sys.stdin.readline N, M = map(in..
-
알고리즘: 백준 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..