본문 바로가기

PS

 (173)
[ 백준 / C++ ] 1744 : 수 묶기 [ 문제 ] 1744번: 수 묶기 [ 접근방법 ] 수열값은 3가지 경우로 처리한다. 1. 1은 묶지 않고 무조건 더한다.2. 양수는 큰 수끼리 묶어서 더한다.3. 음수는 작은 수끼리 묶어서 더한다. 2와 3의 경우는 사실상 절대값이 큰 수끼리 묶는다고 생각하면 된다. [ 소스코드 ] #include #include #include using namespace std;int main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int ans = 0; vector pos, neg; for (int i = 0; i > x; if (x == 1) ans++; else if (x ..
[ 백준 / C++ ] 1562 : 계단 수 [ 문제 ] 1562번: 계단 수 [ 접근방법 ] dp[ m ][ i ][ j ] = [ 숫자 사용 여부 ][ 길이 ][ 마지막 숫자 ]를 만족하는 개수. 숫자 사용 여부는 비트마스크를 활용하여 빠르게 확인하였다.만약 숫자 x를 사용했다면 m의 (x + 1)번째 비트는 1이다. (m >> x) & 1 = 1; 계단수의 정의에 따라 [ 마지막 숫자 ] ± 1에 대해 dp를 갱신하며,모든 숫자 사용 여부는 [ 숫자 사용 여부 ] = (1 따라서 최종적으로 dp[ (1 [ 소스코드 ] #include using namespace std;const int MOD = 1e9;long long dp[1 > n; for (int j = 1; j 0) { ..
[ 백준 / C++ ] 2473 : 세 용액 [ 문제 ] 2473번: 세 용액 [ 접근방법 ] 먼저 전체 용액 벡터를 정렬한 뒤, 노가다를 진행한다. 앞에 2개의 용액은 for문을 통해 정해두고, 나머지 용액은 lower_bound() 함수를 통해 빠르게 구한다. 2개 용액의 특성값 합을 cnt라고 하면, 나머지 용액은 -cnt 기준으로 lower_bound() 함수를 돌려 변수 k에 저장한다.나머지 용액은 k번째 용액이라고 생각하면 된다.약간의 오차가 발생할 수 있기에 k - 1번째 용액에 대해서도 계산을 진행한다. 시간 복잡도는 O(N²logN) 이고, N ≤ 5000 이므로 충분하다. [ 소스코드 ] #include #include #include using namespace std;int main(){ ios::sync_with_std..
[ 백준 / C++ ] 14567 : 선수과목 (Prerequisite) [ 문제 ] 14567번: 선수과목 (Prerequisite) [ 접근방법 ] 먼저 위상 정렬을 통해 과목 우선 순위를 파악하고 dp를 통해 최소 요구 학기를 계산한다. 1. 과목 순서관계를 adj 배열에 저장하고 이를 바탕으로 위상 정렬을 실시한다. 이 때, dfs를 활용한다.2. 정렬 결과를 ord 벡터에 저장하고 이를 바탕으로 dp를 진행한다. 이 때, dp[ i ]는 i번 과목을 이수하는데 필요한 최소 학기이다. [ 소스코드 ] #include #include #include using namespace std;void dfs(int u, vector &visited, vector &ord, vector adj[]){ visited[u] = true; for (int v : adj..
[ 백준 / C++ ] 17472 : 다리 만들기 2 [ 문제 ] 17472번: 다리 만들기 2 [ 접근방법 ] 먼저 BFS를 활용하여 전체 섬의 개수를 파악하고 번호를 매긴다. 이 때 지도도 수정해준다. 그 후 지도를 for문으로 돌면서 각 섬 사이의 최단 거리를 측정한다.지도 크기가 작기에 브루트포스로 계산하였다. 각 섬 사이의 최단 거리를 바탕으로 MST를 통해 모든 섬을 연결하는 다리 길이의 최솟값을 구한다.프림 알고리즘을 활용하여 MST의 총 가중치를 계산하였다. [ 소스코드 ] #include #include #include #include using namespace std;struct Point{ int x, y;};const int INF = 1e5;const int dx[4] = {-1, 1, 0, 0};const int dy[4] ..
[ 백준 / C++ ] 4386 : 별자리 만들기 [ 문제 ] 4386번: 별자리 만들기 [ 접근방법 ] 프림 알고리즘을 활용하여 MST의 총 가중치를 계산하였다. 프림 알고리즘은 MST의 시작점을 하나 정하고, MST와 연결된 최소 가중치 간선을 기준으로 확장하는 방식이다. 최소 가중치 간선을 선택하는 과정에서 우선순위 큐를 활용하여 시간복잡도를 줄였다. 오차를 줄이기 위해 double형 변수를 선언하여 값을 계산하였다. [ 소스코드 ] #include #include #include #include #include using namespace std;int main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector> points(n); for (int i..
[ 백준 / C++ ] 4195 : 친구 네트워크 [ 문제 ] 4195번: 친구 네트워크 [ 접근방법 ] 기존 Union-Find에서 집합의 크기를 구하는 기능을 추가 구현하는 문제이다. 일단 unordered_map 자료구조를 활용하여 친구 아이디와 집합 인덱스를 매핑하였다.그리고 기존 Union-Find 구현에서 size 벡터를 추가하여 집합의 크기 또한 갱신해주었다. [ 소스코드 ] #include #include #include using namespace std;int find(int x, vector &root){ if (root[x] == x) return x; return root[x] = find(root[x], root);}void unite(int x, int y, vector &root, vector &height, ve..
[ 백준 / C++ ] 1717 : 집합의 표현 [ 문제 ] 1717번: 집합의 표현 [ 접근방법 ] Union-Find 트리를 구현하는 문제다.Union-Find 트리는 요소 a와 요소 b가 같은 그룹인지 검사하거나 둘을 병합하는 작업을 빠르게 진행할 수 있다.전체적으로 트리 구조이므로 각 요소도 트리다. 일단 같은 그룹인지는 각 트리의 루트 노드를 확인하면 알 수 있다.검사하는 과정에서 각 노드의 루트를 갱신해준다. 두 요소를 병합하는 작업은 트리의 높이를 비교하여 작은 쪽을 큰 쪽 아래에 붙여준다.이렇게 하면 트리를 최대한 효율적(비편향적)으로 만들 수 있다. [ 소스코드 ] #include #include using namespace std;vector par(1000001), ran(1000001, 0);int find(int x){ i..

티스토리툴바