제민

32965 집합 연산 (동아리 게시글에 쓴 글을 복사해온거라 깔끔하지 못합니다...) 문제는 간단합니다.집합 S가 존재할 때, 다음의 연산을 수행할 수 있습니다.S의 원소 개수가 n개일 때, S의 원소로 n이 있다면 n을 제거하고, 없다면 n을 추가한다.Q개의 쿼리가 주어지고, 각 쿼리마다 수열에 연산을 K_i번 했을 때, 수열의 합을 출력해야 합니다.이때 연산 결과는 누적됩니다.처음엔 다이나믹 세그먼트 트리를 떠올렸습니다. Lazy까지 붙여서 하려고 했는데, 이 문제에 적합하지 않기도 하고 반례가 존재했습니다.이후 혹시나 내가 모르는 자료구조로 풀 수 있나 싶어서 제곱근 분할법을 봤는데 이것도 마찬가지로 적합하지 않았습니다.그래서 몇 가지 관찰 이후 수학으로 접근해 해결했습니다.풀이에 도달하기까지의 관..

Tag : 순열 사이클 분할, DP원형 DP인 점과 그래프 모델링을 떠올리는 아이디어가 쉽지 않습니다. 새 창에서 열기

BOJ 3116 생물학자https://www.acmicpc.net/problem/3116조건 - 박테리아의 시작 위치가 겹치는 경우가 없으며, 적어도 한 번은 박테리아가 만난다. - 1풀이 - sol 1. (MLE){X,Y,T}를 key로 하는 Map에 몇 개의 박테리아가 이 때 모이는지 카운트하는 코드를 짰다. 문제점은 겹치는 박테리아들에 대한 처리를 따로 해줘야 했다. 이것도 마찬가지로 {박테리아 idx, T}를 key로 갖는 Map을 만들어 체크했다. 결과적으로 코드는 잘 동작했지만 MLE를 받았다. 이후 코드를 갈아엎어야 한다는 것을 깨달았다.더보기MLE 코드#include using namespace std;#define fastio cin.tie(NULL)->sync_with_stdio(fal..

제 4회 숙명여자대학교 프로그래밍 경진대회 SMUPChttps://www.acmicpc.net/category/detail/4212 C E를 푸는데 이 글에서 도움을 많이 받았습니다.https://gall.dcinside.com/mgallery/board/view/?id=ps&no=44800A. SMUPC NAME B1https://www.acmicpc.net/problem/31859 구현 + 문자열더보기#include using namespace std;typedef long long ll;const ll INF = 0x7f7f7f7f7f;int n,dels;int alpha[30];string x,ans;int main() { ios::sync_with_stdio(0); cin.tie(0)..

https://youtu.be/o9BnvwgPT-o?si=h9QqnjghGsans5cF 플로이드-와셜과 같은 최단경로 알고리즘입니다.플로이드-와셜은 음수 간선이 존재하는 경우에서는 사용 가능하고, 음수 "사이클" 이 존재하는 경우 사용 불가능했습니다.  다익스트라는 음수 간선이 존재할 경우 사용할 수 없다는 특징을 갖습니다. 한 정점에서부터 다른 정점까지의 최단경로를 구할 수 있습니다.2024/05/13 기본 틀 학습 (경로복원 X) BOJ 1753 최단경로 G4https://www.acmicpc.net/problem/1753 설명이 있는 코드는 이곳에서 확인 가능합니다.더보기#include using namespace std;typedef pair Pii;#define X first //가중치#defi..

https://codeforces.com/contest/1971 Dashboard - Codeforces Round 944 (Div. 4) - Codeforces codeforces.com 일단 ABC 3솔입니다...D는 솔직히 할만했는데 피곤해서 잘못된 알고리즘을 세워서 틀렸습니다.A. My First Sorting Problem테스트케이스마다 a, b를 입력받고 두 값 중 작은 값과 큰 값을 순서대로 출력하는 문제입니다.더보기#include using namespace std;typedef long long ll; int main() { ios::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL); int t; cin>>t; while(t--){ int a..

해당 글을 보고 정리한 내용입니다. 오프라인 쿼리와 Small To Large단어만 들으면 어려워보이지만 그렇지 않다. 오프라인 쿼리는 주어진 쿼리를 순서대로 처리하지 않아도 되는 경우에 사용할 수 있는 테크닉이다.쿼리를 모두 저장하고 역순으로 돌면서 쿼리를 처리하는 기법이다. Small To Large는 작은 집합을 큰 집합으로 합치는 테크닉으로, 시간복잡도를 줄이는데 큰 도움이 된다.오프라인 쿼리의 연습 문제로 "BOJ 13306 트리" 가 있다.https://www.acmicpc.net/problem/13306 해당 문제에서 쿼리는 총 두 종류로, 0 X : X와 X의 부모를 잇는 간선을 제거1 A B : A와 B를 연결하는 경로가 존재하는가? 문제를 잘 보면 쿼리를 순차적으로 살펴보았을 때, 마지..

https://www.acmicpc.net/problem/18251 중위 순회로 각 노드의 높이와 가중치를 저장해 놓고, 스위핑을 통해 최대값을 구하면 됩니다.주의할 점은 모든 노드의 가중치가 음수일 경우인데, 그럴 경우 그 중 가장 큰 가중치를 출력해주면 됩니다.중위순회를 하면 가장 왼쪽 노드부터 오른쪽으로 방문하므로 중위순회 중 백터에 값을 넣게 되면 자연스럽게 왼쪽 노드부터 오른쪽 노드가 순서대로 들어가게 됩니다. 포화 이진 트리이므로 트리의 높이는 log2(N)으로 구할 수 있습니다. 더보기#include using namespace std;typedef long long ll;#define YY first#define WW secondint n;ll W[28'0003];vector> P;void..

KOI 2022 1차대회https://www.acmicpc.net/category/665초등부 A 빵 B4https://www.acmicpc.net/problem/25377 도착 시간이 빵이 들어올 시간보다 작거나 같으면 빵을 먹을 수 있습니다.이를 만족하는 가장 작은 빵이 들어오는 시간을 구하면 됩니다.더보기#include using namespace std;typedef long long ll;int n;vector ans;int main() { ios::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL); cin>>n; for(int i=0;i>a>>b; if(a B 조약돌 G1https://www.acmicpc.net/problem/25378 DP 문제..

KOI 2021 1차대회https://www.acmicpc.net/category/528초등부 A 지우개 B2https://www.acmicpc.net/problem/21756 대충 구현하면 됩니다.더보기#include using namespace std;typedef long long ll;int n;vector arr;int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n; for(int i=1;i=2){ vector tmp; int idx=1; for(int x : arr){ if(idx%2==0) tmp.push_back(x); idx++; } arr=tmp; } cout B 나누기 G2ht..

https://www.devicemart.co.kr/goods/view?no=12525556 작년에 한 번 써봐서 사용하는데 어렵진 않았습니다.아두이노용 OLED의 통신 방법에는 I2C와 SPI가 있습니다.간단하게 SPI는 7핀, I2C는 4핀으로 보시면 될 것 같습니다.대부분의 OLED는 I2C 통신을 지원하기에 해당 제품으로 구매했습니다.물론 I2C가 항상 좋은 것은 아닙니다. 속도는 SPI가 더 낫다는 말도 있습니다. 해당 제품엔 RES핀이 붙어있는데 해당 핀은 무시해도 되는 것 같습니다. Vcc 5VGnd Gnd SDA 20 SCL 21RES X 전에 PM2008M 미세먼지 센서도 I2C 통신이기에 SDA SCL이 겹쳐서 고민이었는데 병렬로 연결해도 문제가 없었습니다.  아두이노에서 OLED를 제..

KOI 2020 1차대회https://www.acmicpc.net/category/503초등부 A 박 터트리기 S4 (고등부에 작성됨) B 피자 오븐 G5https://www.acmicpc.net/problem/19940 Tag : BFS, Greedy, Math 0부터 60을 만드는 방법들을 BFS로 전처리하고, 그리디한 사고로 해결합니다.입력되는 쿼리를 X라고 하면, X/60 번 ADDH를 하고, 남은 횟수는 BFS로 이미 구했으므로 더하면 됩니다.풀이는 간단한데 BFS로 35를 구할 때 문제가 생겨서 여러 번 틀렸었습니다.시간이 충분하다면 모든 60개의 경우를 손으로 적어보는 것도 괜찮은 것 같습니다.중등부 A 햄버거 분배 S3(고등부에 작성됨) B 다이어트 G4https://www.acmicpc...

https://www.devicemart.co.kr/goods/view?no=12240662 제품 설명에는 노란 케이블이라고 나와있는데 파랑 케이블인 것 같다. 빨강 5V검정 GND흰색 SDA (20)녹색 SCL (21)파랑 GND (I2C로 사용) 아두이노 IDE에서 PM2008 Library를 설치한다.example > simple_monitor더보기#include // #define PM2008NPM2008_I2C pm2008_i2c;void getAirState(){ uint8_t ret = pm2008_i2c.read(); uint8_t pm1p0_grade = 0; uint8_t pm2p5_grade = 0; uint8_t pm10p_grade = 0; uint8_t total_gra..

보호되어 있는 글입니다.

https://www.acmicpc.net/category/806Expert DivisionA 스물셋 B2https://www.acmicpc.net/problem/23251  23으로만 이루어진 수의 합으로 나타낼 수 있는 수 중 k번째로 작은 수를 구해야 한다. 23*k를 출력하면 된다.더보기#include using namespace std;typedef long long ll;int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll t; cin>>t; while(t--){ ll x; cin>>x; coutB 자료구조는 정말 최고야 S5https://www.acmicpc.net/problem/23253 문제에서 스택..

https://www.acmicpc.net/problem/2133 풀이https://yabmoons.tistory.com/536 [ 백준 2133 ] 타일 채우기 (C++)백준의 타일채우기(2133) 문제이다.[ 문제 바로가기 ] [ 문제풀이 ]3 x N 크기의 벽을 2 x 1 , 1 x 2 타일들로만 채울 때, 그 경우의 수를 구해야 하는 문제이다.작은 수들부터 차근차근 만들어보면서 하yabmoons.tistory.comhttps://kosaf04pyh.tistory.com/236 [알고리즘 문제] 백준2133 - 타일 채우기https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입..

https://www.acmicpc.net/problem/1071 풀이 참고https://sunrinnote.tistory.com/143https://velog.io/@bgg01578/%EB%B0%B1%EC%A4%80-1071-%EC%86%8C%ED%8A%B8https://oculis.tistory.com/120 백준 1071, 소트개요 문제 링크 플래 5, Greedy a[i+1] != a[i]+1이면서 사전순으로 가장 앞서게 정렬하기 접근 그리디한 인간이 되자. 수를 꺼내서 출력한다고 생각할 때, 가장 작은수부터 꺼내는 것이 가장 유리하다.oculis.tistory.com 백준 1071 소트문제링크 https://www.acmicpc.net/problem/1071 문제 풀이 배열을 오름차순으로 정렬시..

https://www.acmicpc.net/category/detail/3567 2023 가지컵 www.acmicpc.netA가지 교배 B1 https://www.acmicpc.net/problem/27939 B 가지 산사태 S5 https://www.acmicpc.net/problem/27940 C하이퍼  가지 따기 S2 https://www.acmicpc.net/problem/27941 D:danceplant: G5 https://www.acmicpc.net/problem/27942E가지 사진 찾기 G5 https://www.acmicpc.net/problem/27943F가지 이모지 P5 https://www.acmicpc.net/problem/27944G슬슬 가지를 먹지 않으면 죽는다 G3 http..

https://www.acmicpc.net/category/detail/4005 Seoul Nationalwide Internet Competition 2023 www.acmicpc.net2024.04.25https://www.acmicpc.net/problem/30446 30446번: 회문수어떤 양의 정수 $P$에 대해 $P$를 구성하는 숫자들을 왼쪽부터 적는 경우와 오른쪽부터 적은 결과가 서로 일치할 경우, $P$를 회문수(palindrome number)라 한다. 예를 들어 $1$, $101$, $12322321$은 모두 회문www.acmicpc.netPS 갤러리에서 해당 문제에 대한 글이 올라와서 시도해봤는데 실패하고 겨우 해결했다.해결하고 다른 분들의 코드를 보다가 완벽한 풀이를 보고 정리해본다..

https://www.acmicpc.net/problem/13314 13314번: 플로이드에 오타가?평소에 코딩 실력이 부족하다고 느끼고 있는 지구이는 익명게시판에서 “백스페이스 키를 쓰지 않고 코딩하기를 추천합니다” 라는 글을 읽게 되었다. 글의 최하단에는 매우 작은 글씨로 “효www.acmicpc.net작성했던 해설이 날라간 관계로 타 글로 대체함.https://ps.mjstudio.net/boj-13314더보기#includeusing namespace std;int d[103][103];int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n=100; for(int i=1;ihttps://www.acmicpc.ne..

https://youtu.be/dDDy2bEZRA8?si=zCkILIWQt98MpCdQ https://www.acmicpc.net/problem/11404 11404번: 플로이드첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가www.acmicpc.net그래프에서의 최단 경로 알고리즘 중 하나인 플로이드 워셜을 구현하는 문제이다.오버플로 방지를 위해 INF를 0x3f3f3f3f로 해준다.테이블을 채우는 과정에서 k는 경유지라고 보면 이해가 쉽다. i에서 j로 가는데 k를 거쳐가는 경우가 더 빠른지 확인하는 것이다.min 함수로 구현하면 ..

별 찍기는 생략합니다. https://www.acmicpc.net/problem/2562 2562번: 최댓값 9개의 서로 다른 자연수가 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 번째 수인지를 구하는 프로그램을 작성하시오. 예를 들어, 서로 다른 9개의 자연수 3, 29, 38, 12, 57, 74, 40, 85, 61 이 주어 www.acmicpc.net 변수 두 개로 최댓값과 인덱스를 저장해 풀 수도 있겠지만 vector에 익숙해지기 위해 이렇게 짜봤습니다. 더보기 #include using namespace std; vector arr; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); for(int i=1;i>x; arr.pus..

https://www.acmicpc.net/problem/1000 1000번: A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 더보기 #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int a,b; cin>>a>>b; coutb; cout

https://codeforces.com/contest/1955 Dashboard - Codeforces Round 938 (Div. 3) - Codeforces codeforces.com 첫 코포였는데, A B 2솔밖에 못했다. 시간대가 너무 늦어서 피곤한 것도 결과에 영향을 끼쳤던 것 같다. 1955A Yogurt Sale 시간 제한 : 1초 문제 Vosmiorochka 상점에서의 요거트 하나는 가격이 a지만, 두 요거트를 b에 살 수 있는 프로모션이 있다. 사야 할 요거트의 개수는 정확히 n개이다. 두 요거트를 구매할 때, 정가로 살지 프로모션으로 살지 고를 수 있다. 요거트 n개를 사는데 드는 최솟값은 얼마인가? 입력 테스트케이스의 수 t가 들어온다. (1 a>>b; if(a*2 < b){ //프..

https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 유니온 파인드로 이런게 가능할지 몰랐다. Set을 사용한 풀이가 더 직관적인 것 같긴 하지만 유니온파인드가 조금 더 편한 느낌이 있다. 풀이는 다음과 같다. 1. parent 배열 초기화. 2. 값 x를 입력받으면 find(x)와 find(x-1)을 merge. (2-1. 이 때 find(x)의 부모가 find(x-1)인 구조가 되어야 한다.) (2-2. merg..

https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net https://jemin06.tistory.com/129 그래프(3) 문제 중 구슬 찾기마냥 순위를 정할 수 있지 않을까 생각했는데 아니었다. 결국 답지에서 아이디어를 찾았다. 풀이는 다음과 같다. 1. 모든 노드에 대해 선후관계를 정의한다. ex) 5 4 3 입력되었다면 5->4, 5->3, 4->3 식으로 간선을 긋는다. 2. 등수가 바뀐 쌍 a,b가 들어오면 a->b 간선이 존재한다면..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 유니온 파인드를 사용한 크루스칼 알고리즘으로 MST를 구해보았다. 더보기 #include using namespace std; int n,m; //정점 간선 수 int ans; int parent[10'003]; int rnk[10'003]; vector E; void init(){ for(int i=1;irnk[v]) swap(u,v); parent..

위상정렬 https://jemin06.tistory.com/152 위상정렬 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다 jemin06.tistory.com 위상정렬을 배웠다. 위상정렬은 DAG에서만 가능하다는 것을 꼭 기억하자. Union Find https://jemin06.tistory.com/155 Union Find https://m.blog.naver.com/fbfbf1/222278788809 유니온 파인드(Union Find) c++ 유니온 파인드 정의 - 공통 원..

https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 열쇠가 a~f로 6개만 존재하기에 비트마스킹으로 해결할 수 있다.처음에 nkey 대신 key만 써서 틀렸었는데 아직도 틀린 이유를 모른다.key를 갱신하려고 하면 틀린다. #include using namespace std; #define Y first #define X second int n,m; char board[53][53]; bool vis[53][53][1..

https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net "최소 연산 횟수" 를 구하라 했으므로 BFS라는 것을 알 수 있다. vis 배열 대신 set으로 방문 처리를 했다. 다른 코드들을 보니, DFS 풀이도 존재했다. 이 코드에는 불필요한 연산들이 존재한다. 무한대로 증가하는 cur.X, 계속 1로 나누는 나누기 연산 등인데, 이를 없애면 vis 없이도 효율적인 코드를 작성할 수 있다. #include using namespace std; t..