작심 24/7

9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹의 대표적인 문제이다. 이차원 배열을 만들 필요 없이 일차원 배열로 인덱스는 행, 값은 열을 넣어주어 풀 수 있다. 퀸이 배치될 수 있는 조건은 1. 같은 행에 있지 않을 때 2. 같은 열에 있지 않을 때 3. 같은 대각선 상에 있지 않을 때 이다. 1번의 경우는 queen이라는 일차원 배열을 만듦으로써 행이 겹칠 수가 없게 된다. 2번과 3번의 경우는 인덱스 0부터 현재 행 전까지 돌아가는 for문을 끝까지 돌면서 현재 위치가 queen을 놓을 수 있는 조건인 경우 다..

15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N개 중에 중복 포함, 순서 상관없이 M개를 뽑는 중복 조합 문제이다. 앞의 값보다 크거나 같은 값일 경우에만 벡터에 넣어주고 카운트가 M일 때 출력해주면 된다. #include #include using namespace std; vector v; int cnt = 0; void multiCombination(int N, int M, int start) { if (cnt == M) { for (int i = 0; i < v.size(); i..

15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N개 중에 중복 포함, 순서를 고려하여 M개를 뽑는 중복 순열 문제이다. 순열과 다른 점은 중복을 체크해줄 필요 없기 때문에 check배열만 없애면 된다. 자바는 Scanner + print 써서 그냥 제출하니까 시간 초과 나길래 Scanner 대신 BufferedReader를 썼더니 또 시간 초과됐다 (자바 싫어) 찾아보니 print가 시간이 꽤 오래 걸린다 하더라 그래서 출력 부분을 StringBuilder로 넣어준 뒤 마지막에 한 번만 출력시켰더니 통과 <..

15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N개 중에 중복 미 포함, 순서 상관없이 M개를 뽑는 조합 문제이다. 이번엔 check 배열이 필요 없다. 앞의 값보다 큰 값일 경우에만 벡터에 넣어주고 카운트가 M일 때 출력해주면 된다. #include #include using namespace std; vector v; int cnt = 0; void combination(int N, int M, int start) { if (cnt == M) { for (int i = 0; i < v..

15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N개 중에 중복 미 포함, 순서를 고려하여 M개를 뽑는 순열 문제이다. 바로바로 출력을 할 수 없기 때문에 벡터를 만들어 값을 저장하고 빼주면서 출력해준다. 대충 이런 식으로 돌아가는 구성이다. #include #include using namespace std; vector v; int check[10] = { 0 }; int cnt = 0; void permutation(int N, int M) { if (cnt == M) { for (i..

11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 기둥이 A, B, C이고 N이 2개일 때부터 4개일 때까지 순서를 적어나가보면 B에 N-1개의 원반을 쌓아놓은 후 C에 다 옮기는 방식이 공통적으로 나온다. 즉, ​ 1. A -> B 로 N-1개 옮김 2. A -> C 로 1개 옮김 (가장 큰 원반) 3. B -> C 로 N-1개 옮김 ​ 이렇게 세 번의 과정으로 나눌 수 있다. 이걸 그대로 재귀함수에 갖다 넣으면 해결된다. #include #include using namespace std; voi..

2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 � www.acmicpc.net 분할 정복 알고리즘 문제라 한다. 분할 정복법이란 문제를 나눌 수 없을 때까지 나누어서 각각을 풀고 다시 합병하는 방법인데 N이 27이면 그림처럼 27X27 -> 9X9 -> 3X3 -> 1X1까지 분할시킬 수 있다. 언제가 공백인지가 관건인데 저런 식으로 공백인 좌표들을 모아 두고 규칙성을 찾아보니 N이 27인 경우엔 좌표를 9, 3, 1로 나눈 값에 %3을 한 값이 1일 때 즉, i/N/3%3, i/N/3/3%3, i/N/3/3..