본문 바로가기

알고리즘55

백준 27896 특별한 서빙 C++ 간단한 해설처음에는 투포인터를 사용해서 문제를 풀려고했었다. 그러나 음식을 앞에 서있는 학생부터 순서대로 서빙할 때, 어떤 한 순간이라도 불만도가 M 이상이 되면 학생들은 ‘가지 운동’을 일으키게 된다. 이 지문때문에, 우선순위 큐로 관리해서 푸는 것이 해법임을 깨달았다. 처음부터 일단 음식을 파로 받는다. 그러다가 불만도가 M 이상이 되면, 제일 큰 값을 가지로 바꾸면 된다. (이때, 더해준 값을 빼준 값으로 바꿔야하므로 -2*x_i로 한다.) 답#include #include #include #include #define ll long longusing namespace std;int main(){ cin.tie(0); ios_base::sync_with_stdio(0); ll n,m; cin>>n>.. 2024. 11. 8.
백준 23883 알고리즘 수업 - 선택 정렬 3 C++ 간단한 해설N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 선택 정렬로 배열 A를 오름차순 정렬할 경우 K 번째 교환되는 수를 구해야한다. 그런데 K가 최대 50만이고 시간제한은 3초이니까 30억미만으로 연산을 실행한다고 생각하면 된다. 은근 널널하므로 그냥 하나씩 힙을 이용하여서 인덱스를 추적하는 방식으로 조절하면 된다.  힙을 이용하는 방법에는 여러 가지가 있는데, set, priority_queue, map, multiset, multimap이 있지만, N개의 서로 다른 양의 정수가 저장되어 있으므로 그냥 set을 골랐다.답 #include #include #include #include using namespace std;int main(){ cin.tie(0); ios_base::sync.. 2024. 10. 22.
백준 16469 소년 점프 C++ 간단한 해설 방문 배열을 3개 만들어서 bfs를 통해 최소 방문을 시간을 기록한다.3개 배열을 비교하고, 그 최대값이  세 악당이 모일 때 걸린 시간이다. 답#include #include #include #include using namespace std;int r,c;int board[100][100];int visited[3][100][100];int dy[4]={0,0,1,-1};int dx[4]={1,-1,0,0};bool set(int index,int y,int x,int val){ if(y=r||x=c) return false; if(board[y][x]==1) return false; if(visited[index][y][x]>r>>c; for(int i=0;i>str; for(int .. 2024. 10. 21.
백준 16562 친구비 C++ 간단한 해설 친구의친구는친구니깝부모의부모는부모이다즉디스조인트셋, union-parent를 사용하자. N이 최대 10000이라서 union by rank를 안해도 된다. 답 #include #include #include using namespace std;int n,m,k;int parent[10001];int findParent(int vertex){ if(parent[vertex]!=vertex) return findParent(parent[vertex]); return parent[vertex];}int main(){ cin.tie(0); ios_base::sync_with_stdio(0); for(int i=1;i>n>>m>>k; vector v(n+1); f.. 2024. 10. 15.
백준 27978 보물 찾기 2 C++ 간단한 해설 그냥 다익스트라를 활용하면 된다.어렵지 않고 그냥 쉽게 풀음   답 #include #include #include #include #include using namespace std;vector> v;vector> visited;int ans=987654321;int dy[8]={1,1,1,0,0,-1,-1,-1};int dx[8]={1,0,-1,-1,1,1,0,-1};int h,w;bool set(int y,int x,int val){ if(y=h||x=w) return false; if(v[y][x]=='#') return false; if(visited[y][x]>h>>w; v.resize(h,vector(w)); pair startPoint; pair endPoint; for(int.. 2024. 10. 10.
백준 10830 행렬 제곱 C++ 간단한 해설 A의 B제곱은 분할정복으로 다음과 같은 공식을 사용할 수 있다.A^B=A^(B/2)*A^(B/2) (B is even)A^B=A^((B-1)/2)*A^((B-1)/2)*A (B is odd) 여기서 B에 해당되는 값들을 잘 생각해보면 1, 2, 2^2, 2^3... 이런식으로 분할할 수 있다. 만약에 B가 5라고 생각해보자 그러면 B=2^2+1이라고 생각할 수 있다.만약, B가 21이라고 생각하면 B=2^4+2^2+1이다. 그러면 A의 2제곱n지수들을 메모이제이션하고, B를 비트마스킹해서 그 값들을 곱하는 방식으로 사용하면 된다. B의 최대치가 100000000000이니까 B=100000000000일때를 생각해보자. B를 이진법으로 변환했을 때, 0000000000000000000000000.. 2024. 10. 6.

티스토리툴바