본문 바로가기

알고리즘225

냅색, knapsack https://www.acmicpc.net/problem/10265 10265번: MT 문제 남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 말들을 주고받았다. 재혁: 동우가 안 가면 나도 안 간다. 동우: 세종이가 안 가면 난 안 갈래. 버스에 태울 수 있는 인원수는 한정되어 있는데 모두들 다른 누군가가 가지 않으면 자신도 가지 않겠다 하니 남규는 신경이 뻗쳤다. 게다가 술을 너무 많이 샀기 때문에 최대한 www.acmicpc.net 이 문제의 기본 아이디어 작은 상자 n개에 사탕이 최소 mn개 최대 mx개 들어있을 때, 용량이 K인 큰 바구니에 최대 몇개의 사탕을 넣을.. 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.
BOJ 12015 - 가장 긴 증가하는 부분수열2 (segtree) 라이님 블로그에서 공부했음을 밝힘니다. 구간 최대값을 저장하는 세그먼트트리를 마련해 두자. 값을 입력받을 땐, {원소값, 인덱스} pair로 p배열을 만들고, 원소값 순 인덱스 역순으로 정렬해 준다. p배열을 순서대로 방문하면서 세그트리를 업데이트 해준다. 마지막에 루트에 남은 값이 LIS길이가 된다. #include #include #include using namespace std; int arr[1 > a; p[i] = { a,i }; } sort(p, p + n, [](pair p, pair q) { if (p.first != q.first) return p.first q.second; }); for (int i = 0; i < n; i++) {.. 2019. 8. 19.

티스토리툴바