[ALGORITHMS]문제 07 순차탐색

문제 07 

순차 탐색

주어진 리스트에 특정한 값이 있는지 찾아 그 위치를 돌려주는 알고리즘을 만들어 보세요

리스트에 찾는 값이 없다면 -1을 돌려줍니다.

*리스트 안에 있는 원소를 하나씩 순차적으로 비교하면서 탐색한다고 하여 순차 탐색이라고 불립니다.

1. 순차 탐색으로 특정 값의 위치 찾기

다음은 순차 탐색 알고리즘을 이용하여 주어진 리스트[17,92,18,33,58,5,33,42]에서

특정 값(18,33,400)을 찾아서 해당 위치 번호를 돌려주는 프로그램입니다.

18은 리스트의 3번째에 있지만 위치번호는 2로 나옵니다

33은 두개가 중복 되지만 앞에껄로 나옵니다

900은 리스트에 존재하지않아서 -1로 나옵니다

2. 알고리즘 분석

순차 탐색 알고리즘으로 원하는 값을 찾으려면 비교를 몇 번 해야할까요?

이 질문은 답하기가 약간 모호합니다.

찾는 값이 리스트의 맨 앞에 있다면 단 한번만 비교해도 결과를 얻을 수 있습니다.

하지만 찾는 값이 리스트의 마지막에 있거나 아예 없다면 리스트의 끝까지 하나하나 비교해야 합니다.

이처럼 경우에 따라 계산 횟수가 다를 때는 최선의 경우, 평균적인 경우, 최악의 경우로 나누어 각각 계산 복잡도를 생각해 보기도 합니다.

 물론 어느 경우든 나름대로 의미가 있지만, 최악의 경우를 분석하면 어떤 경우라도 그보다는 빨리 계산할 수 있을겁니다. 따라서 최악의 경우로 분석해 보면 비교가 최대 n번 필요하고 계산 복잡도는 O(n)입니다.

연습문제

7-1 위의 그림에 나온 소스는 리스트에 찾는 값이 여러개 있더라도 첫 번째 위치만 결과로 돌려줍니다. 찾는 값이 나오는 모든 위치를 리스트로 돌려주는 탐색 알고리즘을 만들어 보세요. 찾는 값이 리스트에 없다면 빈 리스트인 []를 돌려줍니다.

7-2 연습문제 7-1 프로그램의 계산 복잡도는 무엇일까요?

O(n)

7-3 다음과 같이 학생 번호와 이름이 리스트로 주어졌을 때 학생 번호를 입력하면 학생 번호에 해당하는 이름을 순차 탐색으로 찾아 돌려주는 함수를 만들어 보세요. 해당하는 학생 번호가 없으면 물음표(?)를 돌려줍니다.