본문 바로가기

분류 전체보기

 (152)
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$과 완벽히 같습니다.코..
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더보기점수가 가장 낮은 사람을 봅시다. 이 사람은 모든 사람(같은 칸에 있는 사람 제외)과 비교를 해야 합니다. 어떤 칸에 사람이 있는지에 따라..
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더보기이제부터 모든 좌표..
opencv - 프로젝트 2 - 2. 카드 인식 이전 프로젝트(https://codestudycafe.tistory.com/47)에서 라벨링을 하는 툴을 만들었습니다. 먼저 이 툴을 이용해 라벨링을 해 줍니다.우선 이정도로만 만들고 머신러닝을 학습해 보겠습니다. 먼저 GPU를 사용할 수 있게 세팅을 해줍니다. 몇가지 필요한 설정을들 import한 다음 이미지 파일을 받아옵니다. 저는 data에 원본 이미지, filter에 라벨링한 이미지를 넣었습니다.  이미지를 다 가져오고 크기를 확인해 봅니다. 보니까 몇가지 문제가 있는 것 같네요. 우선 이미지가 너무 큽니다. U-net 논문에서는 572*572 이미지를 사용했는데 그것보다 4배 정도 큰 것 같네요. 그리고 label의 shape가 (8, 1356, 1018, 4)입니다. 마지막 차원이 1이길 바랬..
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$보다..
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,..
17398 - 통신망 분할 step 1더보기원래 상태에서 연결을 끊는다고 생각하지 말고 이미 연결을 다 끊어놓은 상태에서 거꾸로 연결을 한다고 생각합니다.step 2더보기$Q$번의 연결을 다 끊어놓은 상태를 구할 수 있습니다. 유니온 파인드를 이용해서 어떤 정점들이 이어져 있는지 확인합니다. 그 상태에서 쿼리를 반대로 봅니다. 두 정점이 같은 집합에 있다면 해당 쿼리를 실행했을 때 통신망이 나뉘어지지 않았다는 뜻입니다. 두 정점이 다른 집합에 있다면 각 집합의 크기를 곱한 값만큼 비용이 발생했다는 뜻입니다.코드더보기#define _CRT_SECURE_NO_WARNINGS#includestruct data { long long int x, y;}b[200000];long long int tr[200000];long long i..
opencv - 프로젝트 2 - 1. 카드 인식 저는 취미로 마술을 하고 있습니다. 같이 마술하는 친구들이랑 모여서 이야기를 하는데 이런 이야기가 나오더라고요관객이 7하트를 들고 있는 모습을 찍었는데 나중에 사진 속 카드를 확인해 보니 7 스페이드로 바뀌어 있으면 신기하지 않을까? 딥러닝에서 U-net(https://codestudycafe.tistory.com/41)을 이용하면 충분히 만들 수 있겠다는 생각이 들었고 바로 작업에 들어갔습니다. 우선 카드를 인식하는 것부터 시작해 보겠습니다. 윤곽선 추출1. 흑백 샤프닝카드를 먼저 라벨링을 해줘야 학습을 시킬 수 있습니다. 이 부분을 opencv로 처리하겠습니다. 먼저 흑백으로 사진을 입력받고 윤곽선을 추출해 줍니다. 그리고 마우스로 영역을 클릭하면 해당 위치와 색이 비슷한 영역을 bfs로 탐색하면서 ..
13209 - 검역소 step 1더보기더보기검역소를 설치하는 것은 트리에서 간선을 끊는 것으로 생각할 수 있습니다. 즉 $K$개의 간선을 끊었을 때 각 트리에 있는 사람들 수의 합의 최대값을 최소로 하는 문제입니다. 문제를 살짝 바꿔서 "각 트리에 최대 $X$명의 사람이 있을 수 있다고 하면 적어도 몇 개의 다리를 끊어야 하는가"로 생각해 봅시다. $X$가 커질수록 끊어야 하는 다리의 수는 적어집니다. 따라서 이분 탐색으로 $X$값을 찾을 수 있습니다.step 2더보기더보기bridge[i] = i번째 정점을 루트로 생각했을 때 끊어야 하는 다리의 최소값person[i] = bridge[i]를 최소로 만들었을 때 i번째 정점이 속한 트리에 있는 사람 수. 이 두 dp를 채운다고 생각합니다. 어떤 정점이 시작점이여도 답은 바뀌지..
opencv - 프로젝트 1 - 1. 얼굴 모자이크 딥러닝 프로젝트를 하다 보면 사람 이미지를 보여주는 경우가 있습니다. 하지만 사람 얼굴을 그대로 보여주면 초상화같은 다양한 문제가 있을 수 있으니 얼굴을 자동으로 모자이크를 하는 프로그램을 먼저 만드려고 합니다. 얼굴을 인식하는 데에 다양한 방법( haarcascade, DNN 얼굴 검출)이 있습니다. 저는 mediapipe를 이용하기로 했습니다. python(https://codestudycafe.tistory.com/26)과 vscode(https://codestudycafe.tistory.com/16)를 설치하고 pip install mediapipe를 실행합니다.  mp.solutions.face_detection.FaceDetection으로 얼굴 인식 모델을 가져옵니다. mpDraw는 얼굴 인식..

티스토리툴바