방금 프로그래머스에서 풀어본 방식인 크루스칼 알고리즘으로 풀어보았다. 여기서 좀 헷갈렸고, 놓쳤던 부분은 parent를 설정할 때 정점이 1부터 시작한다는 것으로 생각해야하고, 그래서 V + 1 사이즈로 초기화해야한다. // MST(Minimum Spanning Tree) // 최소 신장 트리는 두 종류 알고리즘으로 풀 수 있다. // 크루스칼 알고리즘 VS 프림 알고리즘 // 크루스칼 알고리즘은 간선을 선택하며 찾는 알고리즘 // 프림 알고리즘은 정점을 선택하며 찾는 알고리즘이다. #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; long long V, E; long long getRoot(vector& par..
알고리즘/백준(BOJ)
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개..
