본문 바로가기

백준146

백준 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.
백준 1915 c++ - 가장 큰 정사각형 [필자 처음 생각 ] 처음 문제를 읽고 DFS, BFS 문제라 생각했지만 모든 정사각형인지 판단하려면 코드를 짜는것도 쉽지 않고 무엇보다 시간복잡도 측면에서 어긋나게 된다는걸 알았다. 다음으로 분할로 사고를 바꿨지만 사각형이 어디에 존재하는지 정확히 알 수 없는 상황에서는 균등하게 분할로 풀 수 없었다. [해결과정] 조금의 사고 과정후 DP문제라는걸 알게 되었다 [KEY POINT] 만약 배열 값이 1이면 사각형 오른쪽 아래 꼭짓점이라 가정을한다. 그 점 기준으로 왼쪽, 위쪽, 왼쪽위의 값중 가장 작은값을 구하고 +1을 해주면 동적프로그래밍 완성이다. #include #include #include #include using namespace std; int Arr[1001][1001]; int N, M.. 2024. 2. 13.

티스토리툴바