홈 [Algorithm] 코딩테스트 알고리즘 09 - 탐색
포스트
취소

[Algorithm] 코딩테스트 알고리즘 09 - 탐색

게시 2022-05-19 업데이트 2022-10-16
By 19tak

본 포스팅은 “이것이 취업을 위한 코딩테스트다 with 파이썬” - (한빛미디어, 나동빈 지음)을 바탕으로 공부한 내용을 정리한 것입니다.

  1. 순차탐색
  2. 이진탐색

1. 순차탐색

순차 탐색 (Sequential Search)란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다.

보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다.

최악의 경우 시간 복잡도는 O(N)이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 순차 탐색 소스코드 구현
def sequential_search(n, target, array):
    # 각 원소를 하나씩 확인하며
    for i in range(n):
        # 현재의 원소가 찾고자 하는 원소와 동일한 경우
        if array[i] == target:
            return i + 1 # 현재의 위치 반환 (인덱스는 0부터이므로 +1)
    
print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")
input_data = input().split()
n = int(input_data[0]) # 원소의 개수
target = input_data[1] # 찾고자 하는 문자열

print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
array = input().split()

# 순차 탐색 수행 결과 출력
print(sequential_search(n,target,array))

2. 이진탐색

이진 탐색 (Binary Search)은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정이다.

시간복잡도는 O(logN)이다.

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

# 이진탐색 소스코드 구현 (재귀 함수)
def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
        return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid-1)
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
        return binary_search(array, target, mid+1, end)
    
# n(원소의 개수)과 target(찾고자 하는 문자열)을 입력받기
n, target = list(map(int,input().split()))
# 전체 원소 입력받기
array = list(map(int,input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n-1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

3. 트리 자료구조

이진 탐색은 전제 조건이 데이터 정렬이다.

데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 이용하여 항상 데이터가 정렬되어 있다.

따라서 데이터베이스에서의 탐색은 이진 탐색과는 조금 다르지만, 이진 탐색과 유사한 방법을 이용해 탐색을 항상 빠르게 수행하도록 설계되어 있어서 데이터가 많아도 탐색하는 속도가 빠르다.

이진 탐색 트리에 데이터를 넣고 빼는 방법은 알고리즘보다는 자료구조에 가까우며, 이진 탐색 트리 자료구조를 구현하도록 요구하는 문제는 출제 빈도가 낮다.

4. 실전 문제 1

부품 찾기

N개의 부품이 있고 각 정수 형태의 고유 번호가 있다. 손님이 M개 종류의 부품을 대량 구매하기 위해 견적서를 요청했다. 문의 부품 M개 종류를 모두 확인해서 있는지 확인한다.

  • 첫째 줄에 정수 N이 주어진다. (1<=N<=1,000,000)
  • 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 정수는 1 초과 1,000,000 이하이다.
  • 셋째 줄에는 정수 M이 주어진다. (1<=M<=100,000)
  • 넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. 정수는 1초과 1,000,000 이하이다.
  • 첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes, 없으면 no를 출력한다.

이진 탐색 풀이

부품을 찾는 과정에서 O(MxlogN)이, 정렬에 O(NxlogN)이 필요하여, 결과적으로 이진 탐색으로 풀이할 경우 시간 복잡도는 O((M+N) x logN)이다.

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
29
30
31
32
33

# 이진 탐색 소스코드 구현(반복문)
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start+end)//2
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
            return mid
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
            end = mid - 1
        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else:
            start = mid + 1
    return None

# N(가게의 부품 개수) 입력
n = int(input())
# 가게에 있는 전체 부품 번호를 공백으로 구분하여 입력
array = list(map(int,input().split()))
array.sort() # 이진 탐색 수행 위해 정렬 수행
# M(손님이 확인 요청한 부품 개수) 입력
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백으로 구분하여 입력
x = list(map(int,input().split()))

# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
    # 해당 부품이 존재하는지 확인
    result = binary_search(array, i, 0, n-1)
    if result != None:
        print('yes',end=' ')
    else:
        print('no',end=' ')

계수 정렬 풀이

모든 원소의 번호를 포함할 수 있는 크기의 리스트를 만든 뒤에, 리스트의 인덱스에 직접 접근하여 특정한 번호의 부품이 매장에 존재하는지 확인.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# N(가게의 부품 개수)을 입력받기
n = int(input())
array = [0] * 1000001

# 가게에 있는 전체 부품 번호를 입력받아서 기록
for i in input().split():
    array[int(i)] = 1

# M(손님이 확인 요청한 부품 개수)을 입력받기
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백으로 구분하여 입력
x = list(map(int,input().split()))

# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
    # 해당 부품이 존재하는지 확인
    if array[i] == 1:
        print('yes',end=' ')
    else:
        print('no',end=' ')

집합 자료형 풀이

해당 문제는 단순히 특정 수가 한번이라도 등장했는지만 검사하면 되므로 집합 자료형을 이용해도 된다.

set() 함수는 집합 자료형을 초기화할 때 사용한다. 단순히 특정한 데이터가 존재하는지 검사할 때에 매우 효과적으로 사용한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# N(가게의 부품 개수)을 입력받기
n = int(input())
# 가게에 있는 전체 부품 번호를 입력받아서 집합(set) 자료형에 기록
array = set(map(int,input().split()))

# M(손님이 확인 요청한 부품 개수)을 입력받기
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백으로 구분하여 입력
x = list(map(int,input().split()))

# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
    # 해당 부품이 존재하는지 확인
    if i in array:
        print('yes',end=' ')
    else:
        print('no',end=' ')

참고

“이것이 취업을 위한 코딩테스트다 with 파이썬” - (한빛미디어, 나동빈 지음)

Study, Algorithm
Python Algorithm
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.
최근 업데이트
바로가기