본문 바로가기

1p1d

 (7)
[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
Schedule 2021-01-21 11729 : 하노이 1753 : 최단경로 dijkstra 01-22 1931 : 회의실 배정 1937 : 욕심쟁이 판다 greedy 01-23(토) 3344 : N-queen 2589 : 보물섬 dfs / bfs 01-24(일) 7569: 토마토 dfs / bfs
[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..
[Day 2] 백준 1931 : 회의실 배정 해법 : 정렬 후 greedy 사실 처음보고 무조건 DP로 짰다가 시간초과가 나와서 다시 생각해보았다. 해답은 회의가 끝나는 시간을 기준으로 오름차순 정렬한 뒤에 배열의 앞에서부터 보면서 조건에 맞는(회의 시작 시간이 내가 담은 회의들이 끝나는 시간이 크거나 같은 애들)을 담으면 된다. 왜 Greedy 가 해법일까? 조건에 맞는애가 있을 때 그 애를 선택하지 않고 다음 거를 선택했을 때 얻을 수 있는 이익이 없다. 즉, 현재 지점을 i라고 한다면 i대신 i+1을 선택했을 때(i+1도 조건에 맞는다고 가정하면) 얻는 이익이 없다는 것이다. 그 이유는 회의 종료 시간을 기준으로 정렬했기 때문에 i의 회의 종료 시간이 i+1의 회의 종료시간보다 작거나 같기 때문이다. #include #include #incl..

티스토리툴바