선형구조의 전체탐색은 앞에서 배운 대로 주로 반복문을 이용하여 접근할 수 있다. 1차 원 뿐만 아니라 2차원 이상의 다차원 구조에 대해서도 선형구조로 탐색할 수 있다.
비선형구조의 전체탐색은 문제해결의 가장 기본이 되는 알고리즘 설계법인 백트래킹이 다. 백트래킹 기법은 재귀함수를 이용하여 간단하게 구현할 수 있고, 다양한 문제를 해결하 는데 많이 응용되는 방법이므로 반드시 익혀둘 필요가 있다.
주어진 문제들을 통하여 선형구조, 비선형구조의 전체탐색법을 익힐 수 있도록 하자.
문제 1
약수의 합 구하기 1
한 정수 n을 입력받아서 n의 모든 약수의 합을 구하는 프로그램을 작성하시오.
예를 들어 10의 약수는 1, 2, 5, 10이므로 이 값들의 합인 18이 10의 약수의 합이 된다.
입력
첫 번째 줄에 정수 n이 입력된다.
(단, 1 <= n <= 100,000)
출력
n의 약수의 합을 출력한다.
입력 예 출력 예
10 18
풀이
이 문제는 기본적으로 수학적인 아이디어를 이용하여 해결할 수 있는 문제이지만 이 단 원에서는 전체탐색법을 다루는 단원이므로 전체탐색법으로 해결해보자.
일단 을 입력받으면 부터 까지의 모든 수를 차례로 반복문을 이용하여 선형으로 탐색하면서 의 약수들을 검사한다. 만약 현재 탐색 중인 수가 의 약수라면 누적하여 구 할 수 있다. 이렇게 구한다면 계산량은
이 된다. 이 문제에서는 의 최댓값이이므로 충분히 해결할 수 있는 문제가 된다.
어떤 수 가 의 약수라면 다음 조건을 이용해 구할 수 있다.
n % x == 0
이를 이용하여 문제를 해결한 소스코드는 다음과 같다.
줄 코드 참고
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
#include <stdio.h>
int n;
int solve() {
int ans = 0;
for(int i=1; i<=n; i++ ) if(n%i==0)
ans+=i;
return ans;
}
int main() {
scanf("%d", &n);
printf("%d\n", solve());
}
이 문제는 이와 같은 방법으로 쉽게 해결할 수 있으나, 이 10억 이상의 값으로 커질 때 는 다른 방법을 생각해야 한다. 나중에 다루게 될 것이므로 한 번 생각해보자.
문제 2
최댓값(L)
<그림 1>과 같이 9×9 격자판에 쓰여진 81개의 자연수가 주어질 때, 이들 중 최댓 값을 찾고 그 최댓값이 몇 행 몇 열에 위치한 수인지 구하는 프로그램을 작성하시오.
예를 들어, 다음과 같이 81개의 수가 주어질 경우에는 이들 중 최댓값은 90이고, 이 값은 5행 7열에 위치한다.
입력
첫째 줄부터 아홉째 줄까지 한 줄에 아홉 개씩 자연수가 주어진다. 주어지는 자연 수는 100보다 작다.
출력
첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 위치한 행 번호와 열 번호를 빈칸을 사이에 두고 차례로 출력한다. 최댓값이 두 개 이상인 경우 그 중 한 곳의 위치를 출력한다.
입력 예 출력 예
3 23 85 34 17 74 25 52 65 10 7 39 42 88 52 14 72 63 87 42 18 78 53 45 18 84 53 34 28 64 85 12 16 75 36 55 21 77 45 35 28 75 90 76 1 25 87 65 15 28 11 37 28 74 65 27 75 41 7 89 78 64 39 47 47 70 45 23 65 3 41 44 87 13 82 38 31 12 29 29 80
90 5 7
출처: 한국정보올림피아드(2007 지역예선 중고등부)
풀이
이 문제는 2차원 구조를 선형으로 모두 탐색하면 쉽게 해결할 수 있는 문제이다. 2차원 구조는 행 우선으로 탐색하는 방법과 열 우선으로 탐색하는 방법이 있는데, 이 문제는 어 떤 방법으로 탐색해도 관계없으며, 일반적으로는 행 우선 탐색을 많이 사용한다.
5행 4열의 2차원 배열 5행 4열의 2차원 배열
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 6 11 16 2 7 12 17 3 8 13 18 4 9 14 19 5 10 15 20
[2차원 구조에서의 행 우선 탐색 순서] [2차원 구조에서의 열 우선 탐색 순서]
다음은 행 우선을 반복문으로 구현한 소스코드이다.
줄 코드 참고
1 2 3 4 5 6
for(int row=0; row<5; row++) {
for(int col=0; col<4; col++) printf("[%d, %d]", row, col);
puts("");
}
다음은 열 우선을 반복문으로 구현한 소스코드이다.
줄 코드 참고
1 2 3 4 5 6
for(int col=0; col<4; col++) {
for(int row=0; row<5 ; row++) printf("[%d, %d]\n", row, col);
puts("");
}
[0, 0] [0, 1] [0, 2] [0, 3]
[1, 0] [1, 1] [1, 2] [1, 3]
[2, 0] [2, 1] [2, 2] [2, 3]
[3, 0] [3, 1] [3, 2] [3, 3]
[4, 0] [4, 1] [4, 2] [4, 3]
[0, 0] [1, 0] [2, 0] [3, 0] [4, 0]
[0, 1] [1, 1] [2, 1] [3, 1] [4, 1]
[0, 2] [1, 2] [2, 2] [3, 2] [4, 2]
[0, 3] [1, 3] [2, 3] [3, 3] [4, 3]
[2차원 구조에서의 행 우선 출력 결과] [2차원 구조에서의 열 우선 출력 결과]
이제 문제를 해결하는 방법에 대해서 알아보자.
탐색하기 전 먼저 해를 저장할 변수인 ans를 0으로 초기화한다. 여기서 주의할 점은 각 원소들 중 음수값이 존재할 경우 최댓값을 구하기 위해 ans를 0으로 초기화하면 안 된다는 점이다. 이 문제는 음수값이 존재하지 않기 때문에 ans를 0으로 초기화하고 문 제를 해결한다.
참고로 어떤 변수에 값을 초기화하는 몇 가지 방법을 소개한다. 일단 int형의 최댓값은 0x7fffffff(2,147,483,647)이며, 최솟값은 0x80000000(-2,147,483,648)이다. 엄밀하게 최 대, 최소를 지정할 때 이 값을 이용하면 되며, 16진법을 이용하면 쉽게 처리할 수 있다.
여기서 주의할 점은 위 값들을 설정한 후 값을 증가시키거나 감소시키면 오버플로 (overflow)로 인하여 답이 잘못될 수 있다. 예를 들어 다음 명령을 보자.
줄 코드 참고
1 2
int max = 0x7fffffff;
max = max + 1;
위 예의 경우에 max값이 최댓값이었는데, 여기서 1을 증가하면 오버플로가 발생하 여 max값은 음수가 된다. 따라서 이런 점을 방지하기 위하여 적어도 2배 정도라 하더 라도 오버플로가 발생하지 않도록 처리하는 경우가 많다. 이럴 때는 주로 최댓값을 987654321 등의 자릿수도 쉽게 알 수 있고 2배를 하더라도 정수 범위에 있는 수 등을 활용하는 경우가 많다. 문제에 따라서는 탐색하고자 하는 데이터 중에서 임의의 한 값 을 최댓값 또는 최솟값으로 결정하는 방법도 있다.
이러한 점들도 자신만의 코딩 스타일을 구성하는 요소가 되므로 자신만의 방식으로 최 대, 최소 등을 정하는 방법을 익혀두자. 위 문제를 해결하는 소스코드는 다음과 같다.
줄 코드 참고
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
#include <stdio.h>
int A[10][10], ans, mi, mj;
void input() {
for(int i=0; i<9; i++) for(int j=0; j<9; j++) scanf("%d", &A[i][j]);
}
int solve() {
for(int i=0; i<9; i++) for(int j=0; j<9 ; j++) if(ans < A[i][j]) {
ans=A[i][j];
mi=i+1;
mj=j+1;
} }
int main() {
input();
solve();
printf("%d\n%d %d\n", ans, mi, mj);
return 0;
}
가장 일반적으로 해결할 수 있는 방법이고 이 경우 계산량은
행×열이 된다. 이를 보다 효율적으로 바꾸기 위해서, 입력받으면서 바로 처리할 수도 있으며, ans, mi, mj를 모 두 쓰지 않고 mi, mj만 가지고 처리하는 방법을 소개한다.줄 코드 참고 1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
#include <stdio.h>
int A[10][10], mi, mj;
void input_solve() {
for(int i=0; i<9; i++) for(int j=0; j<9; j++) {
scanf("%d", &A[i][j]);
if(A[mi][mj]<A[i][j]) mi=i, mj=j;
} }
int main() {
input_solve();
printf("%d\n%d %d\n", A[mi][mj], mi+1, mj+1);
return 0;
}
이 방법도 잘 이해하고 익혀두면 코딩의 실수와 시간을 줄일 수 있다.
문제 3
삼각화단 만들기(S)
주어진 화단 둘레의 길이를 이용하여 삼각형 모양의 화단을 만들려고 한다. 이 때 만들어진 삼각형 화단 둘레의 길이는 반드시 주어진 화단 둘레의 길이와 같아야 한 다. 또한, 화단 둘레의 길이와 각 변의 길이는 자연수이다. 예를 들어, 만들고자 하는 화단 둘레의 길이가 9m라고 하면,
• 한 변의 길이가 1m, 두 변의 길이가 4m인 화단
• 한 변의 길이가 2m, 다른 변의 길이가 3m, 나머지 변의 길이가 4m인 화단 • 세 변의 길이가 모두 3m인 3가지 경우의 화단을 만들 수 있다.
화단 둘레의 길이를 입력받아서 만들 수 있는 서로 다른 화단의 수를 구하는 프로 그램을 작성하시오.
입력
화단의 길이 n이 주어진다.(단, 1 <= n <= 100)
출력
출력내용은 입력받은 n으로 만들 수 있는 서로 다른 화단의 수를 출력한다.
입력 예 출력 예
9 3
출처: 한국정보올림피아드(2002 전국본선 초등부)
풀이
이 문제는 입력구조로 볼 때, 전체탐색으로 해결하려면 선형구조인지 비선형구조인 지 등을 판단하기 쉽지 않다. 즉, 지금까지 다루었던 문제들보다 문제를 구조화하는 데 에 조금 더 어려움이 있는 문제라고 할 수 있다.
이 문제에서는 세 변의 길이의 합인 을 알고 있는 상태에서 삼각형의 세 변의 길이를 구하는 문제이므로 각 변을 라고 하면 변의 길이 의 길이를 1부터 까지 정하 고, , 도 같은 방법으로 순차적으로 정해나가는 방법으로 전체탐색을 할 수 있다. 이렇게 정할 경우 3차원 구조를 가지는 선형 구조가 된다.
여기서 주의할 점은 를 각각 부터 까지 탐색한다면 각 삼각형이 여러 번 중 복되어 구해진다. 예를 들어 화단의 길이가 일 때, 으로 골랐다면 와
등은 모두 같은 삼각형이지만 따로 카운팅하게 된다. 따라서 처음부터 를 가장 짧은 변, 를 가장 긴 변으로 정하면 문제 해결이 간단해진다.
그리고 이 문제의 입력 의 최댓값이 이므로 으로 접근하더라도 충분히 해결가 능하기 때문에 전체탐색법으로 해결해보자.
먼저 3차원 구조로 세변의 길이를 전체 탐색하는 구문을 작성해보자.
줄 코드 참고
1 2 3 4 5 6 7 8 9
int count=0;
for(int a=1; a<=n; a++) for(int b=a; b<=n; b++) for(int c=b; c<=n; c++) {
if(count%5 == 0) puts("");
count++;
printf("[%d %d %d]\t", a, b, c);
}
위 구조대로 탐색하면 각 변의 길이가 1부터 5까지의 모든 경우에 대해서 조사한다. 단 각 변의 길이를 라고 할 때, ≤ ≤ 를 만족하는 값들만 탐색한다. 위 탐색의 결과를 출력하면 다음과 같다. 출력할 때, 한 줄에 5개씩만 출력하도록 count변수를 활용
하였으므로 참고한다.
[1 1 1] [1 1 2] [1 1 3] [1 1 4] [1 1 5]
[1 2 2] [1 2 3] [1 2 4] [1 2 5] [1 3 3]
[1 3 4] [1 3 5] [1 4 4] [1 4 5] [1 5 5]
[2 2 2] [2 2 3] [2 2 4] [2 2 5] [2 3 3]
[2 3 4] [2 3 5] [2 4 4] [2 4 5] [2 5 5]
[3 3 3] [3 3 4] [3 3 5] [3 4 4] [3 4 5]
[3 5 5] [4 4 4] [4 4 5] [4 5 5] [5 5 5]
위와 같이 탐색을 하면 모든 경우에 대해서 탐색한다. 따라서 각 건에 대해서 삼각형 여 부만 판단하면 된다. 세 변의 길이로 삼각형을 판단하는 기본 조건은 다음과 같다.
그리고 이 문제에서만 적용되는 조건이 있다. 세 변의 길이의 합이 이어야 한다. 따라 서 다음 조건도 만족해야 한다.
위 탐색방법과 삼각형의 조건을 적용한 소스코드는 다음과 같다.
줄 코드 참고
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
#include <stdio.h>
int n;
int solve() {
int cnt = 0;
scanf("%d", &n);
for(int a=1; a<=n; a++) for(int b=a; b<=n; b++) for(int c=b; c<=n; c++ ) if(a+b+c == n && a+b>c) cnt++;
return cnt;
}
int main() {
printf("%d\n", solve());
9행~13행이 3차원으로 공간을 탐색해 나가는 과정이다. 이러한 문제와 같이 직접적으로 구조화되어 있지 않은 문제도 해결과정에서 구조화해가며 풀어야 하는 문제가 많다.
12행에서는 세 변의 길이의 합 조건과 삼각형을 이루는 조건을 검사한다.
이 문제는 비선형으로 구조화해서 해결할 수도 있다. 문제에서 주어진 조건들을 이용하 여 다음과 같은 탐색구조를 설계할 수 있다.
위 트리를 살펴보면 현재 상태(현재 세 변 길이의 합)가 이 n보다 적으면 (1), (2), (3)의 순으로 깊이우선탐색한다. 그러면 다시 (1), (2), (3)이 각각 새로운 현재 상태가 된다. 계속 깊이우선으로 탐색할 수 있는 상태가 된다.
만약 현재 상태가 n이 되면 탐색을 종료하고 삼각형의 조건이 맞는지 확인한다. a, b, c 세 변이 삼각형을 이루는 조건을 만족한다면 가능한 삼각형의 수를 1증가시킨다.
이렇게 모든 상태를 탐색하면 가능한 모든 경우가 만들어진다. 이를 구현한 소스코드는 다음과 같다.
줄 코드 참고
1 2 3 4 5 6 7 8 9
#include<stdio.h>
int cnt;
void solve(int n, int a, int b, int c) {
if(a+b+c==n) {
if(a<=b && b<=c && a+b>c) cnt++;
6: 모든 변을 다 썼으면
12: a변을 1증가 계속 탐색 13: b변을 1증가 계속 탐색 14: c변을 1증가 계속 탐색
줄 코드 참고 10
11 12 13 14 15 16 17 18 19 20 21 22 23
return;
}
solve(n, a+1, b, c);
solve(n, a, b+1, c);
solve(n, a, b, c+1);
}
int main(void) {
int n;
scanf("%d", &n);
solve(n, 1, 1, 1);
printf("%d\n", cnt);
}
하지만 위 소스코드에는 문제점이 있다. 각 변에 1씩 증가시켜가며 탐색해 나가는데 이 는 n이 5이고 최종 상태가 1, 2, 2라고 할 때, b변에서 1을 먼저 증가시켜 나온 1, 2, 2와 c변에서 1을 먼저 증가시켜 나온 1, 2, 2를 서로 다른 경우로 카운트한다. 즉, 같은 모양의 삼각형을 여러 번 중복해서 계산하게 된다.
이를 방지하기 위하여 한 번 삼각형으로 카운트 된 a, b, c에 대해서는 chk[a][b][c]배열 의 값을 1로 바꾸어 체크해둔다. 이 방법을 이용하여 카운트 하는 것을 방지할 수 있다.
위 방식으로 작성한 소스 프로그램은 아래와 같다.
줄 코드 참고
1 2 3 4 5 6 7 8 9 10 11 12
#include<stdio.h>
int cnt, chk[21][21][21];
void solve(int n, int a, int b, int c) {
if(a+b+c==n) {
if(a<=b && b<=c && a+b>c && chk[a][b][c]==0) {
cnt++;
chk[a][b][c]=1;
3: chk는 중복 체크용
7: 모든 변을 다 썼으면
9: 삼각형 조건 만족
12: 중복 방지용 체크
16: a변을 1증가 계속 탐색 17: b변을 1증 가 계속 탐색 18: c변을 1증가 계속 탐색