본문 바로가기

알고리즘90

BOJ 4013 - ATM https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차로 번호와 끝 교차로 번호를 나타내는 2개의 정수가 주어진다. 그 다음 N개의 줄에는 1번 교차로부터 차례대로 각 교차로의 ATM 기기가 보유한 현금의 액수를 나타내는 정수가 각 줄에 하나씩 주어진다. 그 다음 줄에는 두 개의 정수 S와 P가 주어 www.acmicpc.net 중요한 문제라고 생각함. 유니온파인드 말고 SN, sn[MAX] 쓰면 더 쉽다. scc를 나누는데 레스토랑이 있는지, 시작점인지 등등 정보.. 2019. 8. 19.
BOJ 10265 - MT (sAdj, 위상정렬, knapsack) https://www.acmicpc.net/problem/10265 10265번: MT 문제 남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 말들을 주고받았다. 재혁: 동우가 안 가면 나도 안 간다. 동우: 세종이가 안 가면 난 안 갈래. 버스에 태울 수 있는 인원수는 한정되어 있는데 모두들 다른 누군가가 가지 않으면 자신도 가지 않겠다 하니 남규는 신경이 뻗쳤다. 게다가 술을 너무 많이 샀기 때문에 최대한 www.acmicpc.net 간선을 다음과 같이 잡아준다. u : 난 v없으면 안가 // v->u scc끼리 묶은 그래프를 보면, 한 컴포넌트씩 살펴봤을 때 ind가 .. 2019. 8. 19.
기하 - 두 선분 사이의 거리 라이님 블로그에서 공부했음을 밝힙니다 https://blog.naver.com/kks227/220794097589 https://www.acmicpc.net/problem/11563 11563번: 연돌이와 고잠녀 첫 줄에는 신촌에 연결된 도로의 숫자 n과 안암에 연결된 도로의 숫자 m(1 0) { long double s = triangle(A, B, C); h = min(h, s / distBetweenPoint(A, B) ); } if (innerProduct({ D.first - A.first, D.second - A.second }, { B.first - A.first, B.second - A.second })>0 && innerProduct({ D.first - B.first, D.second .. 2019. 8. 19.
기하1 - 외적, 두 선분의 교차 https://pinkwink.kr/159 [공업수학] 벡터의 외적 본 자료는 국립 창원대학교 메카트로닉스 공학부 학생을 대상으로 한 공업수학 수업 자료입니다. 본 자료는 수업의 교재인 공업수학I 개정3판 (고형준 외, 도서출판 텍스트북스) 의 내용을 재구성한 것으로 수업보.. pinkwink.kr 라이님의 블로그와 위 블로그에서 사진을 가져왔음을 밝힙니다. 벡터의 외적은 교환/결합법칙이 성립되지 않는다. 외적의 크기는 두 벡터가 이루는 평행사변형의 넓이이고 방향은 법선방향이다. (오른나사법칙) 외적의 결과. 맨 밑 행렬만 기억하면 된다. 코드를 짤 땐 보통 2차원 평면에서 다루기 떄문에 k성분을 0으로 두고 생각하면 되겠다. ---------------------------------- 2차원 평면에서.. 2019. 8. 19.

티스토리툴바