728x90 백준브실골/Backtracking2 백준 8905, 리트 개요 문제 링크 골드 3, 백트래킹 알파벳 소문자를 최대 3자리의 문자로 변형하여 다른 문자열을 구성할 수 있는지 확인하기 접근 백트래킹 연습좀 하려고 풀었는데 제한시간 2초에 1932ms으로 통과해버렸다. 당당한 꼴등이 되어보자. 아마 시간이 오래 걸린 이유는 string의 +연산을 그대로 때려박아서 그런 것일텐데, 이해하기 쉬우니 재채점 뜨기 전까지는 냅두려한다. 백트래킹의 핵심은 현재상태, 다음상태, 종료조건, 그리고 가능여부 출력 이라고 했다. 현재상태는 i번째를 바꾸는 상황으로 했다. 다음상태는 i+1이 아니라 i+k번째인데, k개만큼 문자열을 바꿔줄것이기 때문이다. 종료조건은 i = b의 길이 이면서 a == b인 상황으로 했다. 재귀문을 돌려보자. 처음에는 combination으로 길이가 1.. 2023. 2. 22. 백준 4574, 스도미노쿠 개요 문제 링크 골드 1, 백트래킹 36개의 1×2 조각을 이용해 스도쿠 완성하기 접근 백트래킹의 대표적 문제 스도쿠이다. 아마 많이 알려져있어서 익숙할 것이다. 백트래킹의 핵심은 항상 다음단계와 끝단계, 그리고 출력은 가능여부 라는 것이다. 백트래킹은 재귀를 활용하는데, 입력은 i번째 점을 넣어준다. 스도쿠에는 81개의 점이 있으니, 81번째 점에 도달했다는 것은 모든 점을 채웠다는 것이므로, 끝단계 -> i=81이 된다. 문제의 답이 유일하므로, i번째 점을 채워주고, 다음단계가 가능하면 1을 return해서 바로 다음단계로 넘어가버린다. 그렇지 않다면 i번째 점에 할당할 수 있는 모든 경우의 수를 할당해본 뒤 0을 출력한다. 이렇게 해주면 모든 경우의 수를 파악하면서도 빠르게 해줄 수 있다. 1×2.. 2023. 2. 22. 다음 728x90