컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 알고리즘 dfs를 이용해 자리를 바꿔보고 K번 만큼 바꾼 후 가장 큰 값을 출력한다. 이 때 같은 수가 나올 수 있으므로 visited배열을 이용해 중복되는 값은 배제한다. 소스 코드 #include using namespace std; bool check[1000001][11]; string str; int m; int result = 0; void dfs(int K){ if(str[0] == '0') return; if(K == 0){ result = ..

https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 문제 해결 알고리즘 비숍의 특성을 이해해야하는 문제. 체스판에 검은색 타일의 비숍과 흰색 타일의 비숍은 서로 공격할 수 없다. 그렇기 때문에 검은색 비숍과 흰색 비숍을 따로 구분해서 깊이 우선 탐색을 진행해야할 필요가 있다. 만약에 그냥 색깔 상관없이 모든 타일의 비숍을 한 번에 깊이 우선탐색을 진행한다면 시간초과가 난다. 그렇게 한다면 시간 복잡도는 $O(2^{(N*N)})$ 이지만 위의 방식대로 색깔 ..

https://www.acmicpc.net/problem/2239 https://www.acmicpc.net/problem/2580 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 해결 알고리즘 이 두개의 문제가 결이 같아서 같이 정리한다. 우선 입력을 받..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 해결 알고리즘 백트래킹, 깊이 우선 탐색 문제 (0, 0)부터 DFS를 해주는데 이 때, 문제에서 나온 것처럼 중복되는 알파벳을 체크해주는 배열과, 지나온 자리들을 체크해주는 배열을 각각 두고 탐색하는데 시간을 아낀다. 나머지는 그냥 전형적인 백트래킹이다. 소스 코드 #include using namespace std; int R, C; char arr[21][21]; bool vis..

https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 문제 해결 알고리즘 전형적인 dfs 문제 소스 코드 C++ #include #include using namespace std; int answer = 0; void dfs(vector v, int target, int sum, int idx){ if(idx == v.size()){ if(target == sum) answer++; ret..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 해결 알고리즘 모든 노드에서 시작하는 DFS를 활용해서 문제를 풀어준다. 이 때 n이 1이면 런타임 에러가 나니 예외처리를 해주어야한다. 소스 코드 #include using namespace std; vector tree[100002]; vector resultArr; int maxValue = 0, result = 0; bool visited[100002]; void ..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제 해결 알고리즘 모든 노드를 탐색하는데 탐색할 때 연결된 노드들을 전부 DFS로 탐색해준다. 탐색이 안 된 곳(cc[i]가 0인 곳)을 계속해서 DFS로 탐색해주면서 연결요소마다 번호를 매겨준다. 마지막에 그 연결요소의 마지막 번호를 출력한다. 소스 코드 #include using namespace std; int cc[1001];..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 알고리즘 DFS로 푸는데 각 마디별로 부모를 저장해주고 메모리 초과가 나지 않게 인접행렬보다는 인접리스트를 사용해주었다. 소스 코드 #include using namespace std; int parent[100002]; vector graph[100002]; void find_parent(int x){ for(int i=0;i> N; int A, B; for(int i=1;i> A >> B; graph[A].push_back(B); graph[B]..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 해결 알고리즘 DFS를 활용해 백트래킹 기법으로 모든 도시들을 탐색한 후에 가장 적은 비용을 출력해준다. 소스 코드 #include using namespace std; int N; int W[11][11]; bool visited[11]; int result = 99999999; bool visitedCheck(){ for(int i=2;i N;..

되추적 (Back Tracking) 틀린 답에 접근했을 때, 틀리기 전의 상태로 돌아가서 다른 선택을 하는 알고리즘 만약 답이 나올 때까지가 시간 복잡도가 엄청 복잡하게 나올 수도 있지만, 이 답이 유망했는지 아닌지를 판별하면서 불필요한 노력을 절감할 수 있다. 되추적은 트리의 변형된 깊이우선탐색(DFS)이다. 깊이 우선 탐색 (depth - first search) 부모 마디 우선(preorder) 트리 검색은 트리의 깊이 우선 검색이다. 이는 뿌리마디(root)를 먼저 방문한 후, 그 뿌리마디(node)의 후손들을 모두 방문한다. 예시로는 왼쪽에서 오른쪽의 순서로 마디의 자식을 방문한다. 다음은 깊이우선검색을 하는 간단한 재귀 알고리즘을 쓰는 프로시저이다. void depth_first_tree_se..