[정글] WEEK02 - WIL : 컴퓨팅사고로의 전환 2

WEEK02 - 컴퓨팅사고로의 전환 2

이번 2주차에는 이분탐색 분할정복법 스택 큐 우선순위큐 에 대한 내용들을 공부하고 관련 문제들을 풀어보았다. 간단하게 개념 및 구현코드로 정리해보려고 한다.

이분탐색 (Binary Search)

정렬되어있는 리스트에서 원하는 값을 빠르게 찾기 위한 알고리즘으로, 리스트를 절반으로 나누고 중간에 위치한 값과 원하는 값을 비교하여 범위를 좁혀가는 과정으로 진행된다.

# while문 활용
def binary_search(arr, key) :
    left = 0
    right = len(arr) - 1
    

    while True :
        chk_idx = (left + right) // 2
        if arr[chk_idx] == key :
            return chk_idx
        if arr[chk_idx] > key :
            right = chk_idx-1
        else :
            left = chk_idx+1
        if left > right : return -1
        
        
# 재귀 적용
def binary_search_recul(arr, key, left, right) :
    chk_idx = (left + right) // 2
    if arr[chk_idx] == key : return chk_idx
    if arr[chk_idx] > key :
        if left > chk_idx-1 : return -1
        return binary_search_recul(arr, key, left, chk_idx-1)
    else :
        if chk_idx+1 > right : return -1
        return binary_search_recul(arr, key, chk_idx+1, right)

분할정복법 (Devide and Conquer)

문제를 2개 이상의 작은 문제로 분할하고 작은 문제들을 해결함으로써 큰 문제를 정복해내는 방법이다.
대표적인 한가지 예로 A의 N제곱을 구한다고 하면, A의 N/2제곱을 먼저 구한 뒤 이를 제곱함으로써 최종 결과를 얻을 수 있다.

# A의 B제곱을 구하는 함수
def cal(A,B) :
	# B가 1이라면 A 그대로 반환
    if B == 1 :
        return A
    # B가 짝수라면 A의 B//2 제곱을 먼저 구한뒤 이의 제곱을 반환
    if B%2 == 0 :
        return (cal(A,B//2) ** 2)
    # B가 홀수라면 A의 B//2 제곱을 먼저 구한뒤 이의 제곱에 A를 곱한 값을 반환
    else :
        return (cal(A,B//2) ** 2) * A

print(cal(A,B,C))

스택 (Stack)

마지막에 저장한 값을 먼저 빼내는 후입선출(LIFO: Last In First Out) 방식의 자료구조이다.
리스트의 append / pop으로 간단하게 구현할 수 있다.

# 리스트의 가장 오른쪽에 데이터를 추가
list.append()
# 리스트의 가장 오른쪽 데이터를 반환하고 제거
list.pop()

큐 (Queue)

먼저 저장한 값을 먼저 꺼내는 선입선출(FIFO: First In First Out) 방식의 자료구조이다.
리스트와 포인터를 사용한 class를 정의하여 구현할 수 있으며, deque 라이브러리를 사용하여 간단하게 구현할 수도 있다.

from collections import deque
que = deque()
# 큐의 오른쪽에 데이터 삽입
que.append(data)
# 큐의 가장 왼쪽에 있는 데이터를 반환하고 제거
que.leftpop()

우선순위큐 (Priority Queue)

가장 크거나 작은 값을 먼저 꺼내는 방식의 자료구조이다.
heapq 라이브러리를 사용하여 구현할 수 있다.

import heapq
heapq.heapify(list)
# 데이터를 리스트에 최소힙 방식으로 추가
heapq.heappush(list,data)
# 리스트에서 최소값을 반환 후 제거
heapq.heappop()

heapq는 최소힙으로 구현되어있어 최대힙으로 사용하려면 -를 붙여주면 된다.

# 데이터를 리스트에 최소힙 방식으로 추가 - (-를 넣었기 때문에 pop하고 -를 붙이면 최대힙이 됨)
heapq.heappush(list,-data)
# 리스트에서 최소값을 반환 후 제거
-heapq.heappop()

정리

이번 주차에는 자료구조를 어떻게 잘 활용할 수 있을지 생각해볼 수 있었다.
문제들을 그냥 해결하려고 달려들면 어떤 개념을 어떻게 적용해야할지 감이오질 않았다.
하여 문제를 파악할 때, 어떤 자료구조와 어떤 알고리즘이 필요할지 문제정의를 잘 하고 접근해야겠다고 느꼈다.