https://www.acmicpc.net/problem/1406 에디터를 구현하는 문제이다. 배열로 구현하면 삽입이나 삭제 연산이 O(N)이 걸리므로 스택이나 연결리스트를 이용해서 O(1)만에 삽입과 삭제가 가능하게 한다. 스택으로 구현시 커서를 기준으로 왼쪽, 오른쪽 두 개의 스택을 두고 구현한다. 스택 이용 1234567891011121314151617181920212223#include #include using namespace std; int main(){ stack l,r; char c,a; while((c=getchar())!='\n') l.push(c); int n; scanf("%d",&n); while(n--) { scanf(" %c",&c); if(c=='L' && !l.empty(..
https://www.acmicpc.net/problem/15501 처음 수열을 뒤집기나 밀기 연산을 통해 결과 수열로 만들 수 있는지 물어보는 문제이다. 두 수열의 원소가 같은 기준점을 잡고 오른쪽 방향으로 볼 때 혹은 왼쪽 방향으로 볼 때 두 수열이 같아야 한다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std; bool operator==(vector &a,vector &b){ int len=a.size(); for(int i=0;i
https://www.acmicpc.net/problem/14500 브루트 포스로 모든 좌표에 대하여 테트로미노의 모든 경우의 수인 19가지를 살펴보면 된다. 탐색 횟수가 최대 500*500*19*4=19000000 이므로 시간 내에 충분히 돌아간다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include using namespace std; int n,m,map[510][510],ans;pair d[19][4]={ {{0,0},{0,1},{0,2},{0,3}}, {{0,0},{1,0},{2,0},{3,0}}, {{0,0},{0,1},{1,0},..
https://www.acmicpc.net/problem/1937 판다가 대나무를 먹으면서 이동한다. 단, 현재 위치의 대나무보다 더 많은 대나무가 있는 쪽으로만 이동한다. 이 때 판다가 이동할 수 있는 최대 길이를 찾는 문제이다. 먼저 DFS를 이용한 완전 탐색을 생각해 볼 수 있다. 그러나 N이 최대일 때, 500*500의 map에서 모든 경로를 다 탐색하면 시간 초과가 나게 된다. 이 때 다이나믹을 이용해서 가지치기를 한다. d[x][y] = 판다가 (x,y)까지 올 수 있는 최대 길이라고 정의하자. 경로를 탐색하다가 d[x][y]가 지금까지 온 경로의 길이 k보다 크다면 이미 다른 경로로 왔을 때의 최대 길이가 존재한다는 뜻이다. 이 경우 더 이상 탐색하는 것이 의미가 없으므로 탐색을 종료한다. ..
https://www.acmicpc.net/problem/8006 K번째 최단경로 찾기와 같은 문제인데 쿼리로 최대 10000개가 들어오므로 매번 구한다면 시간 초과가 난다.D[S][E][K] = S에서 E로 가는 K번째 최단경로의 길이라고 하고 미리 쿼리를 다 구해놓고 각 쿼리마다 D 배열값을 출력해준다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include #include #include using namespace std; int n,m,a,b,c,q,s,e,k;int d[101][101][101];vector adj[..
https://www.acmicpc.net/problem/1854 각 정점의 1번 도시로 부터의 K번째 최단 경로의 소요시간를 찾는 문제이다. 각 정점마다 소요시간들을 저장할 우선순위 큐(Priority Queue)를 할당한다. 그리고 다익스트라를 돌리면서 만약에 해당 정점의 큐의 크기가 K보다 작다면 시간을 그냥 추가해주고 K까지 꽉찼다면 큐의 top(최대값)과 비교하여 새로운 시간이 더 작다면 기존 값을 pop해주고 새로운 값을 넣어주면 된다. 우선순위 큐를 이용하는 이유는 현재까지의 최대 소요시간을 빠르게 찾기 위해서이다. 배열을 사용하면 새로운 거리를 추가하는데 O(1)이 걸리지만 최대값을 찾을 때마다 O(N)이 걸리기 때문에 비효율적이다. 우선 순위 큐를 사용하면 추가하는데 O(logN), 찾는..
https://www.acmicpc.net/problem/2667 지도를 스캔하면서 단지(연결요소)를 찾고 BFS나 DFS를 이용하여 각 단지마다 집의 수를 세준다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std; int n,map[25][25],cnt;int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};vector ans; void dfs(int x,int y){ cnt++; map[x][y]=0; for(int i=0;i
https://www.acmicpc.net/problem/6593 3차원 상에서 시작 지점 S에서 출구 E까지의 최단 거리를 구하는 문제이다. BFS로 구할 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include using namespace std; int l,r,c;char map[31][31][31];bool visit[31][31][31];int dx[6]={-1,1,0,0,0,0};int dy[6]={0,0,0,0,-1,1};int dz[6]={0,0,-1,1,0,0};queue q; void bfs(){ int depth=1;..
https://www.acmicpc.net/problem/1504 반드시 거쳐야 하는 두 개의 정점을 a,b라 하면 1->a->b->n 의 최단 경로와 1->b->a->n의 최단 경로의 길이 중 더 작은 것이 답이다. 각각 다익스트라를 3번씩 돌려주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include #include #define INF 800001using namespace std; int n,m,u,v,w,a,b,p1,p2,ans;vector adj[801]; int dijkstra(int s,int e){ vector dist..