목록백트래킹 (50)

1일1알

백준 2239번 스도쿠 C++

행과 열의 정보를 이용해서 해당 열, 행, 속해있는 구역에 있는 숫자들을 unordered_set으로 관리하면서 들어갈 수 있는 숫자가 있다면 백트래킹을 이용해서 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; vector vr(10); vector vc(10); vector vs(10); vector board(10, vector(10, 0)); int GetSector(int row, int col) { int ret, r, c; ..
알고리즘 2022. 4. 4. 12:19
백준 15666번 N과 M (12) C++

일반적인 백트래킹으로 문제를 해결하였는데, 비내림차순이고 중복이 아닌 것들만 출력하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; set strs; int n, m; void dp(const vector& v, int cnt, vector &ans) { if (cnt >= m) { string str = ""; for (auto a : ans) { str += to_string(a) + " "; } if (strs.find(str) == strs...
알고리즘 2022. 4. 2. 11:49
백준 15663번 N과 M (9) C++

일반적인 백트래킹 문제인데, 중복을 포함하지 않게 하기 위해 string 타입의 set을 이용해서 중복된 숫자는 출력하지 않았다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; vector found(8, false); set strs; int n, m; void dp(const vector& v, int cnt, vector &ans) { if (cnt >= m) { string str = ""; for (auto a : ans) { str += to..
알고리즘 2022. 4. 1. 12:57
백준 1405번 미친 로봇 C++

백트래킹을 이용해서 마지막 이동까지 마쳤을 때 이동 경로가 단순한 로봇들이 지나온 길의 확률들만 모두 더하는 방식으로 문제를 해결하였다. 중간에 이미 방문한 곳을 가려고 하면 그곳은 탐색을 하지 않았다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int dRow[4] = { 0,0,1,-1 }; int dCol[4] = { 1,-1,0,0 }; vector visited(30, vector(30, false)); vector proV(4); int ..
알고리즘 2022. 3. 17. 12:19
백준 1987번 알파벳 C++

백트래킹을 이용해서 해결할 수 있는 문제이다. 처음에 방문한 알파벳을 set에 저장해서 이미 방문한 곳인지 확인해서 풀었더니 시간초과가 났다. 그래서 알파벳 개수의 크기의 visited 배열을 만들어서 방문 체크를 O(1)에 할 수 있도록 수정했더니 통과되었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int r, c; int ans = 0; int dRow[4] = { -1,0,1,0 }; int dCol[4] = { 0,1,0,-1 }; vec..
알고리즘 2022. 2. 27. 12:36
백준 14600번 샤워실 바닥 깔기 (Small) C++

k의 범위가 1~2이기때문에 바닥의 크기는 2 혹은 4이다. 바닥의 크기가 크지 않기 때문에 백트래킹을 이용해서 모든 경우를 탐색하여 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int dRow[8][2] = { {0,1}, {0,-1} ,{1,1} ,{1,1} ,{0,-1} ,{0,1} ,{-1,-1} ,{-1,-1} }; int dCol[8][2] = { {1,1}, {1,1}, {0,1}, {0,-1}, {-1,-1}, {-1..
알고리즘 2022. 2. 8. 14:04
이전 Prev 1 ··· 3 4 5 6 7 8 9 Next 다음