본문 바로가기

전체 글

 (22)
[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

티스토리툴바