<1> 범위를 반씩 좁혀가는 탐색
순차 탐색
- 순차 탐색Sequential Search이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하니씩 차례대로 확인하는 방법
- 보통 정렬되지 않은 리스트에서 데이터를 찾아야할 때 사용
- 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소를 찾을 수 있음
이진 탐색 : 반으로 쪼개면서 탐색하기
- 이진 탐색Binary Search은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
- 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 잇다는 특징이 있음
- 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있음
- 이진 탐색은 위치를 나타내는 변수 3개를 사용
- 시작점, 끝점, 중간점
- 찾으려는 데이터와 중간점Middle위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾음
- 이진 탐색을 구현하는 방법에는 2가지가 있는데 하나는 재귀 함수를 이용하는 방법이고, 하나는 단순하게 반복문을 이용하는 방법
트리 자료구조
- 이진 탐색은 전제 조건이 데이터 정렬
- 데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리tree자료구조를 이용하여 항상 데이터가 정렬되어 있음
- 따라서 데이터베이스에서의 탐색은 이진 탐색과는 조금 다르지만, 이진 탐색과 유사한 방법을 이용해 탐색을 항상 빠르게 수행하도록 설계되어 있어 데이터가 많아도 탐색하는 속도가 빠름
- 트리 자료구조는 노드와 노드의 연결로 표현하며, 노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체
- 트리 자료구조는 몇가지 주요한 특징이 있음
- 트리는 부모 노드와 자식 노드의 관계로 표현
- 트리의 최상단 노드를 루트 노드
- 트리의 최하단 노드를 단말 노드
- 트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라고 함
- 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합
이진 탐색 트리
- 트리 자료구조 중에서 가장 간단한 형태가 이진 탐색 트리
- 이진 탐색 트리란 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조
- 이진 탐색 트리는 다음과 같은 특징을 가짐
- 부모 노드보다 왼쪽 자식 노드가 작다
- 부모 노드보다 오른쪽 자식 노드가 크다
- 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 가 성립해야 함
<2> 부품찾기
- 동빈이네 전자 매장에는 부품 N개가 있음
- 각 부품은 정수 형태의 고유한 번호가 있음
- 손님이 M개 종류의 부품을 대량으로 구매
- 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성
- 가게 안에 부품이 모두 있는지 확인
내가 작성한 코드
# 가게 부품 입력
n = int(input())
parts = list(map(int, input().split()))
# 손님 부품 입력
m = int(input())
cu_parts = list(map(int, input().split()))
answer = []
for i in cu_parts:
if i in parts:
answer.append("yes")
else:
answer.append("no")
print(answer)
<3> 떡볶이 떡 만들기
- 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단
- 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않음
- 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값
내가 작성한 코드
# 떡 개수와, 떡 최소 길이
n, m = map(int, input().split())
# 전체 떡 길이
cakes = list(map(int, input().split()))
for i in range(1, max(cakes)):
cake_sum = sum([(j - i) if (j-i) > 0 else 0 for j in cakes])
if cake_sum <= m:
print(i)
break
