백트래킹 (14) 썸네일형 리스트형 [C++] 3234번 준환이의 양팔저울 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWAe7XSKfUUDFAUw 25/02/06 가지치기를 "잘"해야 하는 백트래킹 문제다. 나이브하게 무지성으로 탐색하면 시간 초과의 늪에 빠지기 쉽다. 그래서 최적화를 두 번 해야하는데, 내가 풀었던 흐름대로 해설하고자 한다. 문제 접근 방식: 문제를 확인하면 특정 조건을 만족하는 순열의 수를 구하는 것이 목적이다. 또한 문제의 제한도 $N = 9$까지로 매우 작아서 백트래킹이 잘 동작할 것이라는 어떤 믿음이 존재할 것이다. 백트래킹 문제를 좀 풀어봤다면 나이브한 백트래킹 코드는 금방 짤 수 있을 것이라고 확신한다. 나이브한 코드는 다음과 같다.// SWEA323.. [C++] 1952번 [모의 SW 역량테스트] 수영장 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq 25/02/06 전형적인 DP문제이다. 제한이 작아서 백트래킹으로도 해결할 수 있다. 문제 접근 방식: 문제의 요구 사항은 각 달의 이용횟수가 주어지고, 하루 이용권, 한 달 이용권, 세 달 이용권, 1년 이용권의 가격이 주어질 때 수영장을 이용할 수 있는 최소 비용을 구하는 것이다. 나는 다음과 같이 생각했다. 어차피 1달, 3달, 1년 이용권은 중간에 사용할 수 없다. 정확히 말하면 중간에 사용하는 것이 손해이다. 예를 들어, 내가 1월에 5번 이용해야 하는데 하루는 하루 이용권을 사서 이용하고, 나머지 4일은 1달 이용권으로 이용.. [C++] 1007번 벡터 매칭 https://www.acmicpc.net/problem/1007 24/12/26 약간의 아이디어가 필요한 브루트포스 문제이다. $N$의 제한이 $20$으로 수상하게 작은데, 어떻게 하면 효율적으로 탐색할 수 있는지를 고민하면 해결할 수 있다. 문제 접근 방식: 시작 점과 끝 점을 정해서 이음으로써 하나의 벡터를 만들 수 있다. 이렇게 해서 $N$개의 점으로 $N/2$개의 벡터를 만들 수 있는데, 이 벡터들의 합의 길이의 최솟값을 구하는 것이 문제의 목적이다. $N$의 제한이 $20$으로 수상하게 작은 것을 쉽게 관찰할 수 있는데, 효율적으로 브루트포스를 해야함을 확인할 수 있다. 시작 점 $S$과 끝 점 $E$로 이루어진 하나의 벡터 $\mathbf{V}$가 주어지면, 이 벡터는 시작 점이 $O$이.. [Python] 21772번 가희의 고구마 먹방 https://www.acmicpc.net/problem/21772 24/05/14 업다운 랜디를 하다가 만난 문제이다. 처음에는 BFS로 접근할까 하다가 DFS로 방향을 틀어 접근했다. 문제 접근 방식: BFS로 접근할 수도 있다. 그 이유는 최대 10번을 탐색하고 한 번 할 때 4방향을 탐색하기 때문에 $4^{10}$번만 탐색하면 충분하고, 이는 시간 안에 들어오기에 충분하기 때문이다. 하지만 DFS로 접근하는 것이 더 쉬울 것 같아서 DFS로 접근했다. 무의식 중에 재귀 깊이를 10만으로 늘린 코드를 작성하긴 했지만, 사실은 10번만 탐색하기 때문에 그렇게까지 깊게 늘리지 않아도 되었던 것 같기도 하다. DFS를 진행하는데, 들어간 자리에 고구마가 있으면 고구마를 먹었다는 표시로, 고구마 글자를.. [Python] 30959번 앙상블할래? https://www.acmicpc.net/problem/30959 24/05/14 간단한 브루트포스 문제다. 파이썬은 이러한 문제에 있어서 쉽게 구현을 할 수 있어서 좋은 것 같다. 문제 접근 방식: $N$의 제한이 $16$까지이고, 항상 홀수 개의 모델만 선택한다고 했으므로 전수조사를 해도 충분히 시간안에 들어올 수 있음을 생각할 수 있다. 하나의 조합을 통해 앙상블을 구성하는 것은 조합의 크기와 예측 항목의 개수를 곱한 크기에 비례함을 확인할 수 있다. 그 수가 그렇게 많지 않으므로, 모든 조합을 확인해보면 된다. 파이썬의 itertools 모듈의 combinations함수를 사용하면 n개 중 r개를 선택하는 모든 조합의 경우들을 확인할 수 있으므로, 이를 사용하여 쉽게 구현할 수 있다. 인덱스.. [Python] 1038번 감소하는 수 https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 24/01/16 백트래킹 혹은 브루트 포스로 구현할 수 있는 유명한 문제이다. 비트마스킹을 이용해 구현하는 색다른 방법을 발견하여 적어보고자 한다. 기존 문제 접근 방식: 처음 문제를 접근했을 때에는 문제의 조건을 만족하는 함수 bruteforce를 작성했었다. 이 함수는 재귀적으로 호출을 하는 함수로, 호출을 받을 때마다 인자로 받은 현재 숫자를 리스트에 추가하고, 조건을 만족하도.. [Python] 17370번 육각형 우리 속의 개미 https://www.acmicpc.net/problem/17370 17370번: 육각형 우리 속의 개미 무한히 많은 정육각형이 서로 맞닿아 놓인 형태의 개미 우리가 있다. 다음 그림과 같은 형태이고, 하얀색 변으로만 개미가 다닐 수 있다. 개미 우리의 모습 곤충 관찰이 취미인 유이는 세 정육각 www.acmicpc.net 23/09/25 육각형을 어떻게 적절하게 잘 변형시키는 가가 관건인 문제다. 문제 접근 방식: 문제를 처음 보고 규칙성이 있는 DP문제인 줄 알고 한참 동안 점화식을 찾아 해맸다. 이후 규칙성이 없음을 깨닫고 백트래킹으로 접근했다. 이 문제의 핵심은 육각형을 어떻게 적절하게 잘 변형 시킬 수 있는가 이다. 일반적인 2차원 격자로는 상하좌우로 움직이기 때문에 120도 만큼을 돌아가는 것.. [Python] 30518번 짜고 치는 가위바위보 (Small) https://www.acmicpc.net/problem/30518 30518번: 짜고 치는 가위바위보 (Small) 이 경우는 smallant가 기존에 주어진 PP를 그대로 사용하거나, 첫 번째 P만 취하거나, 두 번째 P만 취하여 결승을 진행한다면 관중들이 분노하지 않는다. www.acmicpc.net 23/11/05 내가 만든 문제다. 문제 접근 방식: 먼저 문제부터 읽어보자. 문제는 Large버전과 동일하다. 다만 제한이 조금 다르다. 제한에 주목해 보자. 제한은 $N = 20$까지인 것을 확인할 수 있다. 관객들이 분노하지 않는 경우는 오직 smallant가 내고자 하는 가위바위보 정보에 달려 있음을 알고 있고, 이를 부분적으로 취하는 경우의 수는 $2^N$개라는 것을 알고 있다. (부분집합의 .. 이전 1 2 다음
