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

hyunjin

[BOJ 20440] imso, 누적 합, 좌표 압축

보호되어 있는 글입니다.
알고리즘 연습/백준 2024. 6. 30. 16:54
[BOJ 30870 사이클 없는 그래프 c++ 풀이]

문제 링크코드 문제주어진 그래프에서 t 단계 별로 인접한 노드와 연결 엣지 지워나감.최초로 사이클 생성되지 않는 t 구하기N,M  풀이 전략사이클이 사라지는 것을 찾긴 어렵다.  → 사이클 생성 여부 확인으로 바꾸면 쉽다.주어진 순서대로 간선을 지우고 사이클 생성 여부를 확인 , 지울때마다 사이클을 판단 → TLE그렇다면 역순으로 판단하자.  마지막에 사라졌던 간선들부터 시작하여 처음 사라진 간선들 순서로 그래프가 복원하자.간선이 지워지는 역순으로 그래프를 생성해나가 보면, 어느 순간 사이클 발생 →  (전체 T - 사이클 생성 되는 t) 가 답 요약간선이 언제 지워지는지는 알겠음 : BFS를 적절히 응용지워지는 역순으로 간선을 연결해나가가다가 사이클이 생기는 시점 판단인풋으로 주어지는 K개 시작 노드를..
알고리즘 연습/백준 2024. 6. 20. 14:56
[BOJ22869 징검다리 건너기(small)] 다이나믹 프로그래밍 dp

문제   1. Top Down, 재귀N에 도달 가능 여부만 판단한다.#include #include #include #define MAX_N 5001using namespace std;int N, K;int e[MAX_N], dp[MAX_N];// top - down// 도달 가능 여부만 확인하면 된다// 갈 수 있으면 바로 끝 // 2중 for 사용 가능int canGo(int target) { int& ret = dp[target]; if (ret != -1) return ret; ret = 0; //0으로 설정, 일단 못간다 세팅 // i -> target으로 이동 for (int i = 0; i > N >> K; for (int i = 0; i > e[i]; ..
알고리즘 연습/백준 2024. 5. 18. 00:10
[BOJ 5875 오타 c++] 자료구조 누적 합

문제 풀이좀 조건이 까다로웠다. ( +1) -1로 놓고 생각했다.순차적으로 해당 위치를 반대 괄호를 바꿨을 때 불가능한 경우를 생각해보면 (단, 한번의 오타만 냈다는 조건이 중요하다)양끝단 검사. 맨 앞은 ( , 맨 뒤는 ) 이어야한다.최종적으로 ( ) 개수가 같아야하므로 맨 끝에 합이 0 나와야한다. ( → )  : 해당 위치에서  ~ 맨 끝에 음수가 있는지 확인.  ) → (  : 해당 위치에서 앞 부분에 음수 있는지 확인.( ) ) ( ( )  이 케이스를 생각해보면 된다.  1차 코드#include #define MAX_N 100001using namespace std;string str;int arr[MAX_N];int sum[MAX_N];int len;bool possible(int idx, ..
알고리즘 연습/백준 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에 묶음 가성비 좋은 가게로 설정해두고A를 y개 미만일 때까..
알고리즘 연습/백준 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
이전 Prev 1 2 3 4 ··· 9 Next 다음