Kangho_Story

알고리즘 분류브루트포스백트래킹문제 설명N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.입력 설명첫째 줄에 N이 주어진다. (1 ≤ N 출력 설명첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.예제 입력8예제 출력92아이디어실제로 배열에 퀸의 위치를 기록하지 않고퀸이 놓여있는 열과 퀸이 놓여있는 좌표만 기록한다.그리고 하나의 행과 열에는 무조건 퀸이 한 개만 존재할 수 있으므로0행부터 n-1행까지 재귀적으로 내려가면서 같은 행과 같은 열 그리고 대각선 경로에 겹치는 퀸이 없는 자리에만 다음 퀸을 놓는다.모든 행에 겹치지 않게 퀸을 하나씩 놓았다면 경우의 수를 1 ..

5 51 2 3 4 55 4 3 2 12 3 4 5 66 5 4 3 21 2 1 2 1​알고리즘 분류구현브루트포스 알고리문제 설명폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.정사각형은 서로 겹치면 안 된다.도형은 모두 연결되어 있어야 한다.정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대..

99​210​알고리즘 분류수학브루트포스 알고리즘문제 설명어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 입력 설명첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다.출력 설명첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다.예제 입력11012101000500예제 출력991105144119아이디어각 자리의 숫자가 등차수열을 이루는지 확인해야 한다.우선 1자리뿐인 1~9는 모두 한수이다.또한 10~99는 각 자리의 숫자가 모두 등차수열을 이루므로 10~99도 모두 한수이다.n은 ..

알고리즘 분류다이나믹 프로그래밍브루트포 알고리즘문제 설명라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 1252 + 62 + 12 + 12라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 1052 + 152 + 82 + 52.자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현..

알고리즘 분류수학브루트포스 알고리즘정수론중국인의 나머지 정리문제 설명최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일 x 은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 로 표현되고, 11번째 해는 로 표현된다. 은 13번째..