전체 글
-
비숍백준알고리즘 2019. 8. 27. 00:46
백준 온라인저지의 비숍문제다. 예전에 풀어본 경험이 있는 N-Queen문제와 비슷한문제 였고, NQueen 풀떄보다 훨씬 더 많이 시간을잡아먹었고 많이틀렸다. 다른것보다, 이런 2차원 배열에서 대각선으로 주는 조건은 행 + 열 , 행 - 열 이런식으로해서 규칙성을 찾아낼수가 있어서, r[21] c[21] 배열에, 해당하는 규칙에서 맞는것들을 체킹해주면서 진행하는 재귀함수를 한큐에 썼는데 이게 시간복잡도가 생각보다 엄청나게 큰모양이다. 사실상 전부 해보는거니까 O(N*N)의 시간복잡도가 소요될거라 예상한다. 그래서 일단 비숍이 들어갈수 있는 후보인 맵의 1을 벡터 페어로 잡아서 해봤는데, #include #include #include #include using namespace std; int n; in..
-
불!백준알고리즘 2019. 8. 26. 18:41
#include #include #include #include #include using namespace std; struct man { int x, y; bool life = true; }; man ji; int n, m; int map[1000][1000]; int d[1000][1000]; bool quit = false; bool dead = false; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; int timee = 0; vector mm; vector f; void bfs2() { queue q; for (int i = 0; i < mm.size(); i++) { q.push({ mm[i].first, mm[i].second }); } if (..
-
수들의 합 2백준알고리즘 2019. 8. 26. 00:38
#include #include using namespace std; int n, m; int sum,ans; int main(){ scanf("%d %d", &n, &m); int *a = new int[n]; for(int i = 0; i right && left < n){ right = left; sum = a[left]; } } } printf("%d\n", ans); return 0; } 정말 오랜만에 동적배열 할당해본듯... 문제는 어렵지않았고, 투포인터 사용해서 ..
-
-
나이트의 이동백준알고리즘 2019. 8. 14. 17:58
#include #include #include #include #include using namespace std; struct posi{ int x,y; }; posi st, ed; int tc; int l; int map[300][300]; bool d[300][300]; int dist[300][300]; int dx[] = {-2, -1,-2,-1,1,2,2,1}; int dy[] = {-1, -2,1, 2,-2,-1,1,2}; int ans = 0; void bfs( ){ queue q; q.push({st.x, st.y}); dist[st.x][st.y] = 0; d[st.x][st.y] = true; while(!q.empty()){ int x = q.front().first; int y ..
-
다리만들기백준알고리즘 2019. 8. 14. 17:55
#include #include #include #include #include using namespace std; int n; int map[100][100]; int mapping[100][100]; bool d[100][100]; int dx[] = {0,0,1,-1}; int dy[] = {1,-1,0,0}; int ans = 100000000; void bfs(int x, int y, int value){ queue q; q.push({x,y}); map[x][y] = 0; d[x][y] = true; while(!q.empty()){ x = q.front().first; y = q.front().second; q.pop(); for(int i = 0; i < 4; i++){ int nx = ..