목록알고리즘 연습/백준 (68)

hyunjin

[BOJ 5875 오타 c++] 자료구조 누적 합

문제 풀이좀 조건이 까다로웠다. ( +1) -1로 놓고 생각했다.순차적으로 ..
알고리즘 연습/백준 2024. 4. 28. 14:37
[BOJ 3343 장미] 정수론, LCM

문제최소공배수 구하는 방법 $N =10^15$ 크다. 완탐하면 시간 초과 발생.접근의 핵심은 두 수 a,b의 최소공배수 개념 접근법최소공배수를 찾을 필요는 없지만 최소 공배수 개념을 활용해서 묶음의 가성비를 구한다. A :  2 개 →    3원      X 10B : 10개 →  14원      X  2 A :  20개 →   30원B :  20개 →   28원  win 묶음의 가성비는 B가 더 좋다.A의 묶음 개수 x, B의 묶음 개수 y라 할때만약, 총 x*y(최소공배수) 개를 사야한다면 B를 x개 사는 것이 더 이득이다.B를 x개 사는 게 더 이득이다. ==> A를 y개 이상 살 필요가 없다. (y-1개 이하일 땐 아니란 의미) 그러니 B에 묶음 가성비 좋은 ..
알고리즘 연습/백준 2024. 4. 25. 17:17
[BOJ 2933 미네랄] 구현 그래프 너비 깊이 우선

문제 문제 포인트는 제거 이후 움질일 클러스터를 찾는 부분 문제에서 공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다. 라는 조건이 주어졌다. 하지만 잘생각해보면 아래와 같은 케이스가 있다. 3 3 xxx x.x ..x 1 3 .xx ..x x.x 움직이는 클러스더가 (2,1) 하나이긴 하지만 (1,1)이 제거된 이후에 움직일 가능성이 있는 것은 (2,1)과 (1,2) 클러스터 2개이다. 물론 (1,2) 클러스터가 움직이지 않아서 결론적으로 하나의 클러스터만 움직이지만 그것을 확인하는 과정에선 여러 클러스터가 움직일 가능성이 있다고 판단. 처음엔 이걸 생각못하고 제거되는 위치의 아래는 확인하지 않았다. #include #include #include..
알고리즘 연습/백준 2024. 4. 23. 13:24
[BOJ 9370 미확인 도착지] 다익스트라 dijkstra 그래프 최단경로

문제 S - G - H - T 혹은 S - H - G - T 의 경로가 S - T로 가는 최단 경로인지 확인하면 된다. 그래서 S,G,H 각각의 정점을 시작으로 하는 최단 길이를 다익스트라로 구한다. #include #include #include #include #define INF 0x7f7f7f7f #define MAX_N 2001 using namespace std; int N; int S, G, H; int dist[MAX_N][MAX_N], mdist[MAX_N], mdist_g[MAX_N], mdist_h[MAX_N]; bool vis[MAX_N]; void dijkstra(int start, int *d) { memset(vis, 0, sizeof(vis)); d[start] = 0; fo..
알고리즘 연습/백준 2024. 4. 22. 14:42
[투포인터 BOJ20922 BOJ22862]

BOJ 20922 겹치는 건 싫어 O(N) #include #define MAX_N 200000 #define MAX_A 100001 using namespace std; int N, K; int arr[MAX_N]; int cnt[MAX_A]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> K; for (int i = 0; i > arr[i]; int ans = 1; int left = 0, right = 0; while (right < N) { int num = arr[right]; if (cnt[num] < K) { cnt[num]++; } else { while (arr[left] !..
알고리즘 연습/백준 2024. 4. 20. 15:47
[가장 긴 증가하는 부분 수열] LIS, DP, 이분탐색

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 최장 증가 수열 (LIS, Longest Increasing Subsequence) 다이나믹 프로그래밍을 이용한 방법 : O(N^2) - 최장 길이 구하는 방법 앞 순서의 모든 원소에서 끝나는 최장 증가 수열들의 길이 중 가장 긴 것을 골라 1을 더한 것이 곧 현재 수에서 끝나는 최장 증가 수열의 길이이다. 따라서 dp..
알고리즘 연습/백준 2024. 4. 19. 16:24
[BOJ 15663/15664 c++]N과 M, set, backtracking

15663 set 풀이 set은 키의 중복 허용하지 않고 키값 정렬시킨다. //참고 사이트 https://tooo1.tistory.com/327 #include #include #include #include #define MAX 9 using namespace std; int N,M; int num[MAX]; //input bool visited[MAX]={0,}; int arr[MAX]; set s; void Backtrack(int depth){//depth : depth이자 arr의 index if(depth == M){ vector v; for(auto i = 0; i>N>>M; for(int i = 0 ; i>num[i]; sort(num,num+N); Backtrack(0);//depth 의..
알고리즘 연습/백준 2022. 10. 1. 11:57
[C++][BOJ 7662 이중 우선순위 큐] multiset

백준 이중 우선순위 큐 문제를 읽고 priority_queue 오름차순, 내림차순 2개를 사용해서 풀었으나 고려해야할 부분이 더 생겼고 결국 틀렸다. priority_queue 처럼 자동으로 정렬되면서 대신 앞 뒤 두 방향으로 다 접근 가능한 container가 set이라는 것을 찾았다. 그런데 set은 중복이 허용되지 않고 중복이 허용되는 것은 multiset이었다. 헤더파일 : #include multiset 사용법 multiset은 기본으로 오름차순 정렬된다. [소스 코드] multiset 사용 // multiset 사용법 #include #include #include using namespace std; typedef long long ll; void Solve(){ int testCase; c..
알고리즘 연습/백준 2021. 12. 15. 16:26
이전 Prev 1 2 3 4 ··· 9 Next 다음