본문 바로가기

알고리즘/메모44

기하1 - 외적, 두 선분의 교차 https://pinkwink.kr/159 [공업수학] 벡터의 외적 본 자료는 국립 창원대학교 메카트로닉스 공학부 학생을 대상으로 한 공업수학 수업 자료입니다. 본 자료는 수업의 교재인 공업수학I 개정3판 (고형준 외, 도서출판 텍스트북스) 의 내용을 재구성한 것으로 수업보.. pinkwink.kr 라이님의 블로그와 위 블로그에서 사진을 가져왔음을 밝힙니다. 벡터의 외적은 교환/결합법칙이 성립되지 않는다. 외적의 크기는 두 벡터가 이루는 평행사변형의 넓이이고 방향은 법선방향이다. (오른나사법칙) 외적의 결과. 맨 밑 행렬만 기억하면 된다. 코드를 짤 땐 보통 2차원 평면에서 다루기 떄문에 k성분을 0으로 두고 생각하면 되겠다. ---------------------------------- 2차원 평면에서.. 2019. 8. 19.
2-SAT(Boolean Satisfiability) F = (a||b) && (c||d) && (e||f).... (||대신 xor등으로 변형가능함) 다음과 같이 F가 주어질 때, 1. F가 참이나 거짓이 되도록 할 수 있는지 여부 2. F가 참/거짓일 떄 a,b,c,d,e,f,..의 값은 무엇인지 를 묻는 문제들이 대표적이다. 배경지식: 0. p->q == notp or q . p가 false라면 p->q는 항상 참이다. 1. p || q == notp -> q && notq->p (두 항이 대우관계로 같은 말이다. 방향이 반대인 그래프를 하나 더 그려주기 위함인 것으로 이해함.) 2. p xor q == (notp -> q && notq->p) && (p->notq && q->notp) (묶인 것 끼리 대우관계이다. 위와 같은 이유라고 이해함.) 3... 2019. 8. 19.
강한 연결 요소(SCC) 그래프에셔 u->v와 v->u 경로(간선아님)가 모두 있으면 같은 SCC에 속한다고 한다. dfs하면서 stack을 이용해서 분리해 낸다. 선형시간 O(n) 필요한 것: int id = 0, dfsn[MAX]={0}; //방문하는 정점마다 고유번호를 저장하기 위함. dfsn은 visit의 역할도 수행한다. bool finished[MAX] = {false}; //scc추출이 완료된 정점인지 vector adj[MAX] stack s 선택1) vector SCC; 선택2) int SN=0, sn[MAX]; //해당 정점이 포함된 scc번호를 저장함 int id, dfsn[MAX]; bool finished[MAX]; vector adj[MAX]; vector SCC; stack s; int makeSCC(.. 2019. 8. 19.
위상정렬, DAG(Directed Acyclic Graph) 그래프의 분류 중 하나로 DAG,사이클이 없는 방향그래프가 있다. DAG에서는 항상 위상정렬이 가능하고 그 후에 동적 계획법을 적용하는 것이 가능하다. ㅁ 정점u에서 정점v로 가는 최단/최장 경로는 무엇인가? ㅁ 경로 중 간선의 개수가 가장 적은/많은 경우 간선은 몇 개인가? ㅁ 모든 경로에 포함된 정점은 어떤 것이 있는가? ㅁ 서로 다른 경로의 개수는 몇 개인가? 등등.. 위상정렬된 순서대로 처리하면 구할 수 있다. 또한 모든 동적 계획법 문제는 DAG로 나타낼 수 있다. 이 때 정점은 dp상의 상태에, 간선은 상태간의 관계에 대응된다. ex)동전문제, 냅색.. 사이클이 없는 그래프에서 정점의 탐색이 끝난 순서 (fin[u]=true)의 반대 순서로 처리하면 위상정렬 순서 (예)https://suunt.. 2019. 8. 18.

티스토리툴바