www.acmicpc.net/problem/1708 볼록 껍질 문제는 Convex Hull 문제라고 보면 된다. Convex Hull 문제를 푸는 방식은 두 가지가 있다고 한다. 하나는 Graham Scan 방식과 Jarvis March 방식이다. Jarvis March 방식은 나도 아직 잘 모르겠고, Graham Scan 방식으로 문제를 풀었다. 알고리즘 설명은 이렇다. 1. 좌표값들이 주어진다. 2. 모든 좌표 중에서 극좌표를 결정한다. 3. 극좌표 결정은 y 좌표값이 가장 작고, 만약 y값이 같다면 x값이 작은 좌표를 찾아 극좌표로 결정하면 된다. 4. 극좌표를 기준으로 모든 좌표들을 반시계방향으로 좌표를 정렬한다. 5. 이 때, 정렬하는 방식은 ccw 방식을 사용하면 된다. 6. ccw > 0 이..
전체 글
점 P1, P2, P3가 주어질 때, 점 P1을 기준으로 세 점이 반시계 방향인지, 직선인지, 시계 방향인지 방향성을 판단하는 문제이다. #define _CRT_SECURE_NO_WARNINGS #include int ccw(int x1, int y1, int x2, int y2, int x3, int y3) { int res; res = 1 * (x1 * y2 - y1 * x2) + 1 * (x2 * y3 - y2 * x3) + 1 * (x3 * y1 - x1 * y3); if (res > 0) return 1; else if (res == 0) return 0; else return -1; } int main() { int x1, y1, x2, y2, x3, y3; scanf("%d %d %d %d ..
삼성 역량 기출문제 테트로미노 문제이다. 생각보다 쉬워서 놀랐고, 삼성 기출문제나 다른 코테 문제 수준이 딱 이 정도만 나오면 좋을 것 같단 생각이 들었다.. 일단, tetromino라는 블록에 대한 배열을 다 만들었다. 5개의 블록을 회전 및 대칭을 시켰을 때 생성될 수 있는 경우는 총 19개가 된다. 그렇게 많지 않기 때문에 배열을 사용해서 19개의 모양을 나타내는 배열을 다 생성했다. 그리고 보드의 너비는 최대 500 x 500이지만, 만약 테트로미노가 겹쳐진다고 생각했을 때, 503까지 늘어날 수 있기 때문에 503 x 503의 사이즈로 생성해주었다. 그 다음으로는 너무 쉬웠다. 주어진 입력을 받아서 BOARD를 초기화하고, 좌상단에서 우하단까지 모든 좌표를 방문하면서 그 좌표 위에 올라갈 19개..
요즘 DFS, BFS 문제를 풀고 있는데, 한 번 감이 잡히니까 문제가 계속 잘 풀려서 감사한 마음이 든다. BFS 문제를 풀 때는 Queue를 사용해서 문제를 풀 수 있는데, 내가 초반에 많이 실수 했던 부분은 노드의 방문 기록을 남기는 작업을 하지 않았었다. 이제는 습관을 잡아, 무조건 DFS든 BFS든 visited 배열을 항상 만들고 시작한다. 아래 문제는 전형적인 BFS 문제인데, 이 문제에서 핵심은 수빈이가 동생을 찾기 위한 방법이 3가지라는 것이다. 방법 1. 현재 위치 - 1 방법 2. 현재 위치 + 1 방법 3. 현재 위치 x 2 나 같은 경우는 보통 DFS, BFS 문제를 풀 때, 구조체를 활용해서 움직이는 객체를 생성한다. queue를 생성하고, 초기 위치를 push 해준다. 이 후 ..