🏀 개요

알고리즘 중 탐색 부분을 이어서 공부하고자 하낟.

참고 :
동빈나 유튜브 채널을 기반으로 정리한 것으로, 유튜브 링크를 첨부 하겠습니다.
동빈나 유튜브 링크

💡 접근 방식

정렬 - 선택 정렬, 삽입 정렬, 퀵 정렬

정렬한 결과를 사용하는 경우도 있고, 정렬하는 과정에서 계산하는 경우도 있다. 그래서 일반적으로 지원하는 python array.sort() 뿐만 아니라 각 과정에 대해서도 알고 있으면 이용하는 경우가 있다.

탐색 - 이진탐색
순차 탐색과 다르게 탐색 범위를 계속 줄여 나가면서 진행하므로 성능에 장점이 있다.
단, 배열이 정렬되어 있을 경우라는 조건이 있다.

최적화 문제에서 사용된다. 답으로 가능한 케이스와 최적화 값을 가지고, 답의 케이스 범위를 줄여나가 답을 찾아낸다. 이 부분에 대한 이해는 문제를 풀면 확실히 알 수 있다.

조건에 맞게 답의 범위를 찾고, 그 범위를 줄여서 답을 찾는다! 이것에 일단 집중하자.

💎 선택 정렬, 삽입 정렬, 퀵 정렬

• 선택 정렬

중요 아이디어: 가장 작은 데이터 선택! 하여 범위 내 맨 앞으로 보내는 것

코드:

for i in range(len(array)): # i를 통해서 범위 내 맨 앞 값을 지정
	min_idx = i # 가장 작은 값의 인덱스를 지정할 변수
    for j in range(i+1,len(array)): # min_idx 선택을 위한 반복
    	if array[j] < array[min_idx]:
        	min_idx = j
    array[i], array[min_idx] = array[min_idx], array[i] # 맨 앞과 min swap
 

장점: 보는 것 처럼 구현이 쉽다. 단점 : for 문이 중첩되어 있다. 즉 시간 복잡도가 O(N^2), 성능이 안좋다.

• 삽입 정렬

중요 아이디어: 첫 값은 정렬되어 있다고 가정하고, 나머지 값들의 위치를 선정해 삽입을 한다.

위치 선정 기준은 값의 크기로 작을 경우 왼쪽, 큰 경우 오른쪽에 위치하도록 삽입한다.

결국, 오른쪽, 왼쪽 위치 지정 후 삽입 이라고 이해하면 된다.

코드:

for i in range(1,len(array)): # 1부터 시작하는 이유는 첫 번째는 정렬되어있다고 가정하기 때문
	for j in range(i,0,-1): # 실제로 비교 대상이 되는 값을 의미한다. 가장 적합한 위치를 찾기 위한 반복문
    		if array[j] < array[j-1]:
        		array[j], array[j-1] = array[j-1], array[j] #swap
        	else:
        		break # 작지 않은 경우 적합한 위치를 찾았다고 생각하고 종료!

• 퀵 정렬

중요 아이디어: Pivot이라는 기준 데이터를 선정(첫 번째 데이터)이 기준 데이터 보다 큰 데이터를 왼쪽에서
순차적으로 찾고 작은 데이터는 오른쪽에서 순차적으로 찾음.

종료 조건은 left > right, 즉 엇갈린 경우이다. 이 경우에 종료하면 값들이 분할되고 왼쪽에는 Pivot보다 작은 값만, 오른쪽에는 큰 값만 으로 나눠진다.

코드:

def quick_sort(array):
	# 재귀함수를 이용할 것이므로 종료 조건을 줘야한다.
    if len(array) <= 1:
    	return array
    
    pivot = array[0] # 기준 값, 첫 번째 원소
    target = array[1:] # 기준 값을 제외한 분할 대상 값
    
    left_side = [x for x in target if x < pivot] # 작은 값은 왼쪽으로 분할
    right_side = [x for x in target if x > pivot] # 큰 값은 오른쪽으로 분할
    
    return quick_sort(left_side) + pivot + quick_sort(right_side)

💎 이진 탐색

중요 아이디어:

중간 값을 기준으로 값을 비교해서 범위를 줄여나간다. start, end, mid 이 3가지 값을 기준으로 생각하면 된다.

코드:

def binary_search(array,target,start,end):
	while start <= end: # 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 # 반복문 안에서 값을 찾지못할 경우, target은 존재 하지 않는다.

🔧 예제 문제

이진 탐색 예제문제로 유튜브에서 소개해준 떡볶이 길이 문제가 정말 좋은 예시라고 생각한다.

나아가서 해커랭커에서 아래의 문제를 풀고 정리할 예정

• 정렬

Mark and Toys 문제 바로가기

def maximumToys(prices, k):
    prices.sort()
    i = 0
    while True:
        k -= prices[i]
        if k < 0:
            break
        i += 1

    return i

전형적인 sort 결과 값을 사용하는 문제다.

Sorting: Comparator 문제 바로가기

class Player:
    def __init__(self, name, score):
        self.name = name
        self.score = score
        
    def __repr__(self):
        pass
        
    def comparator(a, b):
        if a.score > b.score:
            return -1
        elif a.score == b.score:
            if a.name > b.name:
                return 1
            elif a.name == b.name:
                return 0
            else:
                return -1
        else:
            return 1

문제에서 요청한 대로 sort할 수 있게 비교함수를 정의하는 문제 였다. 간단하다!

• 탐색

Swap Nodes Algo 문제 바로가기

트리, in-order 탐색 문제라서.. 일단 풀긴했는데 여기서는 스킵하도록 하겠음.

Triple sum 문제 바로가기

처음에 문제보고 바로 접근한 방식은

# Complete the triplets function below.
def triplets(a, b, c):
    a = list(set(a))
    c = list(set(c))
    a.sort()
    c.sort()
    b = list(set(b))
    b.sort(reverse=True)
    answer = 0
    for q in b:
        tempa = []
        tempc = []
        for p in a:
            if p <= q:
                tempa.append(p)
            else:
                break
        for r in c:
            if r <= q:
                tempc.append(r)
            else:
                break
        answer += (len(tempa) * len(tempc))
    return answer

for 문을 통해서 비교하는 방식이었다. 역시나 타임 아웃이 발생하였고, 이를 최적화 하기 위해서 이진 탐색 기법을 도입했다.

def check_cnt(array,target,start,end):
    if array[0] > target:
        return 0

    while start <= end:
        mid = (start + end)//2
        if array[mid] == target:
            return (mid+ 1)
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    else:
        return end + 1

def triplets(a, b, c):
    a= list(set(a))
    b= list(set(b))
    c = list(set(c))
    a.sort()
    b.sort(reverse=True)
    c.sort()
    
    answer = 0

    for q in b:

        a_cnt = check_cnt(a,q,0,len(a)-1)
        c_cnt = check_cnt(c,q,0,len(c)-1)

        answer += (a_cnt * c_cnt)

    return answer

이진 탐색으로 비교 자체의 횟수가 크게 감소한다. 그래서 타임 아웃 이슈를 해결할 수 있었다.
문제 조건에 맞춰서 중복된 값 제거 후에 이진 탐색에서 사용할 수 있게 sort를 하고, 이진 탐색 수행

두 가지 케이스로 나눠서 정확하게 일치하는 경우와 일치하지 않는 경우, 모두 결국 그 이하의 값은 작다는걸 보장하기 때문에 idx + 1 로 cnt를 계산이 가능