이마닷의 블로그

0. 문제 https://www.acmicpc.net/problem/156834 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 1. 문제분석 - 주어진 사다리에서 추가로 가로줄을 그려서 사다리 타기의 시작점과 끝점이 모든 경우에 같도록 하는 경우를 찾는 문제이다. 최대 3개의 가로줄을 넣어보고, 그 때의 사다리 타기 결과가 조건을 만족하는 가로줄 개수의 최솟값을 구해야 하므로, 각각의 가로줄을 넣어보고 각 경우에 대해서 사다리 타기의 결과를 체크해 보아야 한다. 즉, 추가할 가로줄을 순차적으로 대입시켜보고,..

0. 문제 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 1. 문제분석 - 8개 이하의 cctv들이 만들어낼 수 있는 사각지대의 넓이를 구하기 위해서는, 각 cctv들이 감시할 수 있는 경우의 수를 모두 고려해 보아야 한다. 즉, 각 cctv들이 움직일 수 있는 경우의 수 대로 사각지대 넓이를 각각 구해보고 그 최솟값을 구해야 하므로, cctv들이 감시할 수 있는 영역을 순차적으로 대입시켜보고, 다시 원래 상태로 복구한 뒤에 새로운..

0. 문제 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 1. 문제분석 - 특정 위치에 1-9 중 하나의 숫자를 넣을 때에 스도쿠의 모든 조건을 만족하는지 여부를 판단해보아야 하고, 조건을 만족하는지 여부는 이전에 선택했던 결과들(현재 이전의 위치 중 비어있는 자리에 수를 넣은 것)이 영향을 미친다는 점에서 backtracking 방식으로 문제를 풀어야 함을 알 수 있다. - row[i][j], col[i][j], square[i][j]..

0. 문제 https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 문제분석 - 주어진 수들을 순차적으로 다르게 배열한 모든 경우의 수만 제시하면 되는 비교적 간단한 형태의 BackTracking 문제이다. 2. 주의할 점 - 꽤나 간단한 문제이기는 하지만, 꽤 많은 양을 출력해야 하므로 출력과 관련한 시간초과 문제를 조심해야 한다. - 기존에 사용하던 자료구조(스택, 큐, 그래프 등)를 구현한 라이브러리(LinkedList, ArrayL..

0. 문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 문제분석 - N개의 퀸을 체스판에 배치하는 모든 경우의 수에 대해 판단해야 하므로 Brute Force방식으로 각 좌표에 queen이 있는 상황을 다 따져보아야 한다. - N개의 queen이 있는 상황에 대해 조건 만족을 판단하기 위해 체스판을 설정한 뒤에는, 다시 또 다른 경우의 수를 판단하기 위해 체스판의 설정을 되돌려놓은 후 다른 경우의 수를 탐색해야 한다. 따라서 BackTracking 알..