본문 바로가기

분류 전체보기178

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.. 2024. 6. 13.
opencv - 프로젝트 2 - 1. 카드 인식 저는 취미로 마술을 하고 있습니다. 같이 마술하는 친구들이랑 모여서 이야기를 하는데 이런 이야기가 나오더라고요관객이 7하트를 들고 있는 모습을 찍었는데 나중에 사진 속 카드를 확인해 보니 7 스페이드로 바뀌어 있으면 신기하지 않을까? 딥러닝에서 U-net(https://codestudycafe.tistory.com/41)을 이용하면 충분히 만들 수 있겠다는 생각이 들었고 바로 작업에 들어갔습니다. 우선 카드를 인식하는 것부터 시작해 보겠습니다. 윤곽선 추출1. 흑백 샤프닝카드를 먼저 라벨링을 해줘야 학습을 시킬 수 있습니다. 이 부분을 opencv로 처리하겠습니다. 먼저 흑백으로 사진을 입력받고 윤곽선을 추출해 줍니다. 그리고 마우스로 영역을 클릭하면 해당 위치와 색이 비슷한 영역을 bfs로 탐색하면서 .. 2024. 6. 8.
13209 - 검역소 step 1더보기더보기검역소를 설치하는 것은 트리에서 간선을 끊는 것으로 생각할 수 있습니다. 즉 $K$개의 간선을 끊었을 때 각 트리에 있는 사람들 수의 합의 최대값을 최소로 하는 문제입니다. 문제를 살짝 바꿔서 "각 트리에 최대 $X$명의 사람이 있을 수 있다고 하면 적어도 몇 개의 다리를 끊어야 하는가"로 생각해 봅시다. $X$가 커질수록 끊어야 하는 다리의 수는 적어집니다. 따라서 이분 탐색으로 $X$값을 찾을 수 있습니다.step 2더보기더보기bridge[i] = i번째 정점을 루트로 생각했을 때 끊어야 하는 다리의 최소값person[i] = bridge[i]를 최소로 만들었을 때 i번째 정점이 속한 트리에 있는 사람 수. 이 두 dp를 채운다고 생각합니다. 어떤 정점이 시작점이여도 답은 바뀌지.. 2024. 6. 2.
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는 얼굴 인식.. 2024. 6. 2.
opencv 시작 딥러닝 이미지를 전처리하거나 이미지와 관련된 일을 할 때 opencv를 많이 사용합니다. opencv를 사용하는 방법을 간단히 적어보겠습니다. window 기반으로 작성되었습니다.준비python(https://codestudycafe.tistory.com/26)과 vscode(https://codestudycafe.tistory.com/16)를 설치합니다. 그리고 프로젝트 파일 하나를 만들어서 vscode를 실행해 줍니다. 이제 터미널에 pip install opencv-python를 입력해서 opencv를 설치합니다. 파이썬 파일을 만들어 다음과 같이 입력합니다. 4.9.0처럼 숫자가 나오면 잘 설치가 된 것입니다. 이 숫자는 버전에 따라 달라질 수 있습니다. 실행사실 준비는 이걸로 끝입니다. 간단판 .. 2024. 6. 1.
3043 - 장난감 탱크 step 1더보기더보기행과 열을 분리해서 볼 수 있습니다.step 2더보기더보기$N$ * $N$ 크기에 $N$개의 탱크를 놓습니다. 어떤 행이나 열에도 2개 이상의 탱크가 놓일 수 없으니 결국 모든 행에 1대, 모든 열에 1대의 탱크가 놓입니다.열을 먼저 생각해 봅시다. 처음에 탱크가 배치되어 있고 이 탱크들을 모든 열에 1대씩 있도록 재배치해야 합니다.처음 배치에서 두 탱크를 고른다고 생각해 봅시다. 왼쪽에 있는 탱크를 $X$, 오른쪽에 있는 탱크를 $Y$라고 합시다. 이 두 탱크는 재배치된 이후에도 $X$가 $Y$ 왼쪽에 있어야 합니다. 이것을 잘 생각해 보면 열을 기준으로 정렬한 뒤 제일 왼쪽에 있는 탱크는 1번째 열, 두번째로 왼쪽에 있는 탱크는 2번째 열, ..., $N$번째로 왼쪽에 있는 탱크.. 2024. 5. 31.

티스토리툴바