https://www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들자. C 중에서 B보다 작으면서 가장 큰 수 구하기 0으로 시작하면 안 됨 이 문제가 까다로웠던 것은 문자열과 숫자와의 변환이 헷갈려서! 0으로 시작하면 안 되니까 그것도 체크해줘야 한다! 우선 모든 순열을 구해봤다. 아슬아슬하게 통과.. [모든 순열을 구한 경우] -> 676ms 🚨 import F..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net N일동 안 최대한 많은 상담 상담에 걸리는 시간 Ti, 상담 시 금액 Pi 백준이가 얻을 수 있는 최대 수익은? i일에 얻을 수 있는 최대 이익(dp[i]) 중 최대 이익 구하기 2중 for문 - i일에 상담해도 되는지 체크 (상담 기간 n일 넘으면 안 됨) - i일에 상담한다고 했을 때, 얻는 금액 - 0~i-1일을 순회하면서 - j일에 상담하면 i일에 상담할 수 있는지 체크 - 상담할 수 있다면, 금액 합치기 -> 여기서 그동안 dp[i]에 저장된 금액과 비교해서 최대 금액으로 갱신 [DP] import Foundation //i..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 백트래킹 문제인데, 실수가 잦아서 헤맸다. 격자가 나오길래 처음엔 BFS인가 했지만 다 읽어보니 격자는 뭐 사용도 안 한다. 치킨집(chickens)과 집(houses) 배열에 각각 좌표를 넣고 (tuple) chickens의 조합을 구하면 된다. 여기서 실수한 게 바로, 순열을 구했다는 것..!! 시간초과 발생... [1,2,4] = [2,4,1] = [4,1,2] = ....

https://www.acmicpc.net/problem/2992 2992번: 크면서 작은 수 정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다. 수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 www.acmicpc.net x를 구성하는 수로 모든 경우의 수를 진행하면 된다. 경우의 수 중에서 x보다 큰 수 중 가장 작은 수를 찾아야 하므로, answer에 값을 경신하면서 진행 x보다 작은 수는 패스하는 부분을 추가 하지 않았는데, 이 부분을 추가하면 시간이 더 줄어들 것이다. 예를 들어 321라는 수에서 1xx, 2xx는 이미 x보다 크지 않기 때문에 깊게 들어가면 안 된다. 516의 경우 탐색된..

https://www.acmicpc.net/problem/12101 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net 전형적인 백트래킹 문제. 최대한 모든 경우의 수를 보지 않게 하기 위해서 조건들을 넣어줬다. n을 만들 수 있는 k번째에 오는 경우의 수를 찾아야 하기 때문에 n을 만들 수 있는지 체크 k번째에 오는 경우의 수인지 체크 flag의 역할은 k번째 값이 없을 경우 -1을 출력하기 위함 && 경우의 수 줄이기 k번째 경우의 수를 출력한 뒤로는 다음 경우의 수에서 더 깊게 들어갈 필요가 없음 → if문으로 return 해버려서 깊게 들어..

https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 백트래킹은 DFS와 달리 불필요한 탐색은 하지 않는다. 그래서 앞의 키트에서 중량 500을 넘기지 못하면 뒷부분 키트도 사용해보지 않고 패스하도록 했다. (cnt == n 조건까지 들어가지 않고 패스하기) 500을 넘는 애들만 재귀호출 진행. import Foundation //input let nk = readLine()!.split(separator: " ").map{ Int(Str..

https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음 문제를 읽었을 땐 어떻게 하는 거야.. 흑흑 이랬는데 정작 풀어보니까 쉬운 문제였다... 백트래킹으로 생각하면 쉬웠는데 (DFS나 백트래킹이나..) 숫자를 그대로 두고 +로 할거냐 -로 할 거냐를 선택하면서 진행하면 된다. DFS로 지금까지 계산한 값에 numbers의 수를 더할지(0) 뺄지(1)를 넘겨주면 된다. target과 결과가 동일하면 ans++ 이런 형태의 코드를 볼때마다 내가 혼..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 크기가 양수 == 부분 수열 속 원소 1개 이상 (1개 가능) 주의) 연속된 부분 수열이 아님 [백트래킹] #include #include using namespace std; int n, arr[21], s, ans = 0; void BT(int cnt, int sum){ if(cnt == n){ //arr의 끝까지 간 경우 if(sum == s) ans++;..

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 도시가 ..