공작소

도입 이 글은 모든 경우의 수를 찾는 상황에서 사용할 수 있는 백트래킹 (Backtracking) 에 대한 개념 설명을 담고 있습니다. 재귀를 배운 이후에 같이 배우면 좋은 이 백트래킹 알고리즘은 브루트포스와는 다르게, 여러 경우의 수를 조건에 맞게끔 깊게 구해낼 수 있습니다. 재귀를 사용하므로 코드도 간단하게 작성할 수 있어서, 익히게 된다면 재밌게 문제를 해결할 수 있다고 생각합니다. 입력 제한이 큰 경우에는 시간복잡도가 지수적으로 증가하는 백트래킹보다 그리디나 DP를 사용하는 것이 효율적이겠지만, 백트래킹만이 빠르게 문제 상황을 해결할 수 있는 상황도 존재합니다. 백트래킹의 기본 원리를 익히고 예제 문제와 함께 이해하는 것이 이 글의 목표입니다. 본 글은 C를 기반으로 작성되었습니다. 다음 알고리즘..

문제 사토르 마방진에 대해 들어본 적이 있는가? 사토르 마방진은 간단히 말하면 "가로로 읽었을 때와 세로로 읽었을 때 똑같이 읽히는 단어 집합"이다. 예시로는 다음과 같은 것들이 있다. 라팔아 팔렸니 아니오 호반우 반기는 우는나 술을 좋아하는 드립이는 전날 과음한 나머지 수학 수업 시간에 졸다가 선생님에게 걸려버렸고, 단어 집합들이 사토르 마방진인지 아닌지 판단해야 하는 숙제를 받았다. 하지만 N × N 크기의 큰 단어 집합이 사토르 마방진인지 눈으로 확인하는 것은 쉽지 않았다. 불쌍한 드립이는 숙제를 다 끝내기 전까지 집에 갈 수 없다. N × N 크기의 단어 집합이 주어지면, 주어진 단어 집합이 사토르 마방진인지 아닌지 판단하는 프로그램을 작성하자. 드립이를 도와주자! 입력 첫째 줄에 단어의 길이 N..

문제 다들 windows에서 지원하는 지뢰 찾기 게임을 한번쯤은 해 보았을 것이다. 특히 동호는 지뢰찾기의 매니아로 알려져 있다. 지뢰 찾기 map은 N*N의 정사각형 모양으로 각 칸에는 숫자가 들어가 있거나 지뢰가 들어가 있다. 빈 칸에는 숫자 0이 들어있다고 생각하자. map의 어떤 칸에 적혀 있는 숫자는, 그 칸과 인접해 있는 여덟 개의 칸 중에서 지뢰가 들어 있는 칸이 몇 개인지를 나타내 준다. 물론 인접한 칸이 map 내부에 있는 경우에 대해서만 생각하면 된다. 예제를 보면 더 잘 이해할 수 있을 것이다. 이번 문제는 조금 업그레이드 된 지뢰 찾기로, 한 칸에 한 개의 지뢰가 있는 것이 아니고, 한 칸에 여러 개(1 이상 9 이하)의 지뢰가 묻혀 있는 게임이다. 따라서 map의 어떤 칸에 적혀 ..

문제 평면에 네 개의 직사각형이 놓여 있는데 그 밑변은 모두 가로축에 평행하다. 이 네 개의 직사각형들은 서로 떨어져 있을 수도 있고, 겹쳐 있을 수도 있고, 하나가 다른 하나를 포함할 수도 있으며, 변이나 꼭짓점이 겹칠 수도 있다. 이 직사각형들이 차지하는 면적을 구하는 프로그램을 작성하시오. 입력 입력은 네 줄이며, 각 줄은 직사각형의 위치를 나타내는 네 개의 정수로 주어진다. 첫 번째와 두 번째의 정수는 사각형의 왼쪽 아래 꼭짓점의 x좌표, y좌표이고 세 번째와 네 번째의 정수는 사각형의 오른쪽 위 꼭짓점의 x좌표, y좌표이다. 모든 x좌표와 y좌표는 1이상이고 100이하인 정수이다. 출력 첫 줄에 네개의 직사각형이 차지하는 면적을 출력한다. 풀이 과정 색종이 (https://readytojoin...

문제 문장을 읽은 뒤, 줄의 첫 글자를 대문자로 바꾸는 프로그램을 작성하시오. 입력 첫째 줄에 줄의 수 N이 주어진다. 다음 N개의 줄에는 문장이 주어진다. 각 문장에 들어있는 글자의 수는 30을 넘지 않는다. 모든 줄의 첫 번째 글자는 알파벳이다. 출력 각 줄의 첫글자를 대문자로 바꾼뒤 출력한다. 풀이 과정 첫 글자가 소문자라면 대문자로 바꾸어 출력하고, 대문자라면 그대로 출력하면 되는 간단한 문제이다. C언어 환경에서는 N 을 입력받고 다음 줄을 입력받기 위해서의 "엔터"가 문장 입력에 들어갈 수 있으므로, getchar() 함수 등을 활용해 입력을 정상적으로 받는 것이 관건이다. C #include char str[35]; int main(void) { int n; scanf("%d", &n); g..

문제 2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다. 입력 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(1 ≤ i ≤ x ≤ N, 1 ≤ j ≤ y ≤ M). 출력 K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 2^31-1보다 작거나 같다. 풀이 과정 배열 데이터를..

문제 "OOXXOXXOOO"와 같은 OX퀴즈의 결과가 있다. O는 문제를 맞은 것이고, X는 문제를 틀린 것이다. 문제를 맞은 경우 그 문제의 점수는 그 문제까지 연속된 O의 개수가 된다. 예를 들어, 10번 문제의 점수는 3이 된다. "OOXXOXXOOO"의 점수는 1+2+0+0+1+0+0+1+2+3 = 10점이다. OX퀴즈의 결과가 주어졌을 때, 점수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 길이가 0보다 크고 80보다 작은 문자열이 주어진다. 문자열은 O와 X만으로 이루어져 있다. 출력 각 테스트 케이스마다 점수를 출력한다. 풀이 과정 O일 때 점수를 추가하는 것에서, 연속적인 O가 들어올 때마다 카운트하는 기능을..

문제 16진수 수를 입력받아서 10진수로 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 16진수 수가 주어진다. 이 수의 최대 길이는 6글자이다. 16진수 수는 0~9와 A~F로 이루어져 있고, A~F는 10~15를 뜻한다. 또, 이 수는 음이 아닌 정수이다. 출력 첫째 줄에 입력으로 주어진 16진수 수를 10진수로 변환해 출력한다. 풀이 과정 16진수 수를 10진수로 변환하는 방식을 사용하여 풀이한다. 우리가 일상생활에서 사용하는 10진수는 (뒤에서 1번째 자리) x 1 + (뒤에서 2번째 자리) x 10 + (뒤에서 3번째 자리) x 100 + (뒤에서 4번째 자리) x 1000 ... 인 것처럼, 16진수는 (뒤에서 1번째 자리) x 1 + (뒤에서 2번째 자리) x 16 + (뒤에서 3번째 자리..

문제 상근이는 친구들과 함께 SF영화를 찍으려고 한다. 이 영화는 외계 지형이 필요하다. 실제로 우주선을 타고 외계 행성에 가서 촬영을 할 수 없기 때문에, 컴퓨터 그래픽으로 CG처리를 하려고 한다. 외계 지형은 중앙 이동 알고리즘을 이용해서 만들려고 한다. 알고리즘을 시작하면서 상근이는 정사각형을 이루는 점 4개를 고른다. 그 후에는 다음과 같은 과정을 거쳐서 지형을 만든다. 정사각형의 각 변의 중앙에 점을 하나 추가한다. 정사각형의 중심에 점을 하나 추가한다. 초기 상태에서 위와 같은 과정을 한 번 거치면 총 4개의 정사각형이 새로 생긴다. 이와 같은 과정을 상근이가 만족할 때 까지 계속한다. 상근이는 어떤 점은 한 개 보다 많은 정사각형에 포함될 수 있다는 사실을 알았다. 메모리 소모량을 줄이기 위..

문제 당신은 어떤 물건이라도 20% 할인해주는 쿠폰을 가지고 있다. 원래 가격이 주어질 때, 쿠폰을 사용하면 얼마가 되는지 알려주는 프로그램을 작성하시오. 입력 첫 번째 줄에 테스트케이스의 수가 주어진다. 각 줄에는 물건의 원래가격이 소수점 둘째자리까지 주어진다. 출력 할인된 가격을 달러 단위로 출력한다. 나누어떨어지지 않을 때는 소수점 셋째 자리에서 반올림해서 둘째 자리까지 출력한다. 풀이 과정 원가를 입력받고 20% 할인된 가격을 구하기 위해 원가*0.8 을 한 값을 소수점 둘째 자리까지 출력한다. C #include int main(void) { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { double now; scanf("%lf", &now); ..