본문 바로가기

알고리즘56

백준 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.
백준 1956 운동 C++ 간단한 해설 v가 적고, 간선 또한 v*(v-1)개이다에서 사실 플로이드를 염두에 두고 있었으나, 다익스트라로 풀리나 한번 해봤다. 결국 33~36%대에서 시간초과가 나서 플로이드로 풀었다.  플로이드를 구현하는 법은 상당히 간단하다. for문을 3번 돌리는데 이런 식으로 생각하면 편하다. for(int k=1;k 답 #include #include #include using namespace std;vector> graph; int ans=987654321;int v,e;int main(){ cin.tie(0); ios_base::sync_with_stdio(0); cin>>v>>e; graph.resize(v+1,vector(v+1,987654321)); int a,b,c; for(int i=0;i>.. 2024. 10. 6.
백준 17069 파이프 옮기기 2 C++ 간단한 해설 단순히 메모이제이션을 통해서 파이프를 옮기면 된다. 파이프의 모양이 3개 있으니까, 2차원 위치를 나타내는 배열 + 파이프의 모양으로 3차원 배열 선언하였다.  그런데 자꾸 예제 5번의 답이 50445956이 나와서, 다른 예제는 다 맞는데 뭐가 문제이지 1시간고민했었는데,정답인 4345413252가 43억으로 int 형의 범위를 초과해서 그런 것이였다. 감이 다죽었네...  답 #include #include #include #define ll long longusing namespace std;int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int n; cin>>n; vector> v(n,vector(n)); .. 2024. 10. 2.
백준 2294 동전 2 C++ 간단한 해설 1차원 dp로 해결 밑이랑 비슷한 방식 백준 1106 호텔 C++2차원 dp로 할려다가, 기존의 배낭문제처럼 최댓값을 이어서 받는 것은 고객 수의 idx가 배수가 아닐 경우, 문제가 생겨서 1차원 dp로 해결하였다. 주석을 상세히 다시 달아보았다. 적어도 c명 이상ash9river.tistory.com    답#include #include #include using namespace std;int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int n,k; cin>>n>>k; vector v(n); for(int i=0;i>v[i]; } sort(v.begin(),v.end()); vector dp(k+1,987654321); for(int i=.. 2024. 9. 30.
백준 14502 연구소 C++ 간단한 해설 그냥 간단한 브루트포스 + bfs10분컷 답#include #include #include #include using namespace std;vector picker;vector> v;vector> canMakeByeok;vector> vir;int n,m,ans;int dy[4]={1,-1,0,0};int dx[4]={0,0,1,-1};bool set(int y,int x,vector>& table){ if(y=n||x=m) return false; if(table[y][x]!=0) return false; return true;}void bfs(){ vector> tmpV=v; for(int i=0;i> q; for(int i=0;i>n>>m; v.resize(n,vector(m)); .. 2024. 9. 26.
백준 17141 연구소 2 c++ 간단한 해설N이 50밖에 안되서 간단하게 바이러스를 놓는 위치를 정하는 것은 브루트 포스, 바이러스 전파를 BFS로 하면 쉽게 풀린다.  답#include #include #include #include #include using namespace std;vector> vir;vector picker;vector> v;int n,m,ans=987654321;int dy[4]={1,-1,0,0};int dx[4]={0,0,1,-1};bool set(int y,int x,vector>& visited){ if(y=n||x=n) return false; if(v[y][x]==1) return false; if(visited[y][x]) return false; return true;}vo.. 2024. 9. 25.

티스토리툴바