브루트포스 (23) 썸네일형 리스트형 [C++] 10246번 부동산 경매 https://www.acmicpc.net/problem/10246 25/01/05 간단한 수식 정리 문제인데, 나이브하게 돌려서 미리 계산해놓고 푸는 풀이도 꽤 빠른 것 같다. 문제 접근 방식: 각 테스트 케이스 별로 다음을 계산하면 된다. 두 수 사이의 연속 된 수들의 합으로 $N$을 표현할 수 있는 경우의 수. 유의할 점은 테스트 케이스의 개수가 안나와있고, 시간 제한은 10초이며, 실제로도 테스트 케이스의 개수가 매우 많다는 점이다. $N$의 범위가 $1 \ 000 \ 000$까지이기 때문에, 어떤 사람들은 미리 그 크기의 배열을 선언해두어 계산을 다 한 후에 쿼리를 처리하는 방식을 하기도 했다.(이 경우 쿼리 당 소요되는 시복도는 상수다.) 나의 경우는 수식으로 접근하여, 쿼리 당 $\mat.. [C++] 1007번 벡터 매칭 https://www.acmicpc.net/problem/1007 24/12/26 약간의 아이디어가 필요한 브루트포스 문제이다. $N$의 제한이 $20$으로 수상하게 작은데, 어떻게 하면 효율적으로 탐색할 수 있는지를 고민하면 해결할 수 있다. 문제 접근 방식: 시작 점과 끝 점을 정해서 이음으로써 하나의 벡터를 만들 수 있다. 이렇게 해서 $N$개의 점으로 $N/2$개의 벡터를 만들 수 있는데, 이 벡터들의 합의 길이의 최솟값을 구하는 것이 문제의 목적이다. $N$의 제한이 $20$으로 수상하게 작은 것을 쉽게 관찰할 수 있는데, 효율적으로 브루트포스를 해야함을 확인할 수 있다. 시작 점 $S$과 끝 점 $E$로 이루어진 하나의 벡터 $\mathbf{V}$가 주어지면, 이 벡터는 시작 점이 $O$이.. [Python] 32612번 Expected Eyes https://www.acmicpc.net/problem/32612 24/11/15 두 가지 방법으로 풀 수 있다. 둘다 소개해보려고 한다. 문제 접근 방식: 1. 파이썬의 itertools모듈의 product함수를 이용한다. 직접 모든 가능한 경우의 수를 조사하면서 기댓값을 구한다. 이 접근방식의 시복도는 최대 $\mathcal{O}(8^8)$이다. 따라서 파이썬3로는 통과하기 힘들고 파이파이로 하면 통과된다. 2. 기댓값의 선형성 이용 전체 기댓값은 선형성에 의해 각 주사위의 기댓값의 합과 같다. 이를 이용하면 한줄로 코딩할 수 있다.아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.더보기# 32612번 Expected Eyes# 1. 나이브한 반복 풀이.. [Python] 17371번 이사 https://www.acmicpc.net/problem/17371 24/07/05 처음 풀었을 땐 예제보고 신뢰의 제출 했는데, 증명해보려고 한다. 문제 접근 방식: 문제 제한을 보면 $N = 1000$이여서 최대 $\mathcal{O}(N^2\log N)$의 시간 복잡도로 통과할 수 있다.(해설을 읽어보니 이것이 원래 문제의도였다고 한다.) 문제의 요구 조건은 어떤 점 $P$에 대하여, $P$와 가장 가까운 편의 시설 $A$의 거리와 $P$와 가장 먼 편의 시설 $B$의 거리의 평균이 가장 최소가 되도록 점 $P$의 좌표를 구하는 것이다. 문제 예제를 잘 관찰하면 이러한 점 $P$의 좌표가 사실은 그냥 문제에서 주어진 편의 시설로 잡아도 괜찮다는 것을 알 수 있다. UCPC공식 해설에서는 이를 다.. [Python] 30959번 앙상블할래? https://www.acmicpc.net/problem/30959 24/05/14 간단한 브루트포스 문제다. 파이썬은 이러한 문제에 있어서 쉽게 구현을 할 수 있어서 좋은 것 같다. 문제 접근 방식: $N$의 제한이 $16$까지이고, 항상 홀수 개의 모델만 선택한다고 했으므로 전수조사를 해도 충분히 시간안에 들어올 수 있음을 생각할 수 있다. 하나의 조합을 통해 앙상블을 구성하는 것은 조합의 크기와 예측 항목의 개수를 곱한 크기에 비례함을 확인할 수 있다. 그 수가 그렇게 많지 않으므로, 모든 조합을 확인해보면 된다. 파이썬의 itertools 모듈의 combinations함수를 사용하면 n개 중 r개를 선택하는 모든 조합의 경우들을 확인할 수 있으므로, 이를 사용하여 쉽게 구현할 수 있다. 인덱스.. [Python] 5588번 별자리 찾기 https://www.acmicpc.net/problem/5588 5588번: 별자리 찾기 상근이는 밤하늘 사진에서 별자리를 찾고 있다. 사진에는 꼭 찾고 싶은 별자리와 같은 형태, 방향, 크기의 도형이 한 개가 포함되어 있다. 하지만, 상근이가 가지고 있는 사진 속에는 별자리를 www.acmicpc.net 24/02/01 간단한 브루트포스 문제로, 집합을 사용해 적절히 구현하면 쉽게 해결할 수 있는 문제이다. 문제 접근 방식: 별자리를 구성하는 별들은 리스트로 받고, 사진 속 별 들의 위치는 집합에 넣어주었다. 이후 사진 속의 모든 별들 마다 그 별이 옮겨진 별자리의 중심이 된다고 가정하고 이동량을 구해주었다. 옮기기 전 별자리에 있는 모든 별 마다 그 이동량을 적용해 주었다. 즉, 옮겨진 별의 좌표를.. [Python] 1038번 감소하는 수 https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 24/01/16 백트래킹 혹은 브루트 포스로 구현할 수 있는 유명한 문제이다. 비트마스킹을 이용해 구현하는 색다른 방법을 발견하여 적어보고자 한다. 기존 문제 접근 방식: 처음 문제를 접근했을 때에는 문제의 조건을 만족하는 함수 bruteforce를 작성했었다. 이 함수는 재귀적으로 호출을 하는 함수로, 호출을 받을 때마다 인자로 받은 현재 숫자를 리스트에 추가하고, 조건을 만족하도.. [Python] 14502번 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 24/01/06 BFS와 브루트포스 연습 문제로, 구현하는 중간에 조금 꼬여서 살짝 해멨던 문제이다. 문제 접근 방식: 문제 자체는 단순하다. 벽을 $3$개 세워야만 하고, 그렇게 벽을 세운 뒤에는 BFS를 돌리면 된다. 즉, $64\times 64\times 64 \approx 260,000$번 정도의 BFS를 수행하면 된다. BFS를 진행할 때에는 바이러스가 있는 부분을 큐에 넣고 BFS를 진행하면 된다... 이전 1 2 3 다음