본문 바로가기

알고리즘, 자료구조55

[백트래킹] 백준 2580 스도쿠 백트래킹을 알고 있다면, 그대로 하면 풀린다! 원리는 간단하다, 모든 경우를 탐색하는 것인데 빈칸에 들어갈 수 있는 후보자를 찾은 뒤, 처음 후보자를 놓고, 다음 빈칸을 같은 방법으로 탐색한다. 그러다가 막히면(후보자가 없다거나) 다시 돌아오면 된다 (백트래킹!) 주의할 것은, 스페셜 져지문제인 만큼 답이되는 후보 제일 먼저 발견한 것을 찾으면, 바로 프로그램을 종료하면 된다. 헤더파일에 있는 exit(0)함수를 썼다. 후보자를 찾기 위해 가로세로를 탐색하고, 사각형을 탐색하는데 아이디어만 잘 내면 될 듯하다! #include #include #include #include using namespace std; int N = 9; int a[9][9]; int dx[] = {-1, 1, 0, 0}; in.. 2019. 9. 19.
[백준] 15651 N과 M (4) - 중복조합 15650 N과 M (2)를 풀었다면, 정말 거저 먹는 문제이다! 시작하는 부분만 한 단계 낮추어, 중복이 가능하게 하면된다. 이것 역시 stack버전과, 그냥 배열을 쓴 버전 두가지를 참고하시라. #include int N, M; int a[10]; void repeated_combination(int depth, int start){ if (depth == M){ for (int i=0; i 2019. 9. 19.
[백준] 15651 N과 M (3) - 중복순열 15650 N과 M (2)를 풀었다면 정말 쉽게 풀리는 문제이다. #include int N, M; char a[15]; void repeated_permutation(int depth){ if (depth == M){ for (int i=0; i 2019. 9. 19.
[백준] N과 M (2) - 조합 조합. depth를 증가 시키는 것과, start를 하나 더 늘리는 것이 관건이다. 한 재귀함수가 호출되면, depth가 고정되어 있는 채로, start와 관련된 i 인덱스가 바뀌면서 다음 조합의 수를 채운다. #include int N, M; int a[9]; void combination(int depth, int start){ if (depth == M){ for (int i=0; i 2019. 9. 19.
[백준] 15649 N과 M (1) - 순열 단계별로 풀어보기에서 N과 M 시리즈 4개 중 개인적으로 가장 어렵다고 생각한다. 하지만, dfs와 백트래킹을 알고 있다면, N과 M문제 자체가 그렇게 어려운 편은 아니다. DFS는 그래프에서 깊이 우선 탐색을 의미하지만, 완전 탐색에서 주로 쓰이는 알고리즘으로, 모든 것을 다해보는 브루트포스 알고리즘과도 연관이 있다. 백트래킹은 여기에 조건을 더해주어, 원하는 경로로 탐색할 수 있게 도와주는 장치이다. 구현 코드 2개를 소개하고자 한다. #include using namespace std; int n, m; int a[8]; void swap_(int &a, int &b){ int temp = a; a = b; b = temp; } void rotateR(int start, int end){ int t.. 2019. 9. 19.
[SW Expert Academy] 1767. 프로세서 연결하기 DFS를 이용하지만, 조건이 덧붙여져있어서, return 되는 상황을 잘 생각해야하는 문제이다. 1) 전선이 연결된 코어 수는 최대가 되어야 하고, 2) 그 다음으로는, 전선 길이의 합이 최소가 되는 답을 찾으면 된다. 사실 이게 핵심이고, 나머지는 DFS이다. #include #include #include #include using namespace std; int N; int map_[12][12]; bool visited[12][12]; int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1}; vector cores; int core_num; int line_ans; void go(int startidx, int line_len, int core_cnt){ if (st.. 2019. 9. 18.
[BFS] 2206 벽 부수고 이동하기 #include #include using namespace std; struct Pos { int x, y, b; }; queue q; char a[1001][1001]; int dist[1001][1001][2]; int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}; int main() { int n, m; scanf("%d %d", &n, &m); for (int i=0; i 2019. 9. 12.
[백준] 1694 숨바꼭질 BFS를 잘 활용하면 되는 문제. 그래프를 잘 생각 해보자. 각 숫자들을 그래프의 노드라고 했을 때, 1만큼 떨어진 이웃하는 숫자는 양방향 간선으로 다 이어져 있고, x노드에서 2x노드로 가는 간선들이 있다. BFS는 모든 정점과 간선을 살펴보는 알고리즘이므로 시간복잡도는 O(|V| + |E|)인데, V = 100,000, E < 300,000 이면 충분할 거라고 생각했다. 참고로 memset에 사이즈를 sizeof(d)/sizeof(int) 라고 했다가.... 수없이 실패를 했던 문제이다. 나머지는 최단거리를 구하는 BFS문제로 직관적으로 쉽게 풀 수 있다. #include #include #include using namespace std; int d[100001]; int main() { int n.. 2019. 9. 12.
[BFS] 너비 우선 탐색 BFS (너비 우선 탐색) 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘 각 정점을 방문할 때마다 모든 인접 정점을 검사합니다. 처음 보는 정점을 발견하면 이 점을 방문 예정(discoverd)이라고 기록한 뒤, 별도의 위치(queue)에 저장합니다. 인접한 정점을 모두 검사하고 나면, 저장한 목록에서 다음 정점을 꺼내서 방문합니다. BFS (너비 우선 탐색)에서 새 정점을 발견하는데 사용했던 간선을 모은 트리를 BFS Spanning Tree(너비 우선 탐색 신장 트리) 라고 부릅니다. #include #include using namespace std; // Adjacent List vector adj; vector order; /* start 노드로부터 시작하여 너비 우선 탐색하여 각 .. 2019. 9. 9.
[DFS] 깊이 우선 탐색 DFS (깊이 우선 탐색) 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법. 현재 정점과 인접한 간선들을 하나씩 검사가하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있으면 그 간선을 따라간다. dfs(edge) 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 따라 뒤로 돌아간다. dfs 종료 #include using namespace std; // adjacent list vector adj; vector visited; /* Depth First Search node u --> v */ void dfs(int u){ visited[u] = true; // 모든 인접 정점을 순회하면서 for (int i = 0; i < adj[u].size(); ++i){ int v = adj.. 2019. 9. 8.
728x90

티스토리툴바