본문 바로가기

PS(알고리즘 문제풀이) 관련 글/PS일지

 (33)
2024-04-18 -queuestack(24511, 백준) 해당 자료형에서 stack에 해당하는 부분은 움직이지 않는다. 즉 queue에 해당하는 부분들의 수만 이용해서 queue를 사용하여, 계산하면 풀린다. 더보기 #include #include #include using namespace std; int n, m; int arr[100010]; queue q; vector vc; int main() { int i, j; scanf("%d", &n); for (i = 1; i = 2) { int sum = 0, mx = -2e9, mn = 2e9; for (i = 0; i < ans.size(); i++) { //printf("%d ", ans[i]); sum += ans[i]; mx = max(mx, ans[i]);..
2024-04-01 오늘은 만우절! -수들의 합 2(2003, 백준) 쉬운 2포인터 문제라고 생각했다. 시작점에 low, high를 잡아주고, m을 기준으로 투포인터를 돌리면 풀리는 간단한 문제이다. 풀고보니 O(N^2)도 돌아간다고 한다. 더보기 #include #include #include using namespace std; int n, m; vector vec; int ans; int main() { int i, j; scanf("%d %d", &n, &m); for (i = 0; i < n; i++) { int x; scanf("%d", &x); vec.push_back(x); }vec.push_back(0); int low = 0, high = 0; int res = vec[0]; while (low < n &..
2024-03-31 주말동안 푼 문제중 어려웠던 문제 간단 리뷰 작성. -오민식의 고민 (1219, 백준) 문제에서 버는 돈은 최대화해야 한다는 것은 사용하는 비용을 최소화해야된다는 말과 같다. 즉 사용되는 교통비를 (-)로 두고, 해당 도시에서 얻을 수 있는 이득을 (+)로 둔다면 이 문제는 음의 사이클이 존재하는 최단경로를 구하는 문제가 된다. 즉 벨만 포드 알고리즘을 이용해 풀수 있게 된다. 하지만 음의 사이클이 존재한다고 할지라도 그 사이클에서 도착지점으로 갈 수 없다면, 이는 무의미 함으로 이를 예외처리를 시켜 풀어주어야 한다. 더보기 #include #include #include #include #define INF 2e15 using namespace std; int n, m, s, e; long long p..
2024-03-29 TOPOLOGICAL SORTING 문제들 모아서 풀기 -선수 과목 (14567, 백준) 기본적인 위상정렬 문제이다. ans[x] = x과목을 이수할 수 있는 최소 학기로 두고 진입차수를 감소시킬 때마다 ans를 갱신해주어가며 풀었다. 그냥 DP로도 풀린다고한다. 더보기 #include #include #include #include using namespace std; int n, m; vector vec[1010]; int ent[1010], ans[1010]; int main() { int i, j; scanf("%d %d", &n, &m); for (i = 0; i < m; i++) { int x, y; scanf("%d %d", &x, &y); vec[x].push_back(y); ent[y]+..
2024-03-27 -왕위 계승(5021, 백준) 왕위를 계승하기 위해 초대 왕과 피가 얼마나 섞여있는지 구하면 되는 문제이다. 주어진 유향그래프를 보고 사이클이 없기 때문에 위상정렬을 하는 문제임을 알수있다. 자식노드 = (부모노드1 + 부모노드2) / 2 로 결정되며, 모두 계산후, 주어지는 m명의 사람중 가장 값이 높은 사람을 출력해주면 된다. 더보기 #include #include #include #include #include #include #include using namespace std; int n, m; string king; map vec; map ans; map ent; set st; vector s; int main() { int i, j; cin >> n >> m; cin >> king; ans.i..
2024-03-23 -초콜릿 자르기(2163, 백준) 몇번 직접 그리다보면 규칙을 찾을 수 있다. 항상 N*M의 초콜릿을 1*1로 잘라야 한다. 이때 필요한 초콜릿 조각의 수는 N*M개이고, 한번 자를때마다 초콜릿의 조각은 항상 1개씩 늘어나게 됨으로, 답은 N*M-1개가 된다. 입력되는 수의 범위가 큼으로 자료형에 주의하자. 더보기 #include int main() { long long i, j, n, m; scanf("%lld %lld", &n, &m); printf("%lld", (m * n)-1); return 0; } -서울에서 경산까지(14863, 백준) queue를 이용해 최단경로 구하는 것 처럼 접근을 했지만 생각해보니 Dp를 어렵게 푼것에 불과했다. Dis[현재노드][현재까지 걸린 시간] 일때의 최대 모금..
2024-03-21 -줄서기(14864, 백준) 먼저 1~N까지의 ans배열을 각각의 idx값으로 잡아준다. 그 뒤, 문제에서 입력받는 두 쌍에서 앞쪽 수는 - 뒤쪽수는 +를 시켜준다. 만약 겹치는 수가있거나, 문제에서 주어진 순서와 구해진 순서가 달라지면 -1출력. 아니라면 ans배열을 출력해 준다. 더보기 #include #include #include using namespace std; int n, m; int ans[100010]; bool check[100010]; vector vec; int main() { int i, j; scanf("%d %d", &n, &m); for(i=1;i
2024-03-20 -가운데를 말해요(1655, 백준) 우선순위 큐를 이용한 아이디어성 문제라고 생각한다. mid를 기준으로한 우선순위 큐 두개를 잡아 준 뒤, mid를 기준으로 mid보다 작은 수는 minq에, 큰 수 는 maxq에 넣어준 뒤, minq는 가장 높은수가 위에, maxq는 가장 낮은수가 위에 오게끔해서, 만약 계산후, mid값이 바뀌어야 한다면 균형이 맞게 바꾸어준다. 더보기 #include #include #include using namespace std; int main() { int i, j; int n, mid; priority_queue low, high; scanf("%d %d", &n, &mid); printf("%d\n", mid); for(i=2;i mid) high.push(-x); el..

티스토리툴바