배웠던 Union-Find를 복습하기 위해 풀어봤습니다. 동빈나 유튜버 님이 구현한 함수를 최대한 이용해보려고 했습니다. 3개 함수(getParent, unionParent, findParent) 모두 이용하고 인자에 부모 노드 배열을 전달하는 방식으로 구현했더니 시간초과 에러가 발생했습니다. 시간초과 문제를 해결하기 위해 1) 함수 하나를 줄이고 2) 인자를 통해 부모 노드 배열을 전달하는 대신 전역변수로 설정하니 통과했습니다. (getParent, unionParent 사용) 시간 초과 됐던 코드 #include using namespace std; int n, m; int getParent(int parent[], int x) { if(parent[x] == x) return x; return pa..

Union-Find는 그래프 알고리즘 중 하나입니다. 합집합 찾기 또는 서로소 집합(Disjoint-Set) 알고리즘이라고 불립니다. 같은 그래프 내에 확인하고 싶은 노드들이 있는지 확인할 수 있는 알고리즘입니다. Union-Find를 구현하기 위해서는 부모 노드를 가리키는 배열이 존재해야 합니다. 처음에는 모든 값이 자기 자신을 가리키도록 만듭니다. 표와 그림으로 그리면 아래와 같습니다. 노드 1 2 3 4 5 6 7 8 노드의 부모 1 2 3 4 5 6 7 8 이후 2개의 노드를 연결하면 연결된 노드 중 더 작은 값으로 부모 노드 배열 값을 바꿔줍니다. 만약 1과 2가 연결되었다고 하면 2의 부모 노드 아래와 같이 1로 바뀝니다. 부모의 값이 같아짐으로써 노드들을 합칠 수 있습니다. (Union 알고..

코딩테스트 후기 좀 많이 지나긴 했지만 2022년 5월 1일에 있었던 삼성SDS 코딩테스트 후기를 작성해보려고 합니다. 후기라기보다는 어떻게 준비했었는지가 더 맞는 것 같지만 일단 기록해두면 리마인드하면서 다시 공부할 마음을 잡을 수 있을 것 같아서요 :) 잘 알려진 대로 삼성 코딩테스트는 3시간 동안 2문제가 주어집니다! 저는 1문제만 팬다...라는 마음가짐으로 3시간 동안 1문제를 열심히 풀었습니다. 저는 오후 시간이었는데 당연히 첫 번째 문제가 더 쉽겠지 생각해서 먼저 열어서 풀었어요. 근데 다 풀고 두 번째 문제 열어보니 두번째 문제가 더 쉬웠던... 문제 오픈 시간에 따라서도 합격 여부가 달라진다는 말이 있어서 쉽사리 두번째 문제를 열어보지 못했어요. 첫 번째 문제를 쭉 읽어보는데 문제 이해는 ..

15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net #include #include #include using namespace std; #define INF ((int)1e9) struct cctv { int r, c, num, dir; }; int N, M, ans; int map[8][8]; static int dr[4] = { -1, 0, 1, 0 }; static int dc[4] = { 0, 1, 0, -1 }; vector cctvs, cctv_5; void CountZero() { int ..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net #include using namespace std; enum { UP, DOWN, LEFT, RIGHT }; struct board_t { int b[20][20]; }; int N; int maxVal; void moveTo(board_t& board, int dir) { for (int i = 0; i < N; i++) { bool isPossible = true..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 예전에 풀었던 문제인데 지금 다시보니 DFS로도 풀 수 있을 것 같네요! #include #include using namespace std; #define MAXN 15 int N; // N+1일에 퇴사 int T[MAXN + 5]; // 상담 완료하는데 걸리는 기간 int P[MAXN + 5]; // 상담 했을 때 받을 수 있는 금액 int C[MAXN + 5]; int sol; void InputData(void) { cin >> N; for (int i = 1; i > T[i] >> P[i]; } } int max(int a,..