글쓰는공대생의 IT블로그

출처 => [알고리즘 해결을 위한 창의적 알고리즘 해결 (중급)] 문제 문제 분석 문제의 의도: 단순 비선형 탐색이 아니라, 두더지 굴을 나타내는 숫자인 1을 중심으로 상,하,좌, 우에 1이 있다면 이 부분에 간선이 있는 것으로 생각한다. (0,0)에서 순차 탐색을 하여 그 값이 1이라면 그 점을 중심으로 깊이우선탐색을 하여 모든 연결된 점을 방문한다. 풀이 이런 식으로 마지막 칸까지 진행을 한다면 다음과 같은 결과가 나온다. => 따라서 각 굴의 크기는 7, 8, 9라는 사실을 알 수 있다. 소스코드 & 결과 #include #include using namespace std; int n, A[101][101], cnt, Size[101]; void input() { cin >> n; for (int ..

문제 출처입니다. https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 사고의 흐름 2x1 타일링을 할 때부터 차례대로 하여 규칙을 찾아내보록 한다. 그 결과, 2x1일때는 1, 2x2 일때는 2, 2x3 일때는 3, 2x4 일때는 5, 2x5 일대는 8이라는 결과가 나온다. 그런데 2x5 타일링을 분석하면 다음 그림과 같다. 즉, 5번째 타일링은 3번째와 4번째 타일링을 더한 값이다. 즉 피보나치 수열로 나타낼 수가 있다. 해결방법 1 2 3 4 5 6 7 8 9 10..

문제 출저 입니다. https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 사고의 흐름 일단 규칙성을 찾기 위해 1부터 15까지의 경우의 수를 찾아 보았다. 모든 경우의 수를 찾고 그 중 횟수의 최솟값을 찾는 방법을 사용하였더니 가지 치기 방법과 관련하여 고민하였다. 하지만 가지치기로 생각을 하니 숫자가 점점 더 커지면 경우의 수는 기하급수적으로 늘어났다. 즉 틀린 방법이었다. 다른 방법을 고민하다가 규칙성을 발견하였다. 예를 들면 6은 6>>2>>1이 최솟값인데 12를 보면 12>>6>>2>>1이 최솟값이기 때문이다. 즉, 6이 반복됨을 발견할 수 있었다. 해결방..

문제 출저 입니다. https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 사고의 흐름 일단 규칙성을 찾기 위해 1부터 15까지의 경우의 수를 찾아 보았다. 모든 경우의 수를 찾고 그 중 횟수의 최솟값을 찾는 방법을 사용하였더니 가지 치기 방법과 관련하여 고민하였다. 하지만 가지치기로 생각을 하니 숫자가 점점 더 커지면 경우의 수는 기하급수적으로 늘어났다. 즉 틀린 방법이었다. 다른 방법을 고민하다가 규칙성을 발견하였다. 예를 들면 6은 6>>2>>1이 최솟값인데 12를 보면 12>>6>>2>>1이 최솟값이기 때문이다. 즉, 6이 반복됨을 발견할 수 있었다. 해결방..