오늘 한 일📝
- 이분 탐색 이론 공부
- Algorithm 문제 풀이(1920, 2805, 8983, 2630)
이분탐색
탐색은 데이터 집합에서 원하는 값을 가진 원소를 찾아내는 알고리즘을 말한다. 대표적인 탐색 방법은 다음과 같다.
- 배열 검색
- 연결 리스트 검색
- 이진 검색 트리
선형 검색(Linear search)
직선 모양(선형)으로 늘어선 배열에서 검색하여 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 순서대로 검색하는 알고리즘을 말한다.
- n의 복잡도를 갖는다.
검색 종료 조건
- 검색 실패: 검색할 값을 찾지 못하고 배열의 맨 끝을 지나는 경우(
if i == len(a)) - 검색 성공: 검색할 값과 같은 원소를 찾는 경우(
if a[i] == key)
배열 원소의 개수가 n일 때, 조건을 판단하는 횟수는 평균n/2를 갖는다.
def seq_search(a, key):
for i in range(len(a)):
if a[i] == key:
return i
return -1이진 검색(Binary search)
이진 검색 알고리즘을 사용하려면 데이터가 '정렬'되어 있는 상태여야 한다. 정렬된 상태에서 검색 범위를 줄여가면서 탐색하는 방식이다.
- log n의 복잡도를 갖는다.
반복문 사용
def binary_search(a, key):
pl = 0 # 검색 범위 맨 앞 원소의 인덱스
pr = len(a) - 1 # 검색 범위 맨 끝 원소의 인덱스
while True:
pc = (pl + pr) // 2 # 중앙 원소의 인덱스
if a[pc] == key:
return pc # 검색 성공
elif a[pc] < key:
pl = pc + 1 # 검색 범위를 뒤쪽 절반으로 좁힘
else:
pr = pc - 1
if pl > pr: # 검색 범위를 앞쪽 절반으로 좁힘
break
return -1 # 검색 실패재귀 사용
def binary_serach(array, target, start, end):
if start > end:
return -1 # 검색 실패
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) # 검색 범위를 뒤쪽 절반으로 좁힘이진 탐색 심화
만약 찾는 값이 없다면, 인접한 원소를 전달해주는 코드를 작성해보자.
a = [1, 4, 5, 9, 10, 11, 11, 3]
a.sort()
def binary_search(numbers, key):
left = 0
right = len(numbers)-1
while left <= right:
middle = (left + right) // 2
if key == numbers[middle]:
print(middle)
return middle
break
elif key < numbers[middle]:
right = middle -1
elif key > numbers[middle]:
left = middle + 1
# Not key in the list
if right == -1:
print(numbers[0])
elif left == len(a):
print(numbers[len(a)-1])
else:
prev_num = numbers[left-1]
next_num = numbers[right+1]
prev_step = abs(key - prev_num)
next_step = abs(key - next_num)
if prev_step == next_step:
print(prev_num, next_num)
elif prev_step > next_step:
print(next_num)
elif prev_step < next_step:
print(prev_num)
binary_search(a, 8)Algorithm
1920: 수 찾기
1920번: 수 찾기
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들
www.acmicpc.net
이진 탐색으로 풀이하는 코드를 작성하여 풀면 된다.
2805: 나무 자르기
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
계속 틀렸는데 다시 돌아보자면
- 나누어 떨어지지 않을 수도 있다. -> 목표 구매량을 채울 수 있는 범위를 반환한다.
- 경계값을 정확하게 계산하는데 집중하자.
8983: 사냥꾼
8983번: 사냥꾼
KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가
www.acmicpc.net
이진 탐색으로 찾지 못한 것은 인접한 원소를 반환하도록 한다. 이 부분만 잘 생각하면 나머지는 간단하다. 신기하게 부분 점수가 있었다. 그래서 그런지 채점하는데 시간이 오래 걸렸다.
2630: 색종이 만들기
2630번: 색종이 만들기
첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.
www.acmicpc.net
어떻게 풀까 고민했지만 Z문제를 기억해서 금방 해결했다. 그렇지만 범위를 매번 0부터 길이까지 하도록 하여 반복이 끝나지 않아 잘못된 값이 나옴을 확인할 수 있었다.
- 경계값을 정확하게 계산하는 것이 역시나 중요하다.
오늘은 아침 일찍 일어나서 스트레칭도 하고, 약간의 운동도 하고 밥 먹고 8시쯤에 도착했다.
하지만 점심 먹고, 저녁 먹고 모두 졸렸다. 항상 바로 오는데 기숙사가서 잠깐 자고 와도 괜찮을 것 같기도 하다. 아니면 잠 시간을 좀 더 늘려야겠다.
내일 할 일👊
- 2805, 8983 오답
- 알고리즘 문제 풀이: 2110, 2470, 11053, 1629, 6549
- main, python memory 공부하기
- 쿠기, 세션, jwt
