https://www.acmicpc.net/problem/15685 드래곤 커브 1) 문제드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다. 시작 점 시작 방향 세대 0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다...
https://www.acmicpc.net/problem/14503 로봇 청소기 1) 문제로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 방은 N x M 크기의 직사각형으로 나타낼 수 있으며, 1 x 1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (r, c)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0, 0), 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N-1, M-1)이다. 즉, 좌표 (r, c)는 북쪽에서 (r+1)번째에 있는 줄의 서쪽에서 (c+1)번째 칸을 가리킨다. 처음에 빈..
https://www.acmicpc.net/problem/9663 N-Queen 1) 문제N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.입력: 첫째 줄에 N이 주어진다. (1 ≤ N 출력: 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 2) 예시예제입력 1:8예제출력 1: 92 3) 풀이 * 핵심 조건1. 퀸은 가로, 세로, 대각선으로 이동 가능2. 즉, 서로 같은 행, 열, 대각선에 두면 안 됨3. 퀸 N개를 서로 공격하지 않도록 한 개씩 배치 * 아이디어핵심 전략: 백트래킹 + 한 줄씩 퀸 배치 1. 행 단위로 한 줄씩 퀸을 배..
https://www.acmicpc.net/problem/1182 부분수열의 합 1) 문제N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.입력: 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.출력: 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. 2) 예시예제입력 1:5 0-7 -3 -2 5 8예제출력 1: 1 3) 풀이* 아이디어1. 모든 부분수열을 탐색해야 하므로 → 부분집합 문제 → 각 원소..
https://www.acmicpc.net/problem/15650 N과 M (2) 1) 문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다.입력: 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)출력: 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다. 2) 예시예제입력 1:3 1예제출력 1: 123예제입력 2:4 2예제출력 2:1 21 31 42 12 32 43 13 23 44 14 2..
https://www.acmicpc.net/problem/15649 N과 M (1) 1) 문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열입력: 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)출력: 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다. 2) 예시예제입력 1:3 1예제출력 1: 123예제입력 2:4 2예제출력 2:1 21 31 42 12 32 43 13 23 44 14 24 3예제입력 3:4 4예제출력 3..