기록보관소

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

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

이번 문제는 중복조합으로 생성된 수열 중 비내림차순에 해당하는 수열만 출력하는 문제입니다. N과 M(3) 문제와 비슷한 코드를 사용하며 다른 점은 M 길이의 수열을 출력하기 전 해당 수열이 비내림차순인지 확인하는 과정을 거친다는 점입니다. N과 M(3)에 대한 설명은 아래 글에 있습니다. 2021.06.21 - [알고리즘] - [BOJ 15651번] N과 M (3) [BOJ 15651번] N과 M (3) 2021.06.21 - [알고리즘] - [BOJ 15649번] N과 M (1) [BOJ 15649번] N과 M (1) 15649번은 백트래킹 기법으로 해결할 수 있는 문제입니다. 백트래킹은 모든 경우를 탐색하는 기법으로 보통 재귀함수를 이용하여 구 ark-hive.tistory.com 작성한 코드는 다음..

2021.06.21 - [알고리즘] - [BOJ 15649번] N과 M (1) [BOJ 15649번] N과 M (1) 15649번은 백트래킹 기법으로 해결할 수 있는 문제입니다. 백트래킹은 모든 경우를 탐색하는 기법으로 보통 재귀함수를 이용하여 구현합니다. 재귀함수로 구현할 때는 함수 내에서 동일한 함수 ark-hive.tistory.com 2021.06.21 - [알고리즘] - [BOJ 15650번] N과 M (2) [BOJ 15650번] N과 M (2) 이번 문제는 BOJ 15649번 N과 M(1)과 동일한 문제입니다. 다만, 오름차순의 수열만을 출력해야하므로 재귀함수의 탈출조건에서 수열을 출력하기 전에 수열이 오름차순으로 정렬되어 있는지 확인하 ark-hive.tistory.com 이번 문제는 N과..

이번 문제는 BOJ 15649번 N과 M(1)과 동일한 문제입니다. 다만, 오름차순의 수열만을 출력해야하므로 재귀함수의 탈출조건에서 수열을 출력하기 전에 수열이 오름차순으로 정렬되어 있는지 확인하는 과정을 추가하여야 합니다. BOJ 15649번에 대한 설명은 하단의 링크에서 확인부탁드립니다. https://ark-hive.tistory.com/14 작성한 코드는 다음과 같습니다. #include int N, M; int sequence[10]; int check[10]; //back tracking은 모든 경우를 탐색할 때 사용하는 기법입니다. //기능 특성상 재귀함수 형태로 구현됩니다. void final_process(){ for (int i = 0; i < M-1; i++) { printf("%d ..

15649번은 백트래킹 기법으로 해결할 수 있는 문제입니다. 백트래킹은 모든 경우를 탐색하는 기법으로 보통 재귀함수를 이용하여 구현합니다. 재귀함수로 구현할 때는 함수 내에서 동일한 함수를 활용하여 부분 문제를 풀 수 있도록 작성하여야 합니다. 공통적으로 재귀함수는 탈출조건과 호출부로 나누어지게 됩니다. 해당 문제에서는 탈출조건은 depth가 M일 때이며 이때 탐색한 수열을 출력하고 재귀함수를 종료하게 됩니다. 작성한 코드는 다음과 같습니다. #include int N, M; int sequence[10]; int check[10]; //back tracking은 모든 경우를 탐색할 때 사용하는 기법입니다. //기능 특성상 재귀함수 형태로 구현됩니다. void final_process() { for (i..