본문 바로가기

분류 전체보기178

23752 - 카드 잘 섞기 step 1더보기2번 쿼리는 그냥 하면 됩니다.1번 쿼리에서 카드 장수가 홀수인 경우만 생각해 봅시다. 카드 5장이 다음과 같이 있습니다. 카드의 위치는 위에서 부터, 0-base로 셉니다.카드의 인덱스를 2배 한 다음 절반씩 나누고 잘 끼워 넣습니다.그럼 카드의 장수를 $N$이라 할 때 각 카드의 처음 인덱스를 $a_i$라 할 때 셔플 후의 인덱스는 $(a_i*2)\%N$이 됩니다. 이 동작을 $z$번 반복하면 $a_i*2^z\%N$이 됩니다.step 2더보기카드의 장수가 짝수인 경우입니다. 제일 아래쪽 카드의 위치는 절대 바뀌지 않습니다.마지막 카드만 빼고 살펴봅시다. 5장일 때와 다르지 않습니다.즉 $1\,x\,y\,z((y-x)\%2==1)$ 쿼리는 $1\,x\,y-1\,z$과 완벽히 같습니다.코.. 2024. 6. 20.
27086 - 점수 내기 step 1더보기수학토끼가 내야 하는 금액은 $O(N)$에 구할 수 있으니 신경쓰지 맙시다.$y=1$로 계산하고 마지막에 진짜 y를 곱해줍니다.$(x, \lceil 2*10^5 / x \rceil)$ 크기의 배열을 생각해 봅시다. 점수가 $X_i$인 학생은 $(X_i\%x, \lfloor X_i/x\rfloor)$ 칸에 들어가 있습니다. 아래는 각 점수별로 어떤 칸에 들어가는지 표시해 두었습니다. 각 열마다 해당 열에 있는 사람들의 몫의 합과 그 열에 있는 사람의 수를 저장해 둡니다. 아래 그림에서 칸에 있는 숫자는 해당 칸에 해당하는 사람의 수입니다.step 2더보기점수가 가장 낮은 사람을 봅시다. 이 사람은 모든 사람(같은 칸에 있는 사람 제외)과 비교를 해야 합니다. 어떤 칸에 사람이 있는지에 따라.. 2024. 6. 20.
15807 - *빛*영*우* step 1더보기 https://www.acmicpc.net/problem/5419 step 2더보기그림을 반시계 방향으로 45도 돌린다고 생각해 봅시다. 그럼 위 문제를 푸는 것과 같습니다.새로운 좌표축 2개를 도입합니다. 하나는 $y=x$고 다른 하나는 $y=-x$입니다. 새로운 좌표 축에 맞춰 좌표를 재설정하고 위 문제를 해결합니다.축을 바꾸는 것을 해봅시다. 위 그림에서 점 $A$는 원래 축 기준 (1,3)에 있습니다. 그리고 새로운 축(빨간색) 기준으로는 (-2, 4)에 있습니다. 원래 축 기준 $x$좌표를 $X$, 원래 축 기준 $y$좌표를 $Y$라고 하면바뀐 축 기준 $x$좌표 : $X-Y$바뀐 축 기준 $y$좌표 : $X+Y$로 쉽게 계산할 수 있습니다. step 3더보기이제부터 모든 좌표.. 2024. 6. 19.
opencv - 프로젝트 2 - 2. 카드 인식 이전 프로젝트(https://codestudycafe.tistory.com/47)에서 라벨링을 하는 툴을 만들었습니다. 먼저 이 툴을 이용해 라벨링을 해 줍니다.우선 이정도로만 만들고 머신러닝을 학습해 보겠습니다. 먼저 GPU를 사용할 수 있게 세팅을 해줍니다. 몇가지 필요한 설정을들 import한 다음 이미지 파일을 받아옵니다. 저는 data에 원본 이미지, filter에 라벨링한 이미지를 넣었습니다.  이미지를 다 가져오고 크기를 확인해 봅니다. 보니까 몇가지 문제가 있는 것 같네요. 우선 이미지가 너무 큽니다. U-net 논문에서는 572*572 이미지를 사용했는데 그것보다 4배 정도 큰 것 같네요. 그리고 label의 shape가 (8, 1356, 1018, 4)입니다. 마지막 차원이 1이길 바랬.. 2024. 6. 19.
9642 - Omar’s Bug 문제 번역더보기Omar는 다음 이분탐색 코드를 만들었습니다.int findFirstGreaterThanOrEqual(int array[], int N, int X) { int start = 0, end = N; while (start X) { end = middle; } else { start = middle + 1; } } return start;} 파라미터는 다음 조건을 만족합니다.$array$는 1개 이상 99개 이하의 수가 들어있습니다.$array$의 모든 숫자는 서로 다르고 오름차순입니다.$array$에 있는 수는 최대 100입니다.$N$은 $array$의 크기입니다.$X$는 최대 100입니다.만약 $X$보다.. 2024. 6. 13.
17242 - Kaka & Bebe step 1더보기$dp[i][j]$ = i번째 정점에 있고 지금까지 Kaka를 j마리를 봤을 때 그때까지 볼 수 있는 Bebe의 최소 마리 수를 구합니다.step 2더보기위 dp를 구해봅시다. 모든 간선마다 Kaka와 Bebe가 한 마리씩은 있기 때문에 $dp[i][j]$는 $dp[k][l](l>j)$에만 영향을 미칠 수 있습니다. 즉, $j$가 작은 $dp$부터 출발해서 순서대로 채워주면 됩니다.코드더보기#define _CRT_SECURE_NO_WARNINGS#include#include#includeusing namespace std;vector>> v[2000];priority_queue> q;int dp[2000][2000],ch[2000][2000];int main() { int n, m,.. 2024. 6. 13.

티스토리툴바