1. 문제 30022번: 행사 준비 (acmicpc.net) 30022번: 행사 준비 첫째 줄에 정수 $N(2\le N\le 100,000)$과 정수 $A,B(1\le A,B\leq N;A+B=N)$가 공백으로 구분되어 주어진다. 둘째 줄부터 $N$개의 줄에 정수 $p_i,q_i(1\le p_i,q_i\le 10^9)$가 공백으로 구분되어 주어진다. $p_i,q_i$는 www.acmicpc.net 2. 풀이 첫번째 상점 가격을 오름차순 정렬하고, A개만큼 산 다음, 두번째 상점 가격을 오름차순 정렬해서, 이미 산 아이템일때, 첫번째 상점 가격보다 저렴한지 비교해서 저렴하면 두번째 상점 것으로 사보고.. 아니면 첫번째, 두번째 합쳐서 정렬해서 처음부터 순회할때, A개를 맞추면 나머지는 두번째 상점에서 다 ..
1. 문제1 3216번: 다운로드 (acmicpc.net) 3216번: 다운로드 첫째 줄에, 다운로드 시작하고 몇 초 후에 노래를 듣기 시작하면, 끊김 없이 들을 수 있는지 출력한다. 그러한 시간이 여러개라면, 가장 빠른 것을 출력한다. www.acmicpc.net 2. 풀이 생각보다 어렵더라..? 다운로드 하면서 음악 재생시간을 누적해오고.. 어느 순간에 음악을 재생시키면.. 모든 다운로드 시간을 커버하면서 음악이 연속으로 흐를수 있게 할려면.. 다운로드가 언제 끝나는지 알아야하는데.. 이게 가능한가?? 리스트를 구성하면서 미리 더해서 남은 시간을 구해놓기도 하고.. 그리디의 기본인 정렬을 해서 짧은 시간부터 다운로드 해나가야하나? 생각은 했는데 정해진 순서대로 다운받아야하기 때문에.. 정렬은 할 수 ..
1. 문제1 23758번: 중앙값 제거 (acmicpc.net) 23758번: 중앙값 제거 $N$개의 자연수 $a_1$, $a_2$, $...$, $a_N$이 주어진다. 0을 좋아하는 amel은 $N$개의 수 중 0이 등장할 때까지 다음 연산을 반복하려고 한다. 중앙값을 2로 나누고 나머지는 버린다. 중앙값은 $N$개의 수 www.acmicpc.net 2. 풀이 어떤 정수를 2로 나누고 나머지를 버리는 과정을 반복할때, 언제 처음으로 0이 될 수 있을까? 1) 결국에 ? > ? > ? > ... ? > 1 > 0 이 되는 과정을 거친다. 즉 반드시 1에서만 0이 될 수 있다. 즉 "중앙값을 2로 나누고 나머지를 버리는 과정"을 계속 수행할때, 반드시 중앙값이 1이 되어야하고, 여기서 1번 더 수행하면 0..
1. 모노톤 체인(monotone chain) 볼록 껍질(convex hull)을 구하는 두번째 알고리즘 graham scan과는 다르게 점을 정렬하는 방법이 다르고, 아래쪽 껍질과 위쪽 껍질을 구하여 둘을 합치는 방식으로 구한다 구체적으로는... 1) 주어진 점을 x좌표 순으로 오름차순 정렬하고 x좌표가 같으면 y좌표를 기준으로 오름차순 정렬 2) 첫번째 점과 두번째 점을 스택에 넣는다. 3) 이제 순서대로 세번째 점부터 순회하면서 조건에 맞으면 스택에 차례대로 집어 넣는다. 3-1) 스택의 -2번, -1번 점과 새로 추가하려는 점이 CW를 이루면 스택에 집어 넣는다. 3-2) CW를 이루지 않는다면 CW가 될 때까지 스택의 마지막 점을 pop한다 4) 마지막에 스택에 남아있는 점들이 볼록 껍질의 윗 ..
1. 모든 점까지 맨해튼 거리의 합이 최소가 되는 점의 위치? m차원의 n개의 점들 $P_{1}(x_{11},x_{12},...,x_{1m}), ... P_{n}(x_{n1},x_{n2},...,x_{nm})$에 대하여, 이들까지 맨해튼 거리의 합이 최소가 되는 점 X의 좌표를 구하라고 한다면, 어떻게 구할 수 있을까? 정답은 n개의 점들을 1,2,...,m차원의 좌표 값에 대하여 정렬한 다음, 중앙값에 해당하는 점의 좌표 $P_{median}$이 된다. 직관적으로 쉽게 눈치챌 수 있기는 한데, 왜 그런지 생각해보자. 2. 증명 먼저 점들의 좌표가 합에 서로 영향을 주지 않는다는 점을 관찰하자. 예를 들어 (3,5), (4,2), (5,1)에 대하여 (x,y)까지 맨해튼 거리의 합은.. $|x-3| + ..
1. 문제 21203번: Distance (acmicpc.net) 21203번: Distance The City of Manhattan is organized as a grid of streets and avenues, with streets running in the North-South direction and avenues running in the East-West direction. Streets are numbered from East to West starting from 1, and avenues are numbered from N www.acmicpc.net 2. 풀이 n 제한이 20만이라 모든 좌표쌍 일일이 정해서 거리를 구해보는 방법으로는 어림도 없다 https://www.geeksf..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
