본문 바로가기

전체 글343

백준 17387 c++ -선분 교차2 [PlusUltraCode] [필자 생각 ] 문제를 보고 CCW 알고리즘을 이용해야 된다는 생각이 들었다. CCW알고리즘 공식은 알고 있었지만 어떻게 이용해서 선분이 교차되는지 판단하는데는 문제가 있었다. 고등학교 때 배운 선분 교차 방법을 생각해 봤지만 코드로 짜기에는 무척 복잡해졌다. 몇몇 자료를 찾아보니 다음과 같은 해결책을 찾았다. [해결] 1. 두 선분이 방향과는 상관없이 일단 겹쳐져 있나? 2. 두 선분이 겹쳐진거 상관없이 CCW를 이용하여 일직선이냐 아니냐? 이 두가지 함수를 구하면 된다. [소스코드] #include #include #include using namespace std; int CCW(long x1, long y1, long x2, long y2, long x3, long y3) { //x1 x2 x3 .. 2024. 2. 16.
백준 11758 c++ -PlusUltraCode CCW알고리즘을 알고 있으면 쉽게 풀수 있는 문제이다. /* x1 x2 x3 x1*/ /* y1 y2 y3 y1*/ CCW알고리즘은 이런식으로 대각선끼리 곱해주고 빼주면 된다. [소스코드] #include #include #include #include #include #include using namespace std; int main(void) { int x1, x2, x3, y1, y2, y3; /* x1 x2 x3 x1*/ /* y1 y2 y3 y1*/ cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3; int CCW = ( (x1 * y2) + (x2 * y3) + (x3 * y1) ) - ((x2* y1) + (x3 * y2) + (x1 * y3)); if (CCW > 0.. 2024. 2. 15.
기하 개념정리 CCW 는 평면상에서 3개의 점의 위치관계를 알려주는 알고리즘이다. A(x1,y1), B(x2,y2), C(x3,y3) 이 주어질 경우 | x1 x2 x3 x1 | | y1 y2 y3 y1 | 이렇게 만들고 대각선끼리 곱해준다 고등학교 때 배운 신발끈이론 혹은 벡터의 외적개념이다. {(x1*y2) + (x2*y3) + (x3*y1)} - {(x2*y1)+(x3*y2) +(x1*y3)} = CCW CCW가 음수인 경우 A에서 부터 C까지 가는데 시계방향으로 간다는걸 알 수 있따. CCW가 양수인 경우 A에서 부터 C까지 가는데 반시계방향으로 간다는걸 알 수 있다. CCW가 0인경우 일직선인걸 알 수 있다. 2024. 2. 15.
백준 1328 c++ -고층 빌딩 [필자 생각] 1차원과 2차원 배열로만 동적프로그래밍을 생각해왔다. 아무리 생각해도 해답이 나오지 않아 자료들을 찾게 되었다. [깨달음] 이 문제는 처음으로 내게 3차원 동적프로그래밍의 사고를 열어준 문제였다. [문제 풀이] D[N][L][R] 의 배열을 만들어 준다. N의 갯수가 증가함에 따라 가장 작은 빌딩을 어디에 놓는지가 핵심인 문제이다. 1. 가장 작은 빌딩을 맨 왼쪽에 넣는다. => D[N-1][L-1][R] 2. 가장 작은 빌딩을 맨 오른쪽에 넣는다 => D[N-1][L][R-1] 3. 가장 작은 빌딩을 중간에 넣는다ㅏ. => D[N-1][L][R]*(N-2) 3번에서 N-2번 곱한 이유는 왼쪽과 오른쪽을 제외하면 나머지 넣을 수 있는 경우의 수가 N-2번이기 때문에 곱해줘야 된다. [소스코.. 2024. 2. 15.

티스토리툴바