[프로그래머스스쿨]자료구조/알고리즘 기초

힙 heap

[자료구조] 힙(heap)이란 - Heee's Development Blog

# 힙 이용법
from heapq import heapify, heappush, heappop

lst = [5, 1, 2, 7, 4, 9, 8, 10, 3, 6]
heapify(lst) # lst를 Heap으로 만들어줍니다.
print(lst) # [1, 3, 2, 5, 4, 9, 8, 10, 7, 6] Heap 기준에서 바라볼 때 정렬된 모습입니다.

heappush(lst, 3) # Heap에 3을 추가합니다. O(log n)이 소요됩니다.
print(lst) # [1, 3, 2, 5, 3, 9, 8, 10, 7, 6, 4]

heappop(lst) # 가장 작은 값 1을 반환하고 제거합니다. O(log n)이 소요됩니다.
print(lst) # [2, 3, 4, 5, 3, 9, 8, 10, 7, 6] 1 다음으로 작은 값인 2가 root로 선택됩니다.

# 배상 비용 최소화
import heapq
def solution(no, works):
    if sum(works) <= no:
        return 0
    
    heap=[]
    for i in works:
        heapq.heappush(heap,-i)
        
    for _ in range(no):
        heapq.heapreplace(heap, heap[0]+1)
        
    return sum(i**2 for i in heap)

point 1. 파이썬에서는 공식적으로는 maxheap을 제공하지 않기 때문에 연산자를 반대로 적용해준다. (큰 수일수록 -, 작은 수일수록 +)

point2. replace는 제거 후 추가, pushpop은 추가 후 제거

point3. 추가는 가장 마지막 정점에, 제거는 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치

point4. 시간복잡도는 O(logN)

point5. 자료 정렬 규칙에 우선순위가 존재한다? 바로 힙!

point6. 결론적으로 원하는 자료로 루트힙을 바꿔주는게 최종목적

[파이썬] heapq 모듈 코드 뜯어보기

 

heapq --- 힙 큐 알고리즘 — 파이썬 설명서 주석판

트라이 Trie

[Python / 파이썬] Trie 알고리즘

이진 탐색 Binary Search

선형탐색 : O(N), 앞에서 하나씩

이진탐색 : O(logN), 업앤다운 게임시 절반시 줄여나가는 것과 같음, 반드시 정렬되어있어야 함. 최악의 경우 한쪽으로 편향된 트리가 나타남. AVL트리, 레드-블랙트리로 해결

# 기본 구현

def binary_search(array, find_value):
	left = 0
	right = len(array)-1
    mid=(left+right)//2
    
while left < right:
	if array[mid] == find_value:
    	return mid
    
    if array[mid] < find_value:
    	left = mid + 1
        else:
        right = mid -1
        
    mid = (left + right) // 2
    
return -1

# 입국심사

def solution(n, times):
    
    start,end = 1, max(times) *n 
    res = end
    while start <= end:
        mid = (start + end) // 2
        
        people = 0
        for time in times:
            people += (mid // time)
            
        if people < n:
            start = mid+1
        else: #people >= n:
            end = mid-1
            res = min(res, mid)
            
    return res

point1. 데이터가 어어엄청 크다 -> 이진탐색 의심

알고리즘 문제 해결 전략

point2. start, end 잘 설정하고, mid는 return받기 원하는 정보에 관한 데이터

 

넓이 우선 탐색 BFS, 깊이 우선 탐색 DFS

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

DFS(깊이우선탐색)	BFS(너비우선탐색)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현	큐를 이용해서 구현

 

그리디

매 선택에서 지금 이 순간 가장 최적인 탐색을 선택하는 알고리즘으로 최적해를 보장해주지는 않는다. 단 빠르다

크루스칼, 다익스트라 알고리즘 등에 사용

# 큰 수 만들기

def solution(number, k):
    stack = []
    count = 0
    
    for item in number:
        while count < k and stack and stack[-1] < item:
            stack.pop()
            count += 1
        stack.append(item)
        
    while count < k:
        stack.pop()
        count += 1
        
    return ''.join(stack)

소수구하기

1번 방법(직관적, 비추천) : 2부터 n-1까지 모든 수를 돌면서 나누어 떨어지는지 확인한다. O(n)시간 소요.

def is_prime(num):
	for i in range(2, num):
    	 if num % i == 0:
        	 return False
         return True

2번 방법(효율성 개선) : 모든 소수는 제곱근보다 큰 수로 나누어 떨어지지 않는다. 55의 제곱근은 7.xxx이므로 7까지만 확인한다. O(sqrt(n))시간 소요.

def is_prime(num):
	for i in range(2, int(num**0.5) + 1):
    	if num % i == 0:
        return False
    return True

3번 방법(추천) : 에라토스테네스의 체. 구하고자 하는 숫자 범위 내에서 제곱근이 될 수 있는 최대의 숫자범위 까지 탐색.

1~55 내의 소수의 개수를 구하려 7^2=49 < 55 < 8^2=64이므로 7까지만 탐색하며 각 소수의 배수들을 지운 나머지가 소수가 됨. O(n log log n)시간 소요.

def get_primes(num):
	prime = [False,False] + [True] * (num-1)
	for i in range(2, int(num**0.5) + 1):
        if primes[i]:
            for j in range(i*2, num+1, i):
                primes[j]=False
    
    return [i for i in range(num+1) if primes[i]]

재귀 함수

자기 자신을 호출하는 함수.

함수 호출은 Call stack에 쌓이기 때문에 스택 자료구조와 유사하게 동작한다.

함수형 프로그래밍에선 루프 구현을 재귀함수로 함.

파이썬에서 > 콜 스택에 1,000번 제한 있음, 꼬리 재귀(Tail recursion) 미제공, 성능이 좋지 않음

그럼에도 불구하고! 재귀로 구현해야 편한 알고리즘 : Union_find, DFS, Backtracking

반드시 탈출 조건, 탈출 코드를 넣어 무한 루프에 빠지는 것을 방지함.

# 기본 예시 : 피보나치 수열
def fibonacci(x):
	if x <= 2:
    	return 1
    return fibonacci(x-1) + fibonacci(x-2)
print(fibonacci(7))

 

# 합병 정렬
# 결합
def merge(a,b):
	if not a:
    	return b
    elif not b:
   		return a
    elif a[0]<b[0]:
    	return [a[0]] + merge(a[1:],b
    else:
    	return [b[0]] + merge(a, b[1:])
        
# 분해
def mergesort(arr):
	if len(arr)<2:
    	return arr
    else:
    	mid = len(arr)//2
        return merge(mergesort(arr[0:mid]), mergesort(arr[mid:]))
        
print(mergesor([21,10,12,20,25,13,15,22]))
#[10,12,13,15,20,21,22,25]

최단 경로 알고리즘 다익스트라 Dijkstra

그래프의 특정 정점에서 목적지까지 최단 경로를 구하는 알고리즘.

최단 경로 알고리즘 예시

- BFS DFS : 그래프의 간선 가중치가 모두 같을 때 적합. 2차원 배열(지도)입력 -> 최단거리 구하기시 사용

- 벨만-포드, 플로이드 와샬

- 다익스트라 : 그래프의 간선 가중차가 각각 다를 경우 사용. 우선순위 큐를 이용하여 만듦. O(ElogV)(E 정점의수, V 간선의 수)

1. 시작점을 제외한 모든 정점의 거리를 무한으로 설정. 시작점은 0

2. 시작점을 선택

3. 선택한 정점에서 갈 수 있는 정점의 거리를 정점(해당 정점까지의 최단거리)값 +간선(거리)값으로 갱신

4. 선택한 정점을 방문 처리

5. 이미 방문한 정점과 무한인 정점을 제외하고 가장 최단 거리인 정점을 선택

6. 더 이상 방문할 수 있는 정점이 없을 때 까지 3~5 반복

7. 도착점의 값을 확인

# 배달경로 
from heapq import heappush, heappop 

def dijkstra(road, N):
    heap = [[1, 0]] 
    
    dist = [float('inf')] * (N + 1) 
    dist[1] = 0 
    
    while heap:
        current, current_cost = heappop(heap) 
        for src, dest, cost in road: 
            next_cost = cost + current_cost 
            if src == current and next_cost < dist[dest]:
                dist[dest] = next_cost
                heappush(heap, [dest, next_cost]) 
            elif dest == current and next_cost < dist[src]:
                dist[src] = next_cost 
                heappush(heap, [src, next_cost]) 
    return dist

def solution(N, road, K):
    dist = dijkstra(road, N)
    return len([x for x in dist if x <= K]) # list comprehension

최소 신장 트리 Kruskal

신장트리: 그래프 내에 모든 정점을 포함하는 최소 연결 부분

최소신장트리: 최소한의 비용으로 모든 정점을 연결하기 위해서 불필요한 간선을 제거함

- 최소한의 간선으로 모든 정점이 연결

- 모든 신장 트리 중 가중치의 값이 최소

- Cycle이 발생해서는 안됨

Kruskal, Prim 등

Kruskal : 모든 그래프를 부분집합으로 분리 -> 가장 가중치가 낮은 간선부터 선택(Greedy)하고 부분집합을 연결 -> Cycle이 발생하지 않도록 공통 최상위 부모를 찾음: 각 원소가 같은 집합인지 확인(Union-Find), 두 정점이 같은 집합에 속한다면(Cycle)

# 섬 연결하기

def find(parent, x):
    if parent[x] == x:
        return x
    parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
def compare(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    return a == b

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x: x[2])
    parent = [i for i in range(0, n)]
    
    for a, b, cost in costs:
        if not compare(parent, a, b):
            answer += cost
            union(parent, a, b)
            
    return answer

투포인터

일차원 배열에 두개의 포인터를 두고 조작, 보통 연속적인 구간에 대한 계산에 사용

백트래킹이나 완전탐색으로 풀려다 시간 제한에 걸리는 경우 있음

# 보석쇼핑

from collections import defaultdict

def solution(gems):
    answer = [0, len(gems)] # 가장 긴 길이로 초기화합니다.
    gem_kinds = len(set(gems)) # 겹치지 않는 보석의 갯수
    start, end = 0, 0 # 첫 번째와 두 번째 포인터
    gems_count = defaultdict(int)
    gems_count[gems[0]] = 1 # 시작하면서 첫 보석을 먼저 담는다

    while start < len(gems) and end < len(gems): # 두 포인터가 끝에 도달한다면 종료
        if len(gems_count) == gem_kinds: # 모든 보석을 구매할 수 있다면
            if end - start < answer[1] - answer[0]: # 구간을 갱신
                answer = [start + 1, end + 1]
                
            gems_count[gems[start]] -= 1 # 첫 번째 포인터에 해당하는 보석을 한 개 줄인다.

            if gems_count[gems[start]] == 0: # 만약 0이 됐다면 목록에서 제거된다.
                del gems_count[gems[start]]
            start += 1 # 첫 번째 포인터 증가
        else: # 모든 보석을 구매할 수 없다면
            end += 1 # 두 번째 포인터 증가
            if end >= len(gems): # 구간을 벗어나면 종료
                break
            gems_count[gems[end]] += 1 # 보석을 추가한다.

    return answer # 결과 반환

point1. defaultdict를 사용

011 딕셔너리를 한 번에 초기화하려면? ― collections.defaultdict

 

백트래킹

모든 경우의 수를 탐색하는 알고리즘. 효율을 위해 탐색하지 않아도 되는 곳을 미리 가지치기(Pruning)함.

파이썬은 재귀 효율이 나쁘기 때문에 DFS를 구현할 경우 스택을 이용하는 것이 좋다.(예외도 있음)

탐색에서 순환(Cycle)이 발생할 수 있다면 BFS를 이용하는 것이 편하다.

*가지치rl : 우선 모든 경우의 수 찾도록 코딩 -> 특정 조건을 만족하는 것만 탐색하도록 조건문 작성 -> 절대로 답이 될 수 없는 것은 탐색을 종료함

# N-Queen

def check(queen, row):
    # 이전까지 두었던 퀸의 위치를 확인한다.
    for i in range(row):
        # 행의 위치와 대각선의 위치를 체크한다.
        if queen[i] == queen[row] or abs(queen[i] - queen[row]) == row - i:
            return False # 둘 수 없다면 false
    return True # 모두 통과되면 true

def search(queen, row):
    n = len(queen)
    count = 0

    if n == row: #체스판 끝에 도달했다면.. 재귀의 탈출 조건
        return 1

    for col in range(n): # 0부터 n까지 열을 돌면서 퀸을 둘 수 있게 만든다.
        queen[row] = col # 우선 퀸을 둔다
        if check(queen, row): # 퀸을 둘 수 있다면..
            count += search(queen, row + 1) # 다음 행으로 이동!

    return count

def solution(n):
    # 미리 n개 만큼의 배열을 초기화한다. 0번 행부터 시작한다.
    return search([0] * n, 0)

동적 계획법

해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식. 메모리를 많이 사용하는 대신 빠른 성능을 가짐.

- 메모이제이션: 하향식 접근법, 작은 문제의 결과를 저장해두었다가 꺼내어 쓰는 방법

- 타뷸레이션: 상향식 접근법, 필요한 값들을 미리 계산해두는 것. 메모이제이션은 필요할 떄 계산한다면(Lazy evaluation), 타뷸레이션은 미리 계산해둔다(Eager evaluation)

- 가장 작은 문제를 정의할 수 있는지? 작은 문제를 통해 큰 문제를 해결할 수 있는 규칙이 있는지?

# 단어퍼즐
def solution(strs, t):
    # 편의를 위해 t의 길이 + 1만큼 배열을 만든다.
    dp = [0] * (len(t) + 1)
    # 문자열 검사를 빠르게 하기 위해서 문자열 리스트를 set으로 만든다.
    strs = set(strs)

    # 1부터 문자열 길이 + 1까지 루프를 돈다.
    for i in range(1, len(t) + 1):
        # 일단 해당 문자열의 최솟값은 무한으로 설정한다.
        dp[i] = float('inf')
        # 문자열을 자르면서 단어 조각을 찾기 위해 루프를 돈다.
        # 단어 조각은 5 이하기 때문에 마지막까지 자를 필요는 없다.
        for j in range(1, min(i + 1, 6)):
            start = i - j
            end = i
            # 단어 조각이 있다면
            if t[start:end] in strs:
                # 이전 조합과 더해서 최솟값인지 체크 후 대입한다.
                dp[i] = min(dp[i], dp[i - j] + 1)

    # 결과적으로 단어의 최솟값을 구할 수 있다. 만약 무한이라면 불가능한 조합이기 때문에 -1을 리턴한다.
    return -1 if dp[-1] == float('inf') else dp[-1]

비트 마스크

이진법 성질을 이용하여 문제를 해결하는 방법

이진수가 자료구조로 사용된다. 배열 대신 이진수를 이용할 수 있다. 굉장히 빠르고 메모리 사용량이 적다.

그리디, 동적 계획법 등 다른 알고리즘과 함께 사용할 수 있다.

정수형 범위를 점지 않도록 조심할 것. 연산자 우선 순위에 주의할 것.