이지코딩

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)을 설정하고, 각 횟수가 늘어나는 거리의 분기 (분기거리)에 따른 식을 만들었다. 그에 따라 일단 ..

https://www.acmicpc.net/problem/15953 15953번: 상금 헌터 첫 번째 줄에 제이지가 상상력을 발휘하여 가정한 횟수 T(1 ≤ T ≤ 1,000)가 주어진다. 다음 T개 줄에는 한 줄에 하나씩 제이지가 해본 가정에 대한 정보가 주어진다. 각 줄에는 두 개의 음이 아닌 정수 a(0 ≤ a ≤ 100)와 b(0 ≤ b ≤ 64)가 공백 하나를 사이로 두고 주어진다. www.acmicpc.net 문제가 길어서 문제 이미지는 생략하고..... 카카오 2018 코드페스티벌 예선 1번 문제다. 이 문제처럼 '등수'에 따라 값이 달라지는 문제는 개인적으로 array에 미리 집어넣어 배열에 접근하는 방시깅 제일 빠른것 같다. 또한, 함수에 들어오는 파라미터가 들어오자마자 간단한 조건식을 ..