[알고리즘] 정보과학과 문제, 선형구조의 탐색

프로그래밍 언어를 활용해 해결 가능한, 정보과학의 문제 이해와 기본적인 문제 해결 방법인 선형탐색 방법을 이해를 목표로 본 포스팅을 작성합니다.

1. 정보과학과 문제

---

정보과학에서 다루어지는 문제? 계산문제(computational problem)

계산 가능한 문제	계산 불가능한 문제
1. N이하의 자연 수 중 짝수의 갯수는?  2. 폐구간 [a, b]에서 소수는 존재하는가?  3. N개의 원소를 가지는 집한 S의 원소를 오름차순으로 나열하고, 그 최댓값을 구하시오.  4. N개의 원소로 이루어진 집합의 부분집합들 중 그 원소의 합이 k인 부분집합이 존재하는가?  5. 좌표평면 상에 N개의 점의 한 점에서 출발하여 모든 점을 지나고 출발점으로 돌아오는 경로의 길이 중 가장 짧은 길이는 얼마인가?	1. 우리반 학생들 중 키가 큰 학생은 몇명인가?  2. 주어진 음식들 중 맛있는 순서로 나열하시오.  3. 대한민국에서 축구를 잘하는 사람은 모두 몇 명인가?  4. 임의로 한 명을 골랐을때, 그 사람이 요리를 잘 할 확률은 얼마인가?

- 결정문제(decision problem): 결정문제는 예 또는 아니오 중 하나의 답을 얻는 문제

  ex) 폐구간 [a, b]에서 소수는 존재하는가?
       N개의 원소로 이루어진 집합의 부분집합들 중 그 원소의 합이 k인 부분집합이 존재하는가?

- 탐색문제(search problem)

- 카운팅문제(counting problem)

- 최적화문제(optimization problem): 계산결과로 얻어낸 가능한 후보 해들 중에서 가장 좋은 해를 찾는 문제, 보통 올림피아드 문제에서는 결정문제 하나만 나오는 경우는 없으나, 난이도가 있는 최적화 문제에 결정문제를 혼합하여 문제가 출제되는 경우가 존재

  ex) n개의 원소를 가지는 집합 S의 원소를 오름차순으로 나열하고, 그 최댓값을 구하시오.

       좌표평면 상에 N개의 점 중 한 점에서 출발하여 모든 점을 지나고 출발점으로 돌아오는 경로의 길이 중 가장 짧은 길이는 얼마인가?

- 함수형문제(function problem)

2. 탐색

---

어떤 상황에서 어떤 데이터나 값을 얻어내는 문제로써 가장 간단한 상황은 연결된 선형데이터들을 순서대로 탐색하면서 확인하는 방법이 있습니다.

탐색기반 알고리즘 설계방법: 문제를 탐색 가능한 형태로 구조화한 후 체계적으로 탐색해 나가는 알고리즘 설계 방법

하지만, 선형탐색은 정보올림피아드에서 주어지는 문제 범위가 매우 크기때문에 일반적인 방법으로는 제한시간내에 답을 구하지 못하는 경우도 많습니다. 하지만 가장 기본적인 문제 해결방법으로 분류가 되고 가능한 모든 경우에 대해 탐색하는 과정에서 특별한 아이디어들을 만들어내고 적용해 어느정도 실행시간을 줄일 수 있기도 합니다.

탐색: 한 개 이상의 자료들이 구조화된 형태로 모여 있는 집합에서 특정 자료를 찾는 모든 작업

따라서, 어떤 문제상황이 주어진다고할때, 탐색할 자료가 저장되어 있는 구조를 먼저 파악하는 것이 중요합니다. 구조가 쉽게 드러나는 경우에는 쉬운문제라고 할 수 있으나, 주어진 문제상황에서의 데이터들간 연관관계를 스스로 구조화하여 탐색해야하는 경우는 중급이상의 문제라고 할 수 있습니다. 

탐색 대상이 되는 구조: 선형구조(배열, 연결 리스트), 비선형구조(트리, 그래프)

이때 탐색해야하는 데이터 구조 안에서 모든 경우의 수를 탐색하는 전체 탐색 방법과 일부분만 탐색하므로 정확한 결과값을 빠르게 얻어내는 부분 탐색 방법을 사용할 수 있습니다.

3. 선형구조의 탐색

---

선형구조: 탐색 순서가 있는 형태의 구조, i번째 자료를 탐색한 다음 i+1번째로 탐색해야 할 자료가 정해져 있는 형태를 의미. 주로 배열, 리스트 형태.

선형구조의 탐색: 선형구조로 저장된 자료들 중에서 원하는 값/데이터를 찾는 작업. 순차탐색과 이분탐색이 대표적. 구조의 특성에 띠리 특별한 탐색방법을 사용할 수도 있습니다.

순차탐색: 가장 일반적인 방법. 전체탐색기법의 한 방법으로, 첫 번째 원소로부터 시작해 한 원소씩 다음 순서대로 탐색해 나가는 방법. n개의 데이터를 순차적으로 탐색할 때 계산량은 O(n)으로 표현 가능

이분탐색: 정렬된 데이터 집합의 가운데 값을 기준으로 좌우 구간 중 하나를 선택해 같은 방법으로 반씩 쪼개가면서 탐색하는 방법. 계산량은 O(log n)으로 표현 가능.

선형구조의 순차탐색: 모든 경우를 조사하는 전체탐색법으로 생각할 수 있음

선형구조의 이분탐색: 특수한 상황(어떤 기준에 따라 정렬되어 있는 상황)에서 일부분만 탐색해 보다 빠르게 계산해내는 부분탐색법으로 생각할 수 있음.

[문제] n 개로 이루어진 정수 집합에서 원하는 수의 위치를 찾으시오. 단, 입력되는 집합은 오름차순으로 정렬되어 있으며, 같은 수는 없다.

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

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

입력 예	출력 예
8  1 2 3 5 7 9 11 15 (오름차순 정렬이라 이분탐색 가능)  11	7
3  2 5 7  3	-1

int solve(int s, int e) {
    int m;
    while(e-s >= 0)
    {
        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;
}

프로그래밍 언어를 활용해 해결할 수 있는 문제는 계산 가능한 문제이며, 결정문제, 탐색문제, 카운팅문제, 최적화 문제 등이 있습니다. 가장 간단한 선형탐색방법으로 모든 데이터들을 탐색할 수 있는데, 이분 탐색과 같은 방법을 사용하면 보다 빠르게 탐색하는 것이 가능합니다.