기록보관소

마인크래프트 문제는 지형을 평탄화할 수 있는 모든 경우를 고려하여 계산하는 문제이다. 평탄화된 지형의 최소 높이는 0, 최대 높이는 지면의 블록 개수와 인벤토리에 있는 블록 개수를 면적으로 나눈 값이다. 이 두 값 사이의 값을 높이로 가지기 위해 블록을 부수거나 쌓아야 하는 데 이때 가장 시간이 적게 걸리는 높이를 찾으면 된다. 작성한 코드는 다음과 같다. #include int N, M, B; int land[520][520]; int sum = 0; int time; int min=987654321; int height; int main(void) { scanf("%d %d %d", &N, &M, &B); for (int i = 0; i < N; i++) { for (int j = 0; j < M; ..

스타트와 링크 문제는 N명의 사람들을 두 집합으로 나누고 각 집합별로 능력치 합을 구하여 가장 적은 집합 간의 능력치 합의 차를 출력하는 문제입니다. 집합을 나누는 데 모든 가능한 경우의 수를 탐색하기 위해 백트래킹 기법을 사용하였습니다. 이때 주의해야 할 점은 자칫 똑같은 집합을 두 번 중복하여 계산할 수 있다는 점입니다. A집합에 있는 원소들이 그대로 B집합에 있는 상황입니다. 이러한 불필요한 연산을 방지하기 위해서는 어느 특정한 원소를 특정한 집합에만 존재한다고 미리 가정하여야 합니다. 예로 들어서 1을 기준으로 둘 때 모든 경우는 1을 포함한 집합과 포함하지 않는 집합으로 이루어져 있다는 것을 확인할 수 있습니다. 이때 1이 A집합에만 존재한다고 가정하면 똑같은 원소의 종류로 분할된 상황에서 B집..

연산자 끼워넣기 문제는 BOJ 14888번 문제이자 삼성 SW 역량 테스트 기출문제입니다. 가능한 모든 연산자의 순열을 찾기 위해서 백트래킹 기법을 활용하여 완전 탐색을 하는 것이 문제의 핵심입니다. 아래의 풀이에서는 연산자 배열을 정의한 후 0번 인덱스부터 N-2번 인덱스까지 순서대로 4가지 연산자를 채우며 가능한 모든 연산자 수열을 찾는 백트래킹 함수를 설계하였습니다. 문제를 풀면서 느낀 부분은 백트래킹 함수를 통해 완전 탐색을 할 때는 모든 경우를 일정한 기준에 따라 빠짐없이 분류할 수 있다면 문제를 쉽게 할 수 있다는 점입니다. 추가적인 팁으로 int형 변수에서 max와 min의 초기값을 설정할 때 간단하게 987654321, -987654321로 대입하면 int형의 최대, 최소 수의 범위를 기억..

이번 문제는 스도쿠를 푸는 문제입니다. 스도쿠의 규칙에 위배되지 않도록 빈칸을 적절하게 채움으로써 간단하게 문제를 해결할 수 있었습니다. 스도쿠의 빈칸을 채우기 위해 모든 경우를 탐색하는 백트래킹 기법을 사용하였습니다. 빈 칸의 좌표를 저장한 후 빈 칸의 개수만큼의 높이를 가진 트리를 탐색하는 재귀함수를 통해 백트래킹을 구현하였습니다. 재귀함수를 한번씩 통과할 때마다 빈 칸이 한 개씩 채워지며 모든 빈 칸이 채워지면 스도쿠를 출력하도록 하였습니다. 문제에서 제약조건으로 c언어의 경우 80ms 내에 처리하도록 하였으며, 작성한 코드는 76ms에 스도쿠를 처리할 수 있었습니다. 백트래킹을 빠르게 실행하기 위해서는 필요없는 경우를 무시하는 가지치기가 필요합니다. 재귀 함수에서 스도쿠를 출력하자 마자 프로그램이..

이 문제는 N*N 체스판에서 N개의 퀸을 놓을 수 있는 경우를 계산하는 아주 유명한 문제이다. 이 문제를 풀기 위해 N개의 퀸을 놓는 경우를 모두 조사하는 방식으로 진행하였고 따라서 백트래킹 기법을 사용하였다. 백트래킹은 트리 형태로 모든 경우를 탐색하는 기법이므로 재귀함수의 형태로 구현할 수 있고 재귀 함수의 탈출 조건에 문제에서 원하는 답을 얻기 위한 마지막 처리를 추가하는 식으로 코드를 작성할 수 있었습니다. N*N 체스판을 배열로 선언하여 직접 퀸을 체스판에 배치하고 퀸의 이동가능방향에 다른 퀸이 존재하는 지 확인하는 방식으로 문제를 해결할 수 있지만 이번에는 배열 사용을 줄이는 방향으로 코드를 작성해보았습니다. 가로, 세로, 대각선 방향으로 오직 1개의 퀸만이 놓일 수 있다는 사실에서 아이디어를..