코테 챌린지
지난주에 일정이 너무 많아서
못 했고,,,
이번주도 정처기 실기가 있는 관계로
설렁설렁하다
정처기 실기 끝나면
다시 루틴 기강 잡겠습니다,,,
문제
퀴즈 대회에 참가해서 우승을 하게 되면 보너스 상금을 획득할 수 있는 기회를 부여받는다.
우승자는 주어진 숫자판들 중에 두 개를 선택에서 정해진 횟수만큼 서로의 자리를 위치를 교환할 수 있다.
예를 들어, 다음 그림과 3, 2, 8, 8, 8 의 5개의 숫자판들이 주어지고 교환 횟수는 2회라고 하자.
교환전>
처음에는 첫번째 숫자판의 3과 네 번째 숫자판의 8을 교환해서 8, 2, 8, 3, 8이 되었다.
다음으로, 두 번째 숫자판 2와 마지막에 있는 8을 교환해서 8, 8, 8, 3, 2이 되었다.
정해진 횟수만큼 교환이 끝나면 숫자판의 위치에 부여된 가중치에 의해 상금이 계산된다.
숫자판의 오른쪽 끝에서부터 1원이고 왼쪽으로 한자리씩 갈수록 10의 배수만큼 커진다.
위의 예에서와 같이 최종적으로 숫자판들이 8,8,8,3,2의 순서가 되면 88832원의 보너스 상금을 획득한다.
여기서 주의할 것은 반드시 횟수만큼 교환이 이루어져야 하고 동일한 위치의 교환이 중복되어도 된다.
다음과 같은 경우 1회의 교환 횟수가 주어졌을 때 반드시 1회 교환을 수행하므로 결과값은 49가 된다.
94의 경우 2회 교환하게 되면 원래의 94가 된다.
정해진 횟수만큼 숫자판을 교환했을 때 받을 수 있는 가장 큰 금액을 계산해보자.
입력
가장 첫 줄은 전체 테스트 케이스의 수이다.
최대 10개의 테스트 케이스가 표준 입력을 통하여 주어진다.
각 테스트 케이스에는 숫자판의 정보와 교환 횟수가 주어진다.
숫자판의 정보는 정수형 숫자로 주어지고 최대 자릿수는 6자리이며, 최대 교환 횟수는 10번이다.
출력
각 테스트 케이스마다, 첫 줄에는 “#C”를 출력해야 하는데 C는 케이스 번호이다.
같은 줄에 빈 칸을 하나 사이에 두고 교환 후 받을 수 있는 가장 큰 금액을 출력한다.
내 풀이
백트래킹 사용
접근 방식
숫자판과 교환 횟수 입력: 각 테스트 케이스마다 숫자판과
교환 횟수를 입력받기백트래킹 사용: 백트래킹을 사용하여 가능한 모든 교환 조합을 시도
최대 값 갱신: 모든 교환을 시도하면서 가장 큰 숫자를 유지
결과 출력: 각 테스트 케이스마다 결과를 출력
구현 방법
입력 처리: 숫자판을 문자열로 받아서 자리 교환을 쉽게 처리
백트래킹 함수: swap 함수를 사용하여 자리 교환을 하고,
교환 횟수가 0이 될 때까지 재귀적으로 호출
최대 값 갱신: 각 단계에서 현재 숫자가 최대인지 확인하고, 최대 값을 갱신
위의 방법 사용 시 시간초과 뜨기 때문에 아래 방법 추가
최적화 전략
메모이제이션: 이미 방문한 상태를 기록하여 동일한 상태를 다시 방문하지 않도록 하기
정렬 후 우선순위 큐 사용: 가능한 가장 큰 수를 우선적으로 탐색하도록 하기
void find_max(string num, int swaps) {
if (swaps == 0) {
if (num > max_number) {
max_number = num;
}
return;
}
string original_num = num;
if (visited[original_num + to_string(swaps)]) {
return;
}
visited[original_num + to_string(swaps)] = true;
int len = num.length();
for (int i = 0; i < len - 1; ++i) {
for (int j = i + 1; j < len; ++j) {
swap(num[i], num[j]);
find_max(num, swaps - 1);
swap(num[i], num[j]);
}
}
}최적화 코드 설명
메모이제이션:
unordered_map<string, bool> visited;를 사용하여 이미 방문한 상태를 기록.
상태는 현재 숫자 문자열과 남은 교환 횟수를 조합한 문자열로 정의.
if (visited[original_num + to_string(swaps)]) 조건을 사용하여 이미 방문한 상태인지 확인. 방문한 상태라면 더 이상 탐색하지 않기visited[original_num + to_string(swaps)] = true;를 통해 현재 상태를 방문했음을 기록
백트래킹 최적화:
이전 코드와 동일하게 이중 for 루프를 사용하여 가능한 모든 자리 교환을 시도
각 교환 후 재귀적으로 find_max를 호출합
교환 후 원래 상태로 복구하기 위해 다시 swap
그래서 백트래킹이 뭐야? 하실 수 있기 때문에
한번 더 짚고 넘어가겠슴돠
백트래킹(Backtracking)은 주어진 문제를 해결하기 위해 가능한 모든 후보를 하나씩 검사하면서 조건에 맞지 않는 후보를 제거하고 최적의 결과를 찾는 알고리즘 기법
백트래킹은 탐색 트리를 기반으로 동작하며, 주로 재귀를 통해 구현.탐색 공간 정의: 가능한 모든 후보를 탐색
유망성 검사: 현재 후보가 조건에 맞는지 검사
조건에 맞지 않으면 더 이상 진행하지 않고 되돌아감(백트래킹)
재귀적으로 진행: 조건에 맞는 경우 다음 단계로 진행
해결책 찾기: 최종적으로 문제를 해결하는 후보를 찾기보통 백트래킹은 주어진 문제의 모든 가능한 해를 탐색하면서
최적의 해를 찾는 데 유용.
하지만 가능한 해의 수가 많아질 경우 시간 복잡도가 급격히 증가할 수 있으므로, 가지치기(pruning) 기법을 함께 사용하여 불필요한 탐색을 줄이는 것이 중요!!!!!!!!!!!!!!
예를 들어, 위의 최적화된 코드에서는 메모이제이션을 통해 이미 방문한 상태를 기록하여 중복 탐색을 피했음!!!!!!!!!!!!!
그렇다면 여기서 메모이제이션이 뭔지 궁금해하실 수 있잖아요??
메모이제이션(Memoization)은 재귀 호출이나 동적 프로그래밍(dynamic programming)에서 동일한 계산을 반복하지 않도록 결과를 저장해두는 기법
시간 복잡도를 크게 줄이고, 주로 반복되는 중복 계산을 줄이는 데 사용.메모이제이션의 기본 개념
문제 분할: 큰 문제를 여러 개의 작은 문제로 나누기
저장: 각 작은 문제의 결과를 저장
재사용: 동일한 작은 문제가 다시 발생하면 저장된 결과를 재사용
백트래킹, 메모이제이션 기억,,,!!!!!!!!!!!!!!
