1. 다룰 소재
어제까지의 나가 오늘의 나를 결정한다.
이번 게시글에서는 모두가 경험한 피신때의 소재를 활용해서 알고리즘적으로 생각해보는 계기로 삼고자 합니다. (마침 7기도 들어오니, 복습 겸)
오늘의 나는 어제까지의 나에 의해 결정되듯이, 어떤 동작을 수행할때 이전까지의 모든 동작을 고려해야하는것에 대한 고찰이 목적입니다.
사용할 문제는 아래 2가지 입니다.
•
C00_ex05: ft_print_comb
•
C05_ex08: The Ten Queens
먼저 The Ten Queens 문제를 먼저 살펴보고, 이해를 돕기 위해 ft_print_comb 문제를 활용할 예정입니다.
2. The Ten Queens
필요한 문제 요소만 살펴보면
•
10X10 체스판에서 퀸 10개가 갈 수 있는 모든 위치를 표시하고 모든 가능한 수의
숫자를 반환하는 함수를 작성하세요.
•
단, 각 퀸은 1번 움직여서 다른 퀸을 잡을 수 없습니다.
•
프로토타입: int ft_ten_queens_puzzle(void);
가장 먼저 떠올릴 수 있는 문제 해결 방법은 무엇일까요?
2.1 Brute Force로 들이박기
•
사실 적절한 예시는 아니지만….. 그냥 이게 가장 먼저 떠올랐다…..
•
Brute Force는 모든 경우의 수를 탐색하는 알고리즘이다.
•
마찬가지로 100개의 칸에 10개의 퀸을 놓을 수 있는 모든 조합에 대한 결과를 더하면 결과를 얻을 수 있다.
그래도 이건 좀 아닌거 같다. 좀 더 효율적인 방법을 떠올려 보자.
2.2 백트래킹 적용하기
백트래킹은 가능성이 없는 탐색은 하지 않음으로 좀 더 효율적인 결과 도출을 가능하게 한다.
그렇다면 백트래킹을 자연스레 도입할 수 있도록, 규칙을 찾아보자.
2.2.1 하나의 줄에는 하나의 퀸만을 놓을 수 있고 놓아야만 한다.
우선 퀸은 좌우 & 상하 & 대각선으로 움직일 수 있다.
어느 줄(row)에 하나의 퀸을 놓아보자. 퀸은 좌우로 이동이 가능하다. 그래서 어느 줄(row)에 하나의 퀸이 이미 놓였다면, 그 줄(row)의 다른 열(col)에는 더 이상 퀸을 놓을 수 없다.
또한 N개의 줄(row)에 N개의 퀸을 놓아야하기 때문에, 각 줄(row)에 퀸을 하나씩 놓아야만 한다.
비슷한 논리로 열(col)과 두 대각선에 대해서도 아래와 같이 정리할 수 있다.
•
하나의 열에는 하나의 퀸만을 놓을 수 있고 놓아야만 한다.
•
하나의 \ 대각선에는 하나의 퀸만을 놓을 수 있고 놓아야만 한다.
•
하나의 / 대각선에는 하나의 퀸만을 놓을 수 있고 놓아야만 한다.
2.2.2 내가 (row, col)에 퀸을 놓게 된다면
•
row 줄에는 더이상 퀸을 놓을 수 없다.
•
col 열에는 더 이상 퀸을 놓을 수 없다.
•
해당하는 \ 대각선에는 더 이상 퀸을 놓을 수 없다.
•
해당하는 / 대각선에는 더 이상 퀸을 놓을 수 없다.
즉.
2.2.3 이전의 행동(row, col)에 퀸을 놓기으로 인해 다음 행동에 제약사항이 생긴다.
어떤 동작을 수행할때 이전까지의 모든 동작을 고려해야하는 것을 의미 한다.
여기서 잠깐, 어쩌면 그냥 지나쳤을 문제를 다시 보며, 그 문제 역시 어떤 동작을 수행할때 이전까지의 모든 동작을 고려해야했던 문제였을을 상기해보자.
3. ft_print_comb
•
세 개의 서로 다른 숫자를 오름차순의 순서로 여러 가지로 조합한 세 자릿수 숫자를 오름차순으로 표시하는 함수를 작성하세요.
•
프로토타입: void ft_print_comb(void);
아마 해당 알고리즘을 구현한 코드는 모두 비슷하게 3개의 중첩된 반복문을 활용한 구현일 것입니다.
가독성을 위해 당시엔 금지된 for와 printf를 도입한 코드로 표현해보면
void ft_print_comb(void)
{
for (int n1 = 0; n1 <= 9; n1++)
for (int n2 = n1 + 1; n2 <= 9; n2++)
for (int n3 = n2 + 1; n3 <= 9; n3++)
printf("%d%d%d ", n1, n2, n3);
}
C
복사
그런데 왜 이렇게 구현하셨나요?
문제는 분명
세 개의 서로 다른 숫자를 오름차순의 순서로 여러 가지로 조합한 세 자릿수 숫자를 오름차순으로 표시하는 함수를 작성하세요.
간단하게 생각하면, 문제의 요구를 딱 알맞게 충족하는 알고리즘이기 때문입니다.
문제에서 주어진 아래의 예시를 통해, 규칙을 발견하고 해당 알고리즘으로 문제를 해결할 수 있을것이란 통찰을 얻었기 때문일 것입니다.
실제로 코딩테스트에서 주어지는 이미지 예시들의 목적은 참가자들의 문제 이해를 돕는것입니다. 즉 잘 이용합시다!
어떤 동작을 수행할때 이전까지의 모든 동작을 고려하는 것에 초점을 맞춰서 문제를 다시 한 번 살펴봅시다.
큰 자리의 숫자부터 결정하는 관점에서 바라봅시다.
먼저 숫자의 조합이 결정되었을때, 해당 조합으로 가장 작은 숫자를 만들기 위해서 큰 자리의 숫자 < 작은 자리의 숫자 여야만 합니다.
1.
n1 < n2 and n2 < n3
그리고 가장 작은 숫자부터 만들기 위해 n1에 0부터 사용합니다.
2.
n1의 초깃값 = 0
가장 작은 숫자를 만들기 위해 n2에는 n1이 사용한 0을 제외한 가장 작은 숫자 1을 사용합니다.
가장 작은 숫자를 만들기 위해 n3에는 n1과 n2가 사용한 0, 1을 제외한 가장 작은 숫자 2를 사용합니다.
즉 직전 자릿수보다 하나 더 큰 수부터 사용하는것을 알 수 있습니다.
3.
int n2 = n1 + 1; && int n3 = n2 + 1;
그렇게 가장 작은 숫자 012 를 출력합니다.
그 다음으로 가장 작은 숫자만으로 구성된 조합은 0, 1, 3 입니다.
n3만 3으로 바뀌어 013 을 출력하면 되는 것을 확인할 수 있습니다.
이렇게 n3를 1개씩 증가시켜 019까지 출력하면 됩니다.
4.
for (int n3 = n2 + 1; n3 <= 9; n3++;)
다음으로 작은 숫자는 023 인 것을 눈치채실 수 있고, 마찬가지로 n3를 1개씩 증가시켜 029 까지 출력하면 됩니다.
5.
for (int n2 = n1 + 1; n2 <= 9; n2++;)
각 자릿수를 출력하는 재귀함수 void print_n_k(int prev_num, int k)로 표현하면
#include <stdio.h>
static int _arr[3];
void print_n_k(int prev_num, int k)
{
for (int n = prev_num + 1; n <= 9; n++)
{
_arr[k] = n;
if (k == 2)
printf("%d%d%d ", _arr[0], _arr[1], _arr[2]);
else
print_n_k(n, k + 1);
}
}
int main(void)
{
print_n_k(-1, 0);
}
C
복사
마치 체스에서 이전에 놓았던 퀸의 위치에 따라 해당 row & col & \ & / 에 놓을 수 없게 되는 제약사항이 생겼던것 처럼 직전에 출력 상위 자릿수의 값 prev_num보다 큰 숫자를 출력해야하는 제약사항이 생긴다.
4. 다시 The Ten Queens
다시 한 번 문제에 대해 정리해보면
•
목적: N x N 필드에 N개의 Queen을 놓는 것.
•
퀸 하나를 (row, col)에 놓았을때, 해당하는 행 & 열 & 2개의 대각선에는 더 이상 퀸을 놓을 수 없다.
⇒ 현재 이전까지 누적된 행동들로 인해, 현재의 행동에 제약사항이 생긴다.
따라서 위를 활용해 알고리즘을 구현한다고 하면
•
row || col을 기준으로
•
현재 이전까지 누적된 퀸들의 제약사항을 업데이트하고
◦
행
◦
열
◦
대각선 /
◦
대각선 \
•
제약사항을 만족하는 퀸 중에서 하나씩 선택하여
•
총 N개의 퀸이 놓였을때가 하나의 정답
설명의 흐름이 원할하지 않았지만…. 다시 한번 이번 게시글에서 말하고자 했던것은 딱 하나입니다.
현재 이전까지 누적된 행동들로 인해, 현재의 행동에 제약사항이 생긴다.
다음 게시글에서는 2022 KAKAO BLIND RECRUITMENT에 나왔던 양궁대회 문제에
같은 시각으로 접근하여 풀이해 보겠습니다.
