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 이 문제는 백트래킹으로 1~N개의 도시를 모두 돌면 된다. 그러니까 N개를 골라서 걸리는 비용을 구하고 최소 비용을 구하면 된다. 시작 도시로 다시 돌아가야 되니까 마지막 도시에서 첫 도시로 돌아가는 비용도 더해줘야 한다. vector에 도시를 넣어서 순서가 정해지면 이 도시들을 i, i+1 사이의 비용을 sum에 더하는데 마지막 도시는 i+1 도시가 ..

https://www.acmicpc.net/problem/10973 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net https://nyeoungkm.tistory.com/entry/백준c-10972번-다음-순열 [백준/c++] 10972번: 다음 순열 https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net.. nyeoungkm.tistory.com 다음 순열을 구하는 방법을..

https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 이 문제는,, 백트래킹을 하면 시간 초과 발생한다. 그래서 고민 좀 하다가 다른 사람이 푼 방법을 봤는데 도저히 내가 생각해낼..ㅋㅋ 게 아니었다ㅠ 그래서 이번 문제를 통해 공부를 하고 다른 문제에 응용할 수 있도록 해야겠다. 다음 순열을 찾는 건 사전 순의 정렬 원리를 그대로 구현해야 한다. 예를 들어, 1 2 5 4 3 의 다음 순열은? 뒤에서부터 바꿔나가야 한다. → 뒤에서부터 이어진 증가 순열의 끝을 찾아야 한다. 맨 뒤(n-1)에서부터 앞으로 나가..

https://www.acmicpc.net/problem/18290 18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net 이 문제는 BackTracking인데, BFS/DFS의 dx, dy 유형을 가미한 것 같다. BT에서 k개를 선택했으면 ans를 max value로 갱신하고 나가는 기저 조건은 동일한데, 여기서 인접 칸은 선택하면 안 되는 게 관건이다. 이를 위해서, 칸을 선택하기 전에 이 칸의 인접한 칸이 선택되어있는지 체크해줘야 한다. 인접칸이 선택되어있다면 이 칸은 선택하면 안 되기 때문! 선택하..

https://www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net https://nyeoungkm.tistory.com/entry/백준c-17427번-약수의-합-2 [백준/c++] 17427번: 약수의 합 2 https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2..

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 이 문제는 1000000까지의 소수를 먼저 찾고 시작했다. 에라토스테네스의 체 알고리즘으로 빠르게 소수를 찾을 수 있다. 이를 벡터 v에 넣어놓고 여러 테스트 케이스 값을 받아서 답을 출력한다. 여기서 소수 && 홀수이기 때문에 소수&&홀수의 합을 찾기 위해 for문을 돌릴 때, 1부터 시작해야 한다. v [1] = 3 v [0]는 2이므로 안됨..! n보다 작은 값들의 합..

https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net try 01 N보다 작거나 같은 자연수의 약수를 모두 구하고 그 값을 더 했다. 역시나 시간 초과 (제한시간 0.5초 일 때부터 알아봤다..ㅜ) [시간 초과 나오는 코드] int countNumber(int x){ int cnt = 1; //1 for(int i=2; i> n; int sum = 1; //N보다 작거나 같은 자연수의 약수 ..

https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 1로만 이루어진 n의 배수란, 1로만 이루어진 수 && n의 배수 1로만 이루어진 수는 1, 11, 111, 1111,.... 이런 식의 수다. 그러므로 1로만 이루어진 수를 쭉 만들면서 n의 배수인지 체크만 해주면 쉽게 풀 수 있는 문제. 1로만 이루어진 수 만들기 규칙! 1 => 0 * 10 + 1 11 => 1 * 10 + 1 111 => 11 * 10 + 1 1111 => 111 * 10 + 1 11111 => 1111 * 10 + 1 #includ..

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제를 풀기 전에, 소수를 찾는 굉장히 빠른 유명한 알고리즘이 있다. 이 알고리즘부터 구현해보고 가자. 에라토스테네스의 체 : 소수를 찾는 방법 (대량의 소수를 구할 때, 아주 유용한 알고리즘 O(N^1/2) → 1을 제외한 수의 배수가 되는 수는 소수가 아님 임의의 수 n까지의 소수를 구하고자 할 때 2부터 n의 제곱근까지 돌면 모든 배수들을 소수에서 제외시키는 방식 배열을 통해서 소수에서 제외했는지 안 했는지를 관리할 수 있..