전체 글
-
1949. [모의 SW 역량테스트] 등산로 조성SWexpertAcademy 2019. 9. 5. 21:08
정말 많이틀렸다.. 틀린이유는 딱한가지였는데... BFS할땐 기똥차게잘하면서 왜 맨날 DFS나 백트래킹할때는 시작포인트를 체킹안하는질모르겠다.. #include #include #include using namespace std; int tc,n,m; int map[10][10]; bool d[10][10]; int ans = 0; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; bool check(int x, int y, int cnt) { for (int i = 0; i = 0 && nx = 0 && ny < n) { if (d[nx]..
-
스타트와 링크백준알고리즘 2019. 9. 5. 01:49
#include #include using namespace std; int n; int s[100][100]; int ans = 987654321; void go(vector& a, vector& b, int sum, int suma, int idx) { if (idx == n + 1) { if (a.size() == b.size()) { if (ans > abs(sum - suma)) { ans = abs(sum - suma); return; } else return; } else return; } int temp = 0; for (int i = 0; i < a.size(); i++) { temp += s[idx][a[i]]; temp += s[a[i]][idx]; } sum += temp; a.pu..
-
단어 뒤집기백준알고리즘 2019. 9. 5. 01:45
문제를 끝까지 읽어볼 필요가있고 예제 입출력을 한번더 볼필요가있었던문제, 내가 난독증이있는지는 모르겠지만, 그냥 처음에 문자를 아예거꾸로 뒤집는줄알았다. 그게아니여서 처음에 스택을 쓰다가 큐로바꿨고 굉장히 무난하게 푼 문자열문제 #include #include #include #include #include using namespace std; int main() { int n; cin >> n; queue x; string a; getline(cin, a); for (int i = 0; i < n; i++) { getline(cin, a); //cout
-
좋은수열백준알고리즘 2019. 9. 5. 01:44
백트래킹 문제로, 어려운 문제라기보단 귀찮은 문제가아닐까 싶었고, 확신이 쉽게들지않을문제. 첫번째, 일단 재귀를통해 수열을 만드는것은 string을 통해 쉽게 가능함 두번째, 바로앞에 중복되는 값을 수열로만드는건 굉장히 쉬움 세번째, 세번째부터 문제인데, 앞서 사용되있던 문자들과 중복체크하는것 이 굉장히 귀찮다. 하나하나 다해보기엔 시간복잡도가 터져버릴것같은문제, 전략을 세워보면, 딱 반크기만큼만 잘라서 보면된다 전체적으로 다검사해봐야하는것은 맞지만, 이어붙여나가는과정에서 이미 이어붙였던 것까지 한번에 검사할필요는 없다는얘기다. 문제를 풀어서 코드로 작성해보면다음과같다. #include #include #include #include using namespace std; vector a[80]; char..
-
숨바꼭질2백준알고리즘 2019. 9. 1. 23:55
전형적인 BFS 문제랑은 조금 다른문제다. 전에 풀었던, 숨바꼭질4는 트랙킹, 그리고 DSLR은 트랙킹이아닌 하면서 경로 같이쓰기 하지만 이문제는 경로에 관한 정보가아닌 경로의 가짓수를 물어본다. 경로의 가짓수는 잘알고있듯 , DP로 푸는게 빠른편인데, BFS를 해서 최소 가짓수를 구하고, 가짓수를 구하는 동안에 DP를 사용해서 가짓수도구할수있다. 사실 2차원배열문제였다면 많이 어려웠을거 같다는 생각이 들지만, 1차원이라 DP도 쓰기편했다. #include #include #include #include #include using namespace std; bool d[1000000]; int go[1000000]; int cnt[1000000]; int ans = 0; int su, little; vo..
-
로봇 청소기백준알고리즘 2019. 9. 1. 23:17
로봇 청소기 삼성 기출문제, 시뮬레이션문젠데 지난번에는 BFS써서 풀었었던 기억이있다. BFS말고, 그냥 문제에 주어진로직대로 풀어보는 방식을 사용해서 문제를 재구성했다. #include// using namespace std; struct robot {//0북1동 2남, 3서 int x = 0, y = 0, dir = 0, cnt = 1; robot(int x, int y, int dir) { this->x = x; this->y = y; this->dir = dir; } }; int dx[] = { -1,0,1,0 }; int dy[] = { 0,1,0,-1 }; robot rb = robot(0,0,0); int r, c, X, Y, D; int map[51][51]; bool dist[51][51..
-
레이저 통신백준알고리즘 2019. 9. 1. 23:12
BFS문제, 시뮬레이션으로도 풀수있을것 같긴한데, 그냥 끝까지가서 BFS 하면되는문제 까다로운점은 이제 한 직선내에서 모든점들에 대해 BFS를 하다보면, 중복되는지점(방문한 지점)에서 더 작은 값의대한처리는 어떻게 할지 이다. #include #include #include using namespace std; int r,c; char map[100][100]; int dist[100][100]; bool visit[100][100]; int dx[] ={0,0,1,-1}; int dy[] = {1,-1,0,0}; int ans = 0; void bfs(int x, int y){ queue q; visit[x][y] = true; q.push({x,y}); while(!q.empty()){ x= q.fr..
-
물통백준알고리즘 2019. 9. 1. 01:56
물통 A,B,C의 물의 양을 각각의 NODE라고 생각했고, 그리고 물을 옮기는 행위에 대한것을 따르거나, 따르지않거나 즉 따를때 1, 따르지 않을때 0의 가중치를 가지고있어서, BFS로 충분히 풀수있으리라고 생각했다. #include #include #include #include using namespace std; int x[201][201][201]; bool d[201][201][201]; int a, b, c; struct go{ int a, b, c; go(int a, int b, int c) { this->a = a; this->b = b; this->c = c; } }; vector zp; void bfs() { queue q; q.push(go(0, 0, c)); d[0][0][c] = ..