백트래킹14 [백준 1339] 단어 수학 www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 백트래킹 문제여서 백트래킹으로 풀었더니 답은 맞았지만 엄청나게 시간이 오래 걸렸다. 아래 제출한 기록이 백트래킹으로 풀었을 때 걸리는 시간이다. 백트래킹 로직은 1. 사용된 모든 알파벳을 담은 후 2. 각 알파벳에 숫자를 매칭시켜서 (백트래킹) 3. 최댓값을 구한 것이다. #include #include #include #include using namespace std; vector v(11); int .. 2021. 2. 9. [백준 10971] 외판원 순회2 www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 브루트 포스 문제의 일종이다. np problem중 하나로 인터넷에 검색해보면 dp + bit mask로 많은 풀이가 있다. dp와 bit를 사용해서 풀기 전에 일반적인 dfs접근을 해보려고 한다. 문제에 대한 분석 1. 외판원 순회 문제 모든 도시들을 한번만 방문하여 처음 출발한 도시로 돌아올 때 최소 비용을 구하는 문제이다. 2. 출발 도시는 상관없다. 왜냐 어차.. 2021. 2. 5. [백준 1145] 적어도 대부분의 배수 www.acmicpc.net/problem/1145 1145번: 적어도 대부분의 배수 첫째 줄에 다섯 개의 자연수가 주어진다. 100보다 작거나 같은 자연수이고, 서로 다른 수이다. www.acmicpc.net 백트래킹과 최소 공배수를 사용했다. 숫자가 5개라서 백트래킹을 돌렸다. 숫자 5개 중 3개를 선택하여 최소 공배수를 구한 후 가장 작은 값을 리턴한다. #include #include #include using namespace std; int res = 1000000; int arr[5]; vector selected; int gcd(int a, int b) { while (b) { int r = a % b; a = b; b = r; } return a; } int lcm(int a, int b.. 2020. 12. 21. [백준 17141] 연구소 2 www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net dfs + bfs 문제이다. 대부분의 구현 문제와 유사하게 backtracking을 사용하여 연구소를 선택하고 m = cnt라면 bfs를 진행하는 구조이다. 문제 특성상 이차원배열 2개를 사용하는 것이 좋다. 하나는 벽과 빈곳, 연구소를 표현하기 위한 오리지널 배열과 바이러스가 퍼지는 경로를 나타내는 배열 2가지가 필요하다. 경로 배열은 bfs시작시마다 매번 초기화해줘야 한다. 아니면 이전 경로가 저장되어 값이 잘못나온.. 2020. 12. 19. 이전 1 2 3 4 다음
