Toolofv 님의 블로그

문제N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다.사람은 1번부터 N번까지 번호가 매겨져 있으며, 일도 1번부터 N번까지 번호가 매겨져 있다.Dij를 i번 사람이 j번 일을 할 때 필요한 비용이라고 했을 때, 모든 일을 하는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력첫째 줄에 사람과 일의 수 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 D의 내용이 주어진다. 비용은 10,000보다 작거나 같은 자연수이다.출력모든 일을 하는데 필요한 비용의 최솟값을 출력한다.  문제해결방법 - (서칭 참조) 1. 비트마스크를 이용한 dfs탐색으로 재귀함수 끝부분부터 ..

문제 두 원이 주어졌을 때, 교차하는 영역의 넓이를 소수점 셋째자리까지 구하는 프로그램을 작성하시오.입력첫째 줄에 두 원의 중심과 반지름 x1, y1, r1, x2, y2, r2가 주어진다. 실수는 최대 소수점 둘째자리까지 주어진다.출력첫째 줄에 교차하는 영역의 넓이를 반올림해 소수점 셋째자리까지 출력한다.  문제해결방법 - (서치 참조) 1. 겹치는 부분이 없을 때 : 02. 한 원이 다른 원 안에 포함될 때 : 작은 원의 넓이3. 겹치는 부분을 계산해야 할 때 :(큰 원 부채꼴 넓이 - 큰원의 내접한 삼각형 넓이) + (작은 원 부채꼴 넓이 - 작은 원의 내접한 삼각형의 넓이) 4-1. theta1, 2는 코사인 법칙을 역함수로 하는 파이썬 math.acos()로 구할 수 있다.      4-2. 파..

문제해결방법 -  1. 사선공식(신발끈 공식)을 이용하면 주어진 3점의 좌표 방향에 따라 1, 0, -1을 출력한다는 것을 알 수 있다. 1) (x1, y1) (x2, y2) 직선에서 각 점 (x3, y3) 과 (x4, y4)을 사선공식으로 돌린다. 결과를 곱했을 때, 0, -1의 경우만 교점이 있을 가능성이 있다.2) (x3, y3), (x4, y4) 직선에서도 각 점 (x1, y1) 과 (x2, y2)을 사선공식으로 돌린다. 위와 같다. 2. 위 결과가 둘 다 0, -1인 경우만 본다. 예외적으로 기울기가 같을 때, 만나지 않는 경우가 있을 수 있으므로, 범위를 체크한다.  1) 두 직선의 기울기가 같을 때, 접점이 하나면 p1, p2 중 공통되는 부분이 접점이 된다.2) 두 직선의 기울기가 같을 때..

문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.입력입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각..

문제해결방법 - (구글링, 챗GPT 참조) 1. 신발끈 공식이라 일컬어지는 사선공식을 활용한다. 이 사선공식은 좌표로 주어지는 삼각형의 넓이를 구하는 공식인데, 절댓값을 취하기 전, 계산한 결과가 음수냐 양수냐에 따라 p1(x1, y1), p2(x2, y2), p3(x3, y3)의 순서로 선을 긋는다고 할 때 시계방향인지, 반시계방향인지 알 수 있다. (음수면 시계방향, 양수면 반시계방향) 이 문제에서 방향을 체크하는 것으로 연동되어 알 수 있는 것은 삼각형이 p2(x2, y2)에 따라 볼록하냐, 오목하냐를 알 수 있다는 것이다.   위 그림을 보면 쉽게 알 수 있다. 이제 팔각형을 x-y축의 직각 좌표계로 바꾸어서 각각의 요소마다 삼각형을 판단할 수 있어야 한다. 정중앙을 (0, 0)이라고 할 때, p..

문제 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 각 길은 방향성이 없어서 A번 마을에서 B번 마을로 갈 수 있다면 B번 마을에서 A번 마을로 갈 수 있다. 또, 모든 마을은 연결되어 있다. 두 마을 사이에 직접 잇는 길이 있을 때, 두 마을이 인접해 있다고 한다.이 나라의 주민들에게 성취감을 높여 주기 위해, 다음 세 가지 조건을 만족하면서 N개의 마을 중 몇 개의 마을을 '우수 마을'로 선정하려고 한다.'우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을..

문제그래프 G(V, E)에서 정점의 부분 집합 S에 속한 모든 정점쌍이 서로 인접하지 않으면 (정점쌍을 잇는 간선이 없으면) S를 독립 집합(independent set)이라고 한다. 독립 집합의 크기는 정점에 가중치가 주어져 있지 않을 경우는 독립 집합에 속한 정점의 수를 말하고, 정점에 가중치가 주어져 있으면 독립 집합에 속한 정점의 가중치의 합으로 정의한다. 독립 집합이 공집합일 때 그 크기는 0이라고 하자. 크기가 최대인 독립 집합을 최대 독립 집합이라고 한다.문제는 일반적인 그래프가 아니라 트리(연결되어 있고 사이클이 없는 그래프)와 각 정점의 가중치가 양의 정수로 주어져 있을 때, 최대 독립 집합을 구하는 것이다. 입력첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정..

컴퓨터는 0과 1, 이진법을 이용하여 입력 - 저장 - 제어 - 연산 - 출력의 싸이클을 핵심으로 동작하는 장치이다. 현대에는 위 절차가 복합적으로 이루어져 있으며, 입력기기(키보드, 마우스, 마이크, 터치스크린 등)와 출력기기(모니터, 프린터 등), CPU와 저장장치(트랜지스터와 논리회로)의 작동 원리는 개별적으로 올려보고자 한다. 어떻게 해서 컴퓨터가 동작하는지 논리부분을 중점으로 대략적으로 큼지막하게 알아보도록 하자.논리 부분에서 동작이 가능하다면, 현대의 PC처럼 꼭 전기망, 전자회로을 이용해 구성하지 않을 수도 있다는 말이 된다.수력을 이용한 컴퓨터도 만들 수 있을 것이다.(중력을 기반으로 한 수로를 이용하는 방법. 물론 효용성은 없을 것이다.) 1. 트랜지스터트랜지스터를 이용한 회로에 전류가 ..

문제흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 ..