선형구조와 탐색(Linear Structure and Search)

선형구조의 탐색

선형구조란 자료의 순서를 유일하게 결정할 수 있는 형태의 구조를 말한다. $i$번째 자료 를 탐색한 다음, $i+1$번째로 탐색 해야할 자료가 유일한 형태를 의미한다. 2차원, 3차원 구조라도 순서가 일정하게 정해져 있으면 이는 선형이라고 할 수 있다.

선형구조는 주로 배열과 리스트의 형태로 저장된다. 일반적으로 1차원 배열에 자료를 저장하는 1차원 선형구조와 2차원 이상의 배열에 자료가 저장이 되어있는 다차원 선형구조로 나눌 수 있다.

선형구조의 탐색은 선형구조로 저장된 자료들 중에서 원하는 것을 찾는 작업을 말한다. 선형구조를 탐색하는 방법은 기본적으로 순차탐색과 이분탐색이 있고, 이들을 적절히 응용한 탐색법도 만들어 사용할 수 있다. 이 단원에서는 순차탐색과 이분탐색을 익히고 이를 통하여 간단한 문제를 해결하는 실습을 한다.

순차탐색

순차탐색은 자료의 특성에 관계없이 사용할 수 있는 일반적인 방법으로 전체탐색기법의 한 방법이다. 첫 번째 원소로부터 시작하여 한 원소씩 차례로 다음 원소를 탐색해 나가는 방법으로 자료가 $n$개 있을 때의 계산량은 $O(n)$이다.

탐색 순서를 그림으로 나타내면 다음과 같다.

다음은 선형탐색을 구현한 소스코드이다.

public class LinearSearch {
    public static boolean linearSearch(int S[], int k){
        for (int i = 0; i < S.length; i++) {
            if (S[i] == k)
                return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int S[] = {5, 2, 6, 2, 1, 8};
        int k = 4;
        System.out.print(linearSearch(S, k));
    }
}

이분탐색

이분탐색은 배열에서 중간 원소를 선택하여 찾는 값과 비교하고 중간 원소의 값이 찾는 값보다 작다면 중간 원소를 기준으로 오른쪽을 탐색, 중간 원소의 값이 찾는 값보다 크다면 중간 원소를 기준으로 왼쪽을 탐색하는 기법이다. 이 알고리즘은 오름차순이나 내림차순으로 정렬된 선형구조에서 원하는 원소를 찾는 것으로 계산량은 $O(log_2n)$이다.

이분탐색의 탐색순서(원은 처음 접근하는 원소이고, 사각형은 찾은 곳의 값이 찾으려는 값보다 작으면 찾는 위치, 둥근 사각형은 그 값의 반대조건일 경우에 탐색하는 위치이다. 조건의 결과에 따라 왼쪽 또는 오른쪽 중 하나를 탐색하게 된다.)

다음은 이분탐색을 구현한 C++ 소스코드이다.
$S$에 $n$개의 원소를 입력받고, 그 중에 $k$가 있는지를 찾는 알고리즘이다.

// 이분탐색 - 반복
#include <stdio.h>
int S[100], n, k;
int find(int s, int e) {
  while(s<=e) {  // s가 e보다 작거나 같을 때 까지
    int m=(s+e)/2; // 중간 원소
    if(S[m]==k) return m; // 찾았다

    // 탐색한 원소가 찾고자 하는 원소 보다 크다
    //탐색한 원소의 왼쪽 배열 탐색
    if(S[m]>k) e=m‐1; 
    // 탐색한 원소가 찾고자 하는 원소 보다 작다
    //탐색한 원소의 오른쪽 배열 탐색
    else s=m+1;
  }
  return ‐1; // 원하는 원소를 찾지 못했다.
}
int main() {
  scanf("%d%d", &n, &k);
  for(int i=0; i<n; i++ )
    scanf("%d", &S[i]); 
  printf("%d\n", find(0, n‐1));
  return 0;
}

---

다음은 재귀로 이분탐색을 구현한 java 소스코드이다.

// 이분탐색 - 재귀
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BinarySearchRecur {
    private static int S[] = new int[100];
    private static int n, k; // 배열 크기, 찾고자 하는 원소

    public static int find(int s, int e){
        if (s > e) // 원하는 원소를 찾지 못했다
            return -1;
        int m = (s+e)/2; // 중간 원소
        if (S[m] == k) // 찾았다
            return m;
        else if (S[m] < k) // 탐색한 원소가 찾고자 하는 원소 보다 작다
            return find(m+1, e); //탐색한 원소의 오른쪽 배열 탐색
        else               // 탐색한 원소가 찾고자 하는 원소 보다 크다
            return find(s, m-1); //탐색한 원소의 왼쪽 배열 탐색
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()); // n, k
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine()); // S array
        Arrays.sort(S);
        for (int i = 0; i < n; i++) {
            S[i] = Integer.parseInt(st.nextToken());
        }
        System.out.print(find(0, n-1)); // index 반환
    }
}

/* 
Test Case
-----------
input
5 19
3 4 2 19 4

output
3
-----------
input
5 10
3 4 2 19 4

output
-1

*/

---

기본적인 탐색방법을 익힐 수 있는 다음 문제들을 해결해보자.

최댓값

9개의 서로 다른 자연수가 주어질 때, 이들 중 최댓값을 찾고 
그 값이 몇 번째 수 인지를 구하는 프로그램을 작성하시오.

예를 들어, 서로 다른 9개의 자연수가 각각
3, 29, 38, 12, 57, 74, 40, 85, 61 라면, 

이 중 최댓값은 85이고, 이 값은 8번째 수이다.

----------------------------------------

입력
첫째 줄부터 아홉째 줄까지 한 줄에 하나의 자연수가 주어진다. 
주어지는 자연수 는 100보다 작다.

출력
첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 
몇 번째 수인지를 출력한다.

입력 예      출력 예
3          85
29         8
38
12
57
74 
40 
85 
61

이 문제는 자료를 1차원 배열에 저장한 후 반복문을 이용하여 전체탐색법을 구현하면 쉽게 구할 수 있다. 전체탐색을 하더라도 탐색해야할 자료의 수가 9개뿐이므로 충분히 빠른 시간 내에 해를 구할 수 있는 기본적인 문제이다.

따라서 반복문을 구현하는 연습을 할 수 있는 문제로 이 문제를 해결하는 방법이 다른 문제들을 해결하는 도구로 많이 활용될 수 있으므로 꼭 익혀둘 수 있도록 한다.

일단 먼저 문제해결 아이디어를 생각하자. 최종적으로 출력할 해를 변수 ans로 두고, 최댓값의 인덱스를 저장할 변수를 index로 설정한다.

먼저 모든 자료를 탐색하기 전에 ans를 모든 원소들 보다 작은 값으로 설정한다. 이 문제에서는 100 이하의 자연수가 데이터의 정의역이므로, 0으로 설정하면 된다. 다음 으로 첫 번째 자료부터 마지막 자료까지 하나씩 검사해가며 현재까지 ans보다 더 큰 값이 나타나면 ans를 갱신하고, index값도 갱신한다.

마지막 자료까지 탐색을 마치면, ans와 index를 출력하면 된다. 이 과정을 입출력 예를 통해서 알아보자.

이와 같이 배열을 선형으로 전체탐색을 하면서 최댓값을 구할 수 있다. 이 방법은 가장 기본적인 방법 중 하나로 다른 알고리즘에 많이 응용되는 방법이다.

이를 프로그램으로 구현하면 다음과 같다.

#include <stdio.h> 
#define MAXN 9
int ans, A[MAXN+1];

void solve(void) {
  for(int i=1; i<10; i++) {
    scanf("%d", A+i);
    if(A[ans]<A[i]) ans=i; 
  }
}
int main() {
  solve();
  printf("%d\n%d\n", A[ans], ans);
  return 0;
}

ans, index를 하나의 변수 ans로 처리하고 있다. 그리고 9행에서 입력 받을 때 “&A[i]” 대신 “A+i”를 활용하고 있다. 이러한 코딩 스타일도 자주 활용되는 방법으로 배열과 포인터를 이해하면 위와 같이 사용할 수 있음을 알 수 있다. 이와 같을 때에는 특수문자로 인한 오타의 확률도 줄일 수 있으므로 다양한 방법을 익힐 수 있도록 하자.

3의 배수 게임

3의 배수 게임을 하던 정올이는 3의 배수 게임에서 잦은 실수로 
계속해서 벌칙을 받게 되었다.
3의 배수 게임의 왕이 되기 위한 마스터 프로그램을 작성해 보자.

** 3의 배수 게임이란?

여러 사람이 순서를 정해 순서대로 수를 부르는 게임이다.
만약 3의 배수를 불러야 하는 상황이라면, 그 수 대신 "박수" 를 친다.

----------------------------------------------

입력
첫 째 줄에 하나의 정수 n이 입력된다(n은 10000미만의 자연수이다.).
출력
1부터 그 수까지 순서대로 공백을 두고 수를 출력하는데, 
3 또는 6 또는 9인 경우 그 수 대신 영문 대문자 X 를 출력한다.

입력 예      출력 예
7          1 2 X 4 5 X 7

이 문제도 앞선 문제와 마찬가지로 단순히 반복문을 이용하여 전체탐색법으로 해결할 수 있다. 단지 이 문제는 특정 값을 찾거나 하는 것이 아니라 전체 데이터를 읽으면서 특정 자료가 있으면 변경한다는 점은 다르나 전반적으로 같은 방법으로 해결할 수 있다. 이 문제에서 특정 자료란 입력된 숫자가 3의 배수일 경우를 말한다.

임의의 변수 n이 3의 배수인지 판정하는 가장 일반적인 방법은 다음과 같은 방법을 이용한다.

n % 3 == 0

1부터 n까지 1씩 증가하여 탐색하면서 각 수가 3의 배수인지 판정하여 3의 배수이면 “X”를 아니면 그 수를 출력하도록 작성하면 쉽게 해결할 수 있다.

이 문제를 해결한 예시는 다음과 같다.

#include <stdio.h> 
int n;
void solve(void) {
  for(int i=1; i<=n; i++) {
    if(i%3==0) printf("X ");
    else printf("%d ", i);
  }
}
int main() {
  scanf("%d", &n); s
  solve();
  return 0;
}

linear structure search

n개로 이루어진 정수 집합에서 원하는 수의 위치를 찾으시오.

단, 입력되는 집합은 오름차순으로 정렬되어 있으며, 같은 수는 없다.

-------------------------------------------

입력
첫 줄에 한 정수 n이 입력된다.
둘째 줄에 n개의 정수가 공백으로 구분되어 입력된다.
셋째 줄에는 찾고자 하는 수가 입력된다.
(단, 2 <= n <= 1,000,000,
각 원소의 크기는 100,000,000을 넘지 않는다.)

출력
찾고자 하는 원소의 위치를 출력한다. 없으면 -1을 출력한다.

입력 예                       출력 예
8                          
1 2 3 5 7 9 11 15 11        7
11

3
2 5 7                       -1
3               

이 문제는 앞에서 다룬 이분탐색의 예제 프로그램을 거의 그대로 활용할 수 있는 문제이다.

이분탐색으로 풀어보자.

이분탐색 알고리즘

배열을 A라고 할 때, A[m] == k 인 경우와 A[m] > k, A[m] < k인 경우로 나누어 처리 하는 방법으로 문제를 해결할 수 있다.

탐색 범위를 [s, e]로 정한 다음, 이분탐색을 진행한다. (이분탐색 - 반복)

1. s <= e를 만족할 때까지(만족하지 않으면 3번으로 간다), 가운데 위치의 값을 m( (s+e)/2 )으로 설정하고 탐색 진행.
2. A[m] == k인 경우, 찾았으므로 위치를 반환한다. (예제에서는 m+1)
   A[m] > k인 경우, 가운데 위치의 값이 찾고자 하는 값보다 크므로 탐색 범위를[s, m-1]로 하여 다시 이분탐색(1번으로 간다)
   A[m] < k인 경우, 가운데 위치의 값이 찾고자 하는 값보다 작으므로 탐색 범위를[m+1, e]로 하여 다시 이분탐색(1번으로 간다)
3. s > e인 경우, 원하는 값이 없으므로 -1을 반환한다.

그림과 함께 자세한 과정을 보자.

위 방법을 소스코드로 작성하면 다음과 같다.

#include <stdio.h>
int n, k, A[1000001]; 
int solve(int s, int e) {
  int m; 
  while(s<=e) {
    m=(s+e)/2; 
    if(A[m]==k)
      return m+1; 
    if(A[m]<k) s=m+1; 
    else e=m‐1;
  }
  return ‐1;
}
int main() {
  scanf("%d",&n); 
  for(int i=0; i<n; i++ )
    scanf("%d", A+i); 
  scanf("%d",&k); 
  printf("%d\n", solve(0, n‐1)); 
  return 0;
}

위 소스코드를 다음과 같은 재귀함수로도 만들 수 있다. 재귀함수는 매우 다양한 응용이 가능하므로 이해해두면 많은 도움이 된다.

#include <stdio.h>
int n, k, A[1000001]; 
int solve(int s, int e) {
  if(s>e) 
    return ‐1;
  int m=(s+e)/2; 
  if(A[m]==k)
    return m+1; 
  if(A[m]<k)
    return solve(m+1, e); 
  else
    return solve(s, m‐1);
}
int main() {
  scanf("%d",&n); 
  for(int i=0; i<n; i++ )
    scanf("%d", A+i); 
  scanf("%d",&k); 
  printf("%d\n", solve(0, n‐1)); 
  return 0;
}

References

• 문제해결을 위한 창의적 알고리즘