전체 글
-
DSLR백준알고리즘 2019. 9. 1. 00:43
BFS 문제, 사실 처음봤을때 스페셜저지에 이것저것 고려해보니 괴랄한문제라고 생각이많이들었던건데 마음을 조금진정시키고 차분히 읽어보자. 일단 전체적인 숫자의 길이 수가 4개뿐이며, 그 숫자의 크기가 10000을 넘을수없다. D일때 2씩 곱해나가면서 만이 넘어갈경우, 나머지를 지정하고 S는 1씩 감소, L은 왼쪽방향으로 숫자이동 R은 오른쪽방향으로 숫자이동 이 각각의 경우의 수들이 전부 가치가 1씩 이라는점이다.->BFS로 풀수있다. 하지만, 문제를보면 최소 경로의 지나온 횟수를 물어보는 문제가아니다. 횟수가 아닌, 목표지점까지 오게된 경로를 구하는것이다,. 어떻게보면 숨바꼭질4와 비슷하다 생각이됬고 그에 따라 최소경로 구한뒤 -> 트랙킹을했다. #include #include #include #inclu..
-
숨바꼭질4백준알고리즘 2019. 8. 31. 11:19
BFS로 문제를풀긴했는데, 사실 시간자체를구하는건 너무나도쉽다. 하지만, 문제가되는건 과정을 어떻게 알수있을지 가 관건이였던문제 나같은경우는 진행해 나가면서 +1했는지 -1했는지, *2했는지를 배열하나를 더써서 표식을 남겼고, 끝지점에서 트래킹 해나가면서 벡터를 채우는방식으로 문제를 풀었다. #include #include #include using namespace std; int su; bool d[300001]; int dist[300001]; int c[300001]; int little; vector visit; int ans; void bfs(int x) { queue q; q.push(x); d[x] = true; dist[x] = 0; while (!q.empty()) { x = q.fro..
-
합이 0인 네 정수백준알고리즘 2019. 8. 31. 11:14
음.. 문제보면서 가장간단하게 푸는방법은 아무래도 그냥 4중포문 돌리는게 제일 쉽겠지만, 배열의 크기가 4000에, 이걸 4승한다면... 시간제한 2초는 당연히 날거같아서, 그냥 2중포문 + 2중포문으로 나눠서 하는게 좋겠다고 생각이들었다. #include #include #include #include #include using namespace std; int main() { int n; scanf("%d", &n); vector a(n); vector b(n); vector c(n); vector d(n); for (int i = 0; i < n; i++) { scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]); } vector first, second; for ..
-
말이 되고픈 원숭이백준알고리즘 2019. 8. 31. 11:09
좀 전형적이지 않은 BFS문제 사실 처음에 DFS로 풀었는데, 시간초과가 날거같아서 방향을 회선했다.(DFS로 할경우 코드 수는 매우 줄지만, 해당문제의 시간제한 + 예상 가짓수를 보면 절대로 DFS를 해선안된다) 먼저 DFS코드를보자 #include #include #include using namespace std; int k, r, c; int map[200][200]; bool d[200][200]; int ck[200][200]; pair sp; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; int hx[] = { -2,-1,-2,-1,1,2,2,1 }; int hy[] = { -1,-2,1,2,-2,-1,1,2 }; int ans = 100000; v..
-
양백준알고리즘 2019. 8. 29. 00:30
#include #include #include #include using namespace std; int r, c; int map[250][250]; bool d[250][250]; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; int wolf; int lambs; void bfs(int x, int y) { queue q; q.push({ x,y }); d[x][y] = true; int wolv = 0; int lamb = 0; if (map[x][y] == 2) wolv++; if (map[x][y] == 1) lamb++; while (!q.empty()) { x = q.front().first; y = q.front().second; q.pop();..
-
뱀백준알고리즘 2019. 8. 29. 00:03
예전 삼성전자 코딩역량테스트 문제라고한다. 시뮬레이션 문제고 솔직히, 문제 난이도 자체는 어렵지않았지만, 디버깅부분에서 애를 많이먹었고, 문제가 직관적으로 이해가 잘안된부분, 그리고 게임이 끝나는 부분에 대한 확인 미숙 등이 문제를 어렵게 느끼게 했던것같다. 알고리즘에 대한 생각은 시뮬레이션 문제이며, 뱀 자체를 벡터로 표현했는데, 헤드 부분이 벡터 0번째 인덱스며, 사과를 먹었을때 비활성화 벡터로 놓고 문제를 풀었다. #include #include #include #include #include using namespace std; struct sn { int x, y; int dir = 0; bool life = false; }; int n; int map[102][102]; int an; int ..
-
토마토백준알고리즘 2019. 8. 27. 22:19
예전에 풀었던 그냥 한판짜리 토마토가 기억이났는데, 비슷하지만 조금다르다. 차원이 하나가 더 늘어난 문제, 하지만 풀어보면서 느낀건 로직자체가 변화했거나 하진않았다는것이고, 이를통해서 충분히 BFS로 풀수있었다. #include #include #include #include #include #include #include using namespace std; struct tdi { int x, y, z; }; int n, m, h; int map[100][100][100]; int d[100][100][100]; bool dist[100][100][100];//필요한지 안필요한지 모르겠음 지금은 int dx[] = { 0,0,1,-1,0,0 }; int dy[] = { 1,-1,0,0,0,0 }; in..
-
백조의 호수백준알고리즘 2019. 8. 27. 22:15
백조의 호수문제 사실 여태까지 문제를 풀면서 재귀를 쓰는게 아니고서야, 메모리초과나 스택오버플로우를 걱정해본적은없는데, 이건 코드짜면짤수록 메모리가 엄청나게 신경쓰였다. 또한 문제를 잘읽어야하는 이유중의 한가지는 바로 백조가있는곳 역시 물이기때문에 이곳과 접촉해있는 얼음도 녹는다는것이다. 혹시나 논증의 여지가있다면, 문제 어디에도 백조가 절대로 다른백조를 만나지 못한다는 조건이 없다는것이다. 인접한 물이녹는다거나 이런류의 문제를 보면 딱떠오르는게 BFS인데, 초기로직은 다음과같다 #include #include #include #include #include #include #include using namespace std; int r, c; int map[1500][1500]; bool d[1500]..