Algorithm

[백준 1799번] 비숍 (C/C++)

https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 비숍은 N-Queen 문제와 유사합니다. 비숍은 대각선으로 공격할 수 있기 때문에 배치된 비숍의 대각선으로는 다른 비숍을 배치할 수 없습니다. 따라서 백트래킹 기법을 이용하여 각 대각선마다 하나의 비숍을 배치시키면서 가능한 경우의 수를 모두 수행해봄으로써 체스판 위에 배치할 수 있는 비숍의 개수를 계산할 수 있습니다. (저는 우상향 대각선을 이용하였습니다.) n이 5일 때, 대각선의 개수는 9개입니다. 즉..

[백준 18809번] Gaaaaaaaaaarden (C/C++)

https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net 알고리즘의 전체 틀은 아래와 같습니다. 초록색 배양액을 뿌릴 땅과, 빨간색 배양액을 뿌릴 땅을 선택하는 모든 경우의 수를 계산합니다. 같은 색의 배양액을 선택할 때, 배양액을 선택하는 순서는 상관없기 때문에 초록색 배양액을 선택하는 경우의 수와 빨간색 배양액을 선택하는 경우의 수는 따로 계산되어야 합니다. (배양액 땅의 개수) C (초록색..

[백준 1941번] 소문난 칠공주 (C/C++)

https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 처음에는 백트래킹으로 풀어보려 했지만, 칠공주의 자리 배치가 여러 갈래로 나누어질 수 있기 때문에, 조합과 BFS를 사용했습니다. 알고리즘의 기본 틀은 아래와 같습니다. next_permutation을 사용해 순서를 고려하지 않고 25개 중 7개의 좌표를 선택합니다. bfs를 이용해 선택된 좌표들이 서로 이어져있는지 확인합니다. 이어져 있다면, 'S'의 개수를 count하고, 4개 이상이라면 경우의 ..

[백준 15655번] N과 M (9) (C/C++)

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이번 문제는 전체 수열에 같은 값이 있을 때, 임의의 수열에 같은 수가 여러번 나올 수 있도록 하면서, 수열은 중복되지 않도록 하는 것이 핵심인 문제입니다. 14와 17번째 라인이 핵심 코드입니다. 먼저, th번째 숫자를 선택할 때 vector에 저장합니다. 34번째 라인에서 전체 수열을 오름차순으로 정렬했기 때문에, 다음 수열을 결정할 때 vector의 back()을 확인해서 현재 선택하려는..

[백준 1182번] 부분수열의 합 (C/C++)

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 부분 수열을 선택하기 위해서 길이가 1 ~ n까지의 부분 수열을 모두 뽑았습니다. 하지만, n의 최대 값이 20이기 때문에 순서가 다른 수열까지 모두 뽑을 경우 시간초과가 발생합니다. 아래 풀이의 핵심은 17번째 라인입니다. i의 초기값이 r로 시작하고, 재귀 함수 호출 시 i + 1을 전달함으로써 다음 선택할 숫자를 이전에 선택한 숫자 다음 인덱스부터 확인함으..

[백준 9663번] N-Queen (C/C++)

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 본 포스트는 BaaakingDog님의 [바킹독의 실전 알고리즘] 0x0C강 - 백트래킹을 참고하여 작성하였습니다. 퀸의 움직임은 아래 이미지와 같습니다. 처음엔 상태를 저장하는 2차원 배열을 사용해서 퀸이 이동할 수 있는 부분에는 true를 저장함으로써 백트래킹을 사용했습니다. 이 풀이의 경우 퀸을 놓는 순서까지 고려하기 때문에 factorial(n)으로 나눈 값을 출력하도록 했습니다. 하지만, n의 최대 값은 ..

[백준 2448번] 별 찍기 - 11 (C/C++)

https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 개행 때문에 고민이 필요했던 문제였습니다. 개행은 배열을 이용하여 해결하였습니다. 재귀 시작 전 배열을 공백 문자로 채워주고, 각각의 재귀는 맡은 범위에 삼각형 형태의 별을 저장해주면 됩니다. 재귀 함수 탈출 조건은 가장 작은 삼각형을 기준으로 작성하였습니다. 우측 하단의 꼭짓점과 좌측 하단의 꼭짓점의 y좌표 차이가 4이면 가장 작은 삼각형이므로, 재귀 함수의 입력으로 받은 세 꼭짓점을 기준으로 삼각형 형태의 별을 저장해줍니다. * * * *****..