이지코딩

미로에서 끝까지 연결되어있는 길을 찾아내는것은 DFS, BFS 모두 가능하지만, 최단 거리를 찾아낼때는 BFS를 사용해야 한다. (DFS가 구현하기 편해서 그렇게 하다가 안되는걸 직접 알았기 때문에 알게 됬당....) DFS로 이 문제를 풀기 힘든 이유는, 처음 선택하게 되는 길로 계속 탐색을 하기 때문이다. 이렇게 탐색을 할 경우에 선택한 길이 가장 최단경로 라는 보장이 없기 때문에 여러 복잡한 조건들을 달아야 하게 될것이다. (경험담..) BFS로 풀면 쉬운 이유는 같은 계층이 즉 같은 거리가 되기 때문이다. 아래 지도를 예제로 들어보자. BFS를 (1,1)에서 시작하면, 네방면으로 같은 계층이므로 같기 때문에 인접한 부분의 거리는 아래와 같다. 이렇게 된다면, 거리가 멀어지더라도 같은 거리(계층)을..

2차원 배열에서 연결되어있는 숫자 1 끼리의 묶음을 찾는 문제이다. 연결되어있는 숫자들을 찾기 위해서는 BFS 또는 DFS를 사용한다. 이 문제의 경우에는 묶음의 갯수와 각 묶음안의 원소 갯수를 찾는 문제이다. 이렇게 입력이 붙어있을 경우에는 getchar()를 사용하면 편리하다. 하지만 getchar의 경우 엔터를 입력으로 인식하기 때문에 버퍼에 엔터가 남아있어 입력시 원하는대로 동작하지 않을 수 도 있다. 이를 위해 엔터가 들어가는 부분마다 getchar를 넣어줘야 한다. 2차원 배열에서 연결된 묶을을 찾기 위해서는, 이전 글에서 사용한 DFS와 비슷하지만, 체크해서 넘어가야 하는 방향이 위,아래,오른쪽,왼쪽으로 4방향이다. if 문을 사용하여 모든 방향을 고려해야 한다. 이런 경우에는 경계 부분을 ..

DFS를 가장 기본적으로 사용하는 알고리즘 문제였다. 전 글에서 사용했던 dfs 를 그대로 사용하여 풀었다. >> DFS BFS 설명 바로가기 BOJ 1260번 : DFS와 BFS 다른 문제를 풀다가 DFS구현에서 계속 문제가 발생해서 초심으로 돌아가고자 DFS와 BFS를 복습...할겸 풀었다. 역시나 자주 사용하지 않던 알고리즘이라 그런지 구현 방식부터 틀렸었더라..... 공부하자 공부! n; cin >> m; for (int i = 0; i > a >> b; arr[a][b] = arr[b][a] = 1; } dfs(1); cout

다른 문제를 풀다가 DFS구현에서 계속 문제가 발생해서 초심으로 돌아가고자 DFS와 BFS를 복습...할겸 풀었다. 역시나 자주 사용하지 않던 알고리즘이라 그런지 구현 방식부터 틀렸었더라..... 공부하자 공부! 위 그림을 바탕으로 DFS, BFS 의 개념을 보자. DFS (Depth First Search)는 깊이 우선 탐색 이다. 가장 깊은 노드 를 우선으로 탐색하는 방식으로, 탐색 순서는 아래와 같다. BFS (Breadth First Search)는 넓이 우선 탐색 이다. 깊은곳이 아니라 같은 계층에 있는 노드을 먼저 탐색하는 방식으로, 탐색 순서는 아래와 같다. 탐색 주체로부터 가장 가까운 노드부터 방문하게 되므로 "최소" 비용, "최단" 거리등의 문제는 bfs를 사용할 확률이 높다. 이제 각 ..

손풀기 문제로 풀었다. 기본적인 dp문제였고, 경우의 수를 물어보았으니, dp안에 들어가는 원소는 경우의 수가 될것 이라고 예상하고 풀면 되는 문제였다. 또한, 표를 한번 그려보면 어렵지 않게 규칙을 찾을 수 있다. N과 M에 대해 표를 그려보면 아래와 같다. 위와 위의 왼쪽 원소의 합이 자신의 값이 되는것을 알 수 있다. 즉, 아래의 점화식 표현이 가능하다. dp[m][n] = dp[m-1][n-1] + dp[m-1][n] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include using namespace std; void Solve() { int t, n, m; cin >> t; for (int x = 0; x > n >> m; for (int..

오랜만에 골드 문제! 처음에 만들었던 수식이 완벽한줄 알았지만.. 3번쯤 틀리고서야 수식이 잘못 됬다는걸 알았다. 열심히 공부하자... ㅠㅜ 게다가 MOD 를 출력하는 건지 몰라서 2번쯤 또 틀렸다..헤헤... 문제좀 끝까지 읽자.... ㅠ 경우의 수를 잘 따져야 하는 문제이다. 이 문제의 경우, 한 사람을 기준으로 두고 생각하면 편하다. 6명일 경우를 예시로 들어보자. 이 그림의 경우에서 6을 기준으로 보자. 6의 위치에서 악수가 가능한 사람은 1,3,5번 이다. 6과 1이 연결 되었을 경우에는 (2,3,4,5)가 각각 악수할 경우인 4명이 완전한 악수를 할 수 있는 경우의 수와 같다. 6과 3이 연결 되었을 경우에는 (1,2), (4,5)가 각각 연결된 경우인 2명이 완전한 악수를 할 수 있는 경우의..

카카오 코드페스티벌 2018 예선 B번 문제이다. 수식만 구현 하면 되겠네~! 라고 생각하고 덤볐다가 꽤나 틀렸다.. 하하.... 첫번째로 틀린 이유는 오차범위가 10^-6 인것을 생각하지 않고 풀었던것...과 두번째는 K범위의 최소값을 생각하지 않고 코드를 구성한 것이였다. 시간복잡도만 생각하고 풀었다가 랭크만 갉아먹어 버렸지 뭐얌... 빠끄.... 기본적으로 산술평균, 분산, 표준편차를 함수로 구현해서 함수를 콜 하는 방식을 사용했고, 메인문에서 범위를 모두탐색 하는 방식을 사용했다. 또한, cout 을 사용하여 소수점 자리수를 강제적으로 고정시키려면 setprecision()을 사용해야한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ..

실버 1 문제라고 겁도 없이 건들였다가 어머어마하게 시간을 뺏겨 버렸다... 규칙을 찾기가 너무 어려웠고, 규칙을 찾은것 같아도, 식으로 풀어내는 과정이 너무 어려웠다. 기본적으로, 한 단계마다 속력의 변화가 ±1 이고, 출발과 도착시에 1의 속도를 맞춰야 하기에 무조건 속도를 증가시킬수는 없다. 따라서 속도를 증가시키다 감소 시켜야 한다. 처음에는 간단한 수식 한줄로 해결될줄 알았으나, 변수를 어떻게 설정하느냐의 문제였던 것 같다. 규칙을 찾기 위해 각 거리마다 최소 이동횟수를 적어보았다. 여기서 이동 횟수가 늘어나는 분기의 규칙성이 있는것같아 이동 횟수(n)에 연관된 변수 (An)을 설정하고, 각 횟수가 늘어나는 거리의 분기 (분기거리)에 따른 식을 만들었다. 그에 따라 일단 ..