최소 신장 트리, C++ 최소 신장 트리, MST(Minimum Spanning Tree) 알고리즘은 두 가지 방식으로 풀 수 있다. 크루스칼 알고리즘과 프림 알고리즘이다. 크루스칼 알고리즘은 간선을 가중치가 작은 순서대로 오름차순으로 정렬을하고, 사이클을 형성하지 않는 방향으로 간선을 선택하며 트리를 구성한다. 정점이 많을 때 효과적인 알고리즘이다. 프림 알고리즘은 아무 정점을 시작 정점으로 설정한 뒤, 시작 정점의 인접 정점들 중에 가장 가중치가 작은 간선을 선택하며 정점을 잇는다. 하나의 정점을 잇게 되면, 현재까지 방문한 정점들의 인접 정점중에서 방문하지 않으면서 가장 작은 가중치를 가진 간선을 선택하는 알고리즘이다. 이렇게 되면 문제는 정점이 많아지게 된다면, 이전 방문했던 모든 정점들의 인접 ..
전체 글
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개..