본문 바로가기

acmicpc

 (5)
[Day 4] 백준 9663 : N-queen 사실 3344번을 풀려고 했지만.. DFS로는 도저히 시간복잡도가 나오지 않는다. 그래서 다른 해법들을 찾아보니 케이스 by 케이스로 분류해서 비교해보는 문제였기 때문에 비교적 작은 값들로 시행하는 9663번을 선택하여 풀게 되었다. 해법 : DFS 이긴 한데 사실상 시간 제한이 10초이기 때문에 가능한 해법이라고 볼 수 있다. 그만큼 DFS 시간복잡도가 매우 나쁘다. 특히 이 문제에서는 O(n!)의 시간복잡도.. n 최대가 15여서 가능한 풀이라고 볼 수 있다. 어릴 때 이 문제를 처음 봤을 때에는 대각선 분류를 어떻게 해야하는지를 가지고 많은 시간을 고민했었던 것 같다. 그 학습의 결과인지 모르겠지만 대각선 분류는 행 번호(i)와 열 번호(j)를 이용하여 쉽게 할 수 있다. slash 방향의 대각선은..
[Day 4] 백준 7569 : 토마토 해법 : 3차원 bfs 정보올림피아드 2013 초등본선 3번 문제인데 이 당시에 본선에서 문제를 풀 때.. 그냥 배열로 3차원을 구현할 수 있을지 몰랐어서.. 당황했던 기억이 난다. 사실 그냥 2차원에서처럼 3차원에 적용해서 풀어주면 된다. 유의할 점은 for 문을 작성할 때 행, 열, 차원 순서가 아니라 차원, 열, 행 순서로 작성해야 한다는 점 정도 인듯. #include #include #include #include #include using namespace std; int n,m,h; int A[105][105][105]; int vt[105][105][105]; struct tuple2 { int x,y,z; int val; }; vector que; int r,f; int ans; int ..
[Day 3] 백준 2589 : 보물섬 해법 : bfs 최단 거리들 중에서 최대값을 찾아야하는데 map의 크기가 50*50이기 때문에 각각의 점들에 대해서 bfs를 각각 돌려도 시간복잡도가 충분히 나온다. #include #include #include #include using namespace std; int n,m; int M[55][55]; int vt[55][55]; int que[2505][3]; int r,f; int _max; int X[4]={0,0,1,-1}; int Y[4]={1,-1,0,0}; void bfs(int x,int y) { que[r][0]=x; que[r][1]=y; que[r++][2]=1; int i,j; for(i=0;i
[Day 1] 백준 1753 : 최단경로 해법 : dijkstra 그런데 시간복잡도 문제 때문에 heap dijkstra로 작성해야 한다. 편이를 위해서 STL을 사용하였다. dijstra 설명 : [알고리즘] Dijkstra (tistory.com) [알고리즘] Dijkstra 최단 경로 알고리즘에는 다양한 종류의 알고리즘이 있는데 그 중에서 Dijkstra는 하나의 시작점에서 다른 모든 노드까지의 거리의 최소를 알려준다. Dijkstra 알고리즘을 사용하기 위한 조건으로 algorithm01.tistory.com #include #include #include #include #include #define INF 99999999 using namespace std; int n,e; int s; struct tuple2 { int node; ..
[Day 1] 백준 1937 : 욕심쟁이 판다 해법 : 이것도 greedy 음 사실 이것도 처음에 dfs로 뻘 코딩을 했다가 다시 생각해보았다. 사실 제목부터가... 물론 다른 의미지만 왜 greedy같은 형식으로 문제 푸는 것이 가능할까? 판다가 선택하는 기준에 방향성이 있기 때문인 것 같다. 시간복잡도와 내용을 고려해서 한 번 더 고민하는 것이 필요할듯.. #include #include #include #include using namespace std; int n; int A[505][505]; struct tuple2 { int x,y,val; }; tuple2 s[250005]; int _x[4]={1,-1,0,0}; int _y[4]={0,0,1,-1}; int m[505][505]; int _max; bool sf(tuple2 a,tu..

티스토리툴바