[중급-1] 정보과학과 문제, 선형구조의 탐색

이 포스트는 https://www.digitalculture.or.kr/koi/StudyOnline.do 를 기초로 하는 포스트입니다.

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

학습 목표

-프로그래밍 언어를 활용해 해결 가능한, 정보과학의 문제들에 대해서 이해한다.

-기본적인 문제 해결방법인 선형탐색 방법을 이해한다.

1. 정보과학과 문제

<1: 정보과학과 문제

계산문제 : 수학적 계산 가능(결정, 탐색, 카운팅, 최적화, 함수형)

(1) 결정문제 : 예or아니오

(2) 최적화 : 가장 좋은 해 찾기

(3) 탐색 : (탐색 가능한 형태로 구조화 후 탐색) 한개 이상의 자료들이 구조화된 집합에서 자료 찾기.

선형구조-배열, 연결리스트, 비선형구조-트리, 그래프

선형구조 : 다음 탐색해야할 자료가 정해져 있음.

선형구조의 탐색 : 선형구조의 자료 중에서 원하는 값or데이터 찾음. 순차탐색과 이분탐색이 대표적임.

순차탐색 : 첫번째부터 하나씩 하나씩 탐색.

이분탐색 : 가운데 값 기준으로 좌우 구간 중 하나 선택해서 탐색.

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

입력

첫 줄에 한 정수 n이 입력된다.

둘째 줄에 n개의 정수가 공백으로 구분되어 입력된다.

셋째 줄에는 찾고자 하는 수가 입력된다.(단, 2<=n<=1000000, 각 원소의 크기는 100,000,000을 넘지 않는다.

출력

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

입출력 예시_1:

<입력

8

1 2 3 5 7 9 11 15

11

<출력

7

입출력 예시_2:

<입력

3

2 5 7

3

<출력

-1

1. 순차탐색

#include <stdio.h>
#include <stdlib.h>
 
int main(){
    int *arr=(int *)malloc(sizeof(int)*1000000);
    int input;
    int wanttofind;
    int i, j;
 
    scanf("%d", &input);
 
    for(i=0; i<input; ++i){
        scanf("%d", &arr[i]);
    }
 
    scanf("%d", &wanttofind);
 
    for(i=0; i<input; ++i){
        if(wanttofind==arr[i]){
            printf("%d", i+1);
            break;
        }
        else if(i==input-1)
            printf("-1");
    }
    free(arr);
}

2. 이진탐색

(강의 선생님의 코드)

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