Algorithm) Binary Search

이진탐색에 들어가기전

가장 기본 탐색 방법인 순차 탐색에 대해서

살짝 다루고 가보쟈 !

 

순차탐색(Sequential Search)이란 ? 

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 

데이터를 하나씩 차례대로 확인하는 방법

 

- 리스트에 특정 값의 원소가 있는지 체크 

- 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는

count() 메서드의 내부에서의 순차탐색 

 

# 순차탐색 소스코드
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))

 

 

본론인 이진탐색 시작 -! 

 

이진탐색 : 반으로 쪼개면서 탐색하기 

 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다. 

탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다! 

 

이진탐색은 위치를 나타내는 변수 3개를 사용하는데

탐색하고자하는 범위의 시작점, 끝점, 그리고 중간점이다.

 

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로

비교해서 원하는 데이터를 찾자 !

---

예를 들어, 

0 2 4 6 8 10 12 14 15 18

=> 여기서 시작점은 0, 끝점은 18, 중간점은 [4.5] 위치에서 

소숫점 자리를 버린 [4] 위치의 8이 된다 ! 

찾으려고하는 데이터가 4일때 중간점인 8보다 작으므로 ,

8 이후의 값은 확인할 필요가 없다. 

 

다시, 시작점은 0 끝점은 6 중간점은

[1.5] -> [1] 인 2가 된다. 

중간점인 2보다 4가 크므로, 2 이하의 값은 확인할 필요가 없다. 

 

다시, 시작점은 4 끝점은 6이 된다.

중간점이 찾으려는 데이터와 동일하므로 탐색을 종료한다 !

 

---

이렇게 전체 데이터의 개수는 10개 지만, 이진탐색을 이용해 

총 3번의 참색으로 원소를 찾았다. 시간복잡도는 O(logN)이 된다.

 

이진탐색 알고리즘은 한 단계를 거칠때마다 화인하는 원소가 평균적으로

절반으로 줄어든다. 

 

구현하는 방법은 2가지가 있다 !

1. 재귀함수를 이용하는 방법

2. 단순하게 반복문을 이용하는 방법

 

---

1. 재귀함수를 이용하는 방법

 

# 이진탐색 - 재귀적
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 = 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)

 

 

 

 

2. 단순하게 반복문을 이용하는 방법

 

# 이진탐색 소스코드 - 반복문
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, target = 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)

 

코딩테스트에서 이진탐색은 단골 문제 !

가급적 외우자 

 

---

트리 자료구조 🌿

 

노드와 노드의 연결로 표현하며 여기에서 노드는 

정보의 단위로서 어떠한 정보를 가지고 있는 개체로 이해할 수 있다.

데이터베이스 시스템이나 파일시스템과 같은 곳에서 많은 양의

데이터를 관리하기 위한 목적으로 사용한다.

 

- 트리는 부모노드와 자식노드의 관계로 표현된다

- 트리의 최상단 노드를 루트 노드라고 한다

- 트리의 최하단 노드를 단말 노드라고 한다

- 트리에서 일부를 뗴어내도 트리구조이며 이를 서브트리라고 한다

- 트리는 파일 시스템과 같이 계층적이고 

정렬된 데이터를 다루기에 적합하다 

 

---

이진 탐색 트리 🥗

 

트리자료구조 중에서 가장 간단한 형태가 이진 탐색 트리이다.

이진 탐색 트리란 이진 탐색이 동작할 수 있도록 고안된

효율적인 탐색이 가능한 자료구조이다.

 

- 부모노드보다 왼쪽 자식 노드가 작다

- 부모노드보다 오른쪽 자식 노드가 크다 

 

왼쪽 자식노드 < 부모 노드 < 오른쪽 자식 노드

 

---

빠르게 입력받기 👀

 

이진탐색 문제는 입력 데이터가 많거나 , 탐색 범위가 매우넓은 편 ! 

이렇게 입력 데이터의 개수가 많은 문제에 input() 함수를 사용하며 동작 속도가 느려서

시간초과로 오답 판정을 받을 수 있다 ! 

 

입력데이터가 많은 문제는 sys 라이브러의 readline() 함수를 이용하자 !

 

import sys
# 하나의 문자열 데이터 입력받기 
input_data = sys.stdin.readline().rstrip()

print(input_data)

 

sys 라이브러리를 사용할 땐

한줄 입력받고나서 rstrip() 함수를 꼭 호출해야한다

readline() 으로 입력하며 입력후 엔터가 줄바꿈 기호로 입력되는데,

이 공백 문자를 제거하기 위해서다 ! 

 

 

깃헙에 정리해놓은 input ! 

GitHub - Suyeon9911/Algorithm-Study: 알고리즘 공부 레포 🦋