728x90 Baekjoon/[Code.plus] 알고리즘 기초 2／261 [BOJ/백준] 10971 외판원 순회 2 ● [문제번호 10971] 10971 외판원 순회 2 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 : 재귀 ● 풀이 과정 : 순열을 가지고 요리조리 하는 것 같아 고민을 많이 했다. 그러다가 하드코딩해서 구현을 했는데, '시간 초과' 가 나왔다. 왜 그런지 고민을 해보니 중복되는 부분이 많았다. 왜냐하면 구하고자하는 값에는 같은 사이클들 중 순서가 필요없다. 예를 들어.. 2021. 9. 2. [BOJ/백준] 10819 차이를 최대로 ● [문제번호 10819] 차이를 최대로 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net ● 알아야 할 것 : 브루트 포스 (Brute Force) : 재귀 ● 풀이 과정 : N과 M (5) 문제에서 (조건말고) 작업을 추가한 정도의 문제 같다. : 특별한 것 없이 재귀를 이용한 DFS의 형태로 구현했다. ● 주의 할 것 : NULL ● 참고 할 것 : N과 M (5) https://pirateturtle.tistory.com/247 ● 풀이 코드 #incl.. 2021. 9. 2. [BOJ/백준] 10974 모든 순열 ● [문제번호 10974] 모든 순열 https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net ● 알아야 할 것 : 브루트 포스 (Brute Force) : 재귀 ● 풀이 과정 : 이전에 있었던 다음 순열, 이전 수열 문제 보다는 N과 M (1) 문제와 거의 동일했다. : 특별한 것 없이 재귀를 이용한 DFS의 형태로 구현했다. ● 주의 할 것 : NULL ● 참고 할 것 : 15649 N과 M (1) https://pirateturtle.tistory.com/243 ● 풀이 코드 #include using namespace std; // n.. 2021. 9. 2. [BOJ/백준] 10973 이전 순열 ● [문제번호 10973] 이전 순열 https://www.acmicpc.net/problem/10973 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net ● 알아야 할 것 : NULL ● 풀이 과정 : 다음 순열 문제에서 부등호만 잘 바꿔주면 된다. : 다음 순열 문제와 같은 원리로 1. 기존 수열의 맨 오른쪽부터 하나씩 {왼쪽 원소} > {오른쪽 원소} 인지 검사한다. 2. 조건에 맞으면 그 왼쪽 원소(기준 : 값교환해도 index는 그대로)를 중심으로 오른쪽에 존재하는 원소들 중에서 '기준보다 작은 값 중 가장 큰 값' 을 찾으면 된다. 3. 그렇게 찾은 값을 기.. 2021. 9. 2. 이전 1 ··· 10 11 12 13 14 15 16 다음 728x90
