260204 [ Day 25 ] - Algorithm 특강

시작하며

오늘은 특강으로 알고리즘에 대한 내용들과 코딩 테스트에 관한 내용을 배워보았다.

알고리즘 효율성

• 알고리즘의 효율성 평가
  • 단순 실행 시간으로 평가하기엔, 환경(컴퓨터 성능)에 의존적
• 시간 복잡도(Time Complexity)
  • 입력 크기가 커질수록 알고리즘의 연산량 증가를 대략적인 수식으로 표현
• Big O Notation
  • 시간 복잡도를 표현하는 방법 중 하나
  • 알고리즘의 효율성은 최악의 경우를 가정하는 것이 유리
  • 의도적으로 상한선을 표기
    • 알고리즘이 최대 어느 정도까지 나빠질 수 있는지

Big O	의미
$O(1)$	입력 크기와 상관없이 항상 일정
$O(n)$	입력이 2배 → 시간도 2배
$O(n^2)$	입력이 2배 → 시간은 4배(비효율적)
$O(\log n)$	입력이 커져도 아주 천천히 증가(효율적)

알고리즘 효율성
$O(1) < O(\log n) < O(n) < O(m \log n ) < O(n^2) < O(2^n)$

ArrayList / LinkedList

ArrayList

• 정의
  • 연속된 메모리공간을 사용하는 동적배열 기반 리스트 자료구조
    • 메모리에 저장된 값 사이의 빈공간X
    • 동적배열 : 리스트의 길이가 자동으로 확장되는 것
  • 각 원소에 순서대로 index 할당(원소 간 빈공간 허용X)
• 참조 = $O(1)$
  • 인덱스를 통해 해당 원소에 바로 접근 가능
  • 높은 참조 효율성
• 삽입/삭제 = $O(n)$
  • 삽입 : 삽입 공간을 만들기 위해 이후 원소들을 한 칸씩 미룸
  • 삭제 : 삭제 공간을 메우기 위해 이후 원소들을 한 칸씩 당김
  • 낮은 삽입/삭제 효율성

LinkedList

• 정의
  • 포인터 기반 리스트 자료구조
  • 각 원소는 “노드”형태로 저장
  • (1)값과 (2)다음(이전) 노드를 참조하는 포인터를 가짐
• 참조 = $O(n)$
  • 특정 위치의 노드에 접근하기 위해, 시작부터 순차적으로 포인터를 이동
  • 낮은 참조 효율성
• 삽입/삭제
  • 삽입 : 노드(i - 1)의 포인터가 신규노드를 참조하도록 수정
  • 삭제 : 노드(i - 1)이 노드(i + 1)를 향하도록 수정
  • 효율성 = $O(1)$ or $O(n)$
    • 삽입/삭제할 위치의 포인터를 아는 경우 $O(1)$
    • 모르는 경우 $O(n)$
• Doubly Linked List
  • 이전 노드를 참조하는 포인터도 저장
  • 실질적으로 많이 사용하는 형태

ArrayList / LinkedList 효율성 비교

	ArrayList	LinkedList
인덱싱	$O(1)$	$O(n)$
삽입, 삭제(끝)	$O(1)$	$O(1)$
삽입, 삭제(시작)	$O(n)$	$O(1)$
삽입, 삭제(중간)	$O(n)$	$O(1)$ / $O(n)$
메모리 효율	보통	비교적 낮음

Stack / Queue

Stack

• LIFO(Last In, First Out) : 가장 마지막(최신) 데이터부터 접근
• 주요 연산
  • push(x) : 마지막에 원소 삽입
  • pop() : 마지막 원소 추출
  • peek() : 마지막 원소 조회
• 적합한 자료구조 → ArrayList

Queue

• FIFO(First In, First Out) : 가장 오래된 데이터부터 접근
• 주요 연산
  • enqueue(x) : 마지막에 원소 삽입
  • dequeue() : 첫번째 원소 추출
  • peek() : 첫번째 원소 조회
• 적합한 자료구조 → LinkedList

정리

	Stack	Queue
규칙	LIFO	FIFO
구현	ArrayList (LinkedList 도 가능)	LinkedList
주요함수(삽입)	push - 마지막에 원소 삽입 $O(1)$	enqueue - 마지막에 원소 삽입 $O(1)$
주요함수(추출)	pop - 마지막 원소 추출 $O(1)$	dequeue - 첫번째 원소 추출 $O(1)$

코드 구현

• Stack - ArrayList

stack = [0, 10, 5, 7, 20, 9] # ArrayList

stack.append(3) # PUSH
# [0, 10, 5, 7, 20, 9, 3]
_ = stack.pop() # POP
# 3 [0, 10, 5, 7, 20, 9]

• Stack - LinkedList

from collections import deque

vals = [0, 10, 5, 7, 20, 9]

stack = deque(vals) # LinkedList
# deque([0, 10, 5, 7, 20, 9])
stack.append(3) # PUSH
# deque([0, 10, 5, 7, 20, 9, 3])
_ = stack.pop() # POP
# 3 deque([0, 10, 5, 7, 20, 9])

• Queue - LinkedList

q = deque(vals)
# deque([0, 10, 5, 7, 20, 9])
q.append(3) # enqueue
# deque([0, 10, 5, 7, 20, 9, 3])
_ = q.popleft() # dequeue
# 0 deque([10, 5, 7, 20, 9, 3])

PriorityQueue

PriorityQueue가 필요한 상황

• 적재 순서가 아닌 값의 크기를 기준으로 추출 우선순위를 정하고 싶을 때
• 최대값(최솟값) 탐색이 빈번히 발생하는 상황
  • 일반 리스트에서의 최대/최소 탐색 효율은 $O(n)$

Heap

• 정의
  • 계층간 대소관계가 있는 완전 이진트리
  • PriorityQueue를 표현하는데 가장 적합
• 완전이진트리
  • Leaf 노드를 제외한 모든 노드는 2개의 자식 노드를 가짐
  • 왼쪽 → 오른쪽 방향으로 채움
• 종류
  • MaxHeap : 부모노드의 크기 ≥ 자식노드의 크기
  • MinHeap : 부모노드의 크기 ≤ 자식노드의 크기

PriorityQueue 주요 연산

• enqueue(x)
  • 신규 노드(x)를 가장 마지막에 추가한 후 올바른 자리로 이동
  • $O(\log_2n)$
• dequeue()
  • 루트 노드를 삭제하여 리턴
  • 가장 마지막 노드를 루트 노드로 이동시킨 후 올바른 자리로 이동
  • $O(\log_2n)$
• find()
  • 가장 큰/작은 원소 조회
  • root node 조회이므로 연산량 X
  • $O(1)$

import heapq # minHeap

init_list = [10, 30, 20, 60, 40, 0]
heapq.heapify(init_list)
# [0, 30, 10, 60, 40, 20]

# peek (루트노드 참조)
_ = init_list[0]
# 0

# dequeue (루트 노드를 추출)
_ = heapq.heappop(init_list)
# 0 [10, 30, 20, 60, 40]

# enqueue (새로운 노드를 추가)
heapq.heappush(init_list, 100)
# [10, 30, 20, 60, 40, 100]

heapq.heappush(init_list, 5)
# [5, 30, 10, 60, 40, 100, 20]

# print(_, init_list)
print(init_list)

HashTable

Hash

• 특정 값을 특정 인덱스로 매핑하는 고정된 규칙
  • 같은 입력에 대해서는 항상 같은 출력
  • 입력이 다르다면 출력 또한 다름이 보장

HashTable

• hash 값을 인덱스로 사용하는 배열
• $O(1)$

탐색 알고리즘

Linear Search(선형 탐색)

• 시작부터 끝까지 순차적으로 순회하며 값을 탐색
• $O(n)$

Binary Search(이진 탐색)

• 절반씩 범위를 좁혀가며 탐색하는 방식
  • 정렬된 리스트에서만 사용 가능
• $O(\log_2n)$

a = [i + 1 for i in range(100)]

# 탐색 함수 구현
TARGET_VAL = 23
FOUND = False # flag

left, right = 0, len(a) - 1 # 가장 왼쪽과 오른쪽 인덱스

while left <= right:
    mid = (left + right) // 2 # 중심 인덱스
    print('현재 인덱스 :', mid, '/', '값 :', a[mid])

    if a[mid] == TARGET_VAL:
        print('찾았습니다!')
        FOUND = True
        break
    elif a[mid] < TARGET_VAL: # up
        left = mid + 1
    else: # down
        right = mid - 1

if not FOUND:
    print('타겟값이 해당 리스트에 없습니다.')
# 현재 인덱스 : 49 / 값 : 50
# 현재 인덱스 : 24 / 값 : 25
# 현재 인덱스 : 11 / 값 : 12
# 현재 인덱스 : 17 / 값 : 18
# 현재 인덱스 : 20 / 값 : 21
# 현재 인덱스 : 22 / 값 : 23
# 찾았습니다!

Graph Traversal Algorithm

그래프 구조에서의 데이터 탐색

• 이전까지는 값들이 일렬로만 놓이는 구조 위에서 탐색
• 일렬이 아닌 여러 분기로 갈리는 경우 별도의 탐색 알고리즘 필요

Graph Traversal Algorithm

• 그래프 구조(노드들이 연결된 구조)에서 모든 노드를 빠짐없이 방문하는 방법
• DFS
  • 구체적인 경로(패턴)까지 모두 추출해야 되는 경우에 사용
• BFS
  • 빠르게 탐색을 해야 된느 경우에 사용
• 보통의 경우에 DFS가 BFS보다 더 쉽고 구현하게 편함

DFS (Depth-First Search) = 깊이 우선 탐색

• 정의
  • 특정 방향을 끝까지 파고드는 방식
  • 막히면 돌아와서 다른 방향 선택
• 구현
  • Stack
  • 재귀함수

BFS (Breath First Search) = 넓이 우선 탐색

• 정의
  • 깊이 이동 전에 가까운 노드부터 모두 탐색
  • 먼저 발견한 노드들 부터 먼저 처리
• 구현
  • Queue

정렬 알고리즘

Selection Sort

• 구간 내 최솟값을 가장 앞으로 이동시키는 것을 반복
• $O(n^2)$

Insertion Sort

• 순차적으로 각 원소를 정렬된 위치로 이동
• $O(n^2)$

Bubble Sort

• 인접한 두 원소를 교환시키며 순차적으로 정렬 상태를 만듦
• $O(n^2)$

Divide & Conquer

• 큰 문제를 하위 문제로 쪼개어 나누어 푸는 기법
  • 더 효율적인 풀이가 가능해짐

Merge Sort

• Divide
  • 전체 리스트를 재귀적으로 절반씩 분리
• Conquer
  • 리스트 길이가 1이 되면 분리를 멈춤
• Combine
  • 쪼개진 리스트들을 다시 합치는 과정에서 정렬 수행
• 시간 복잡도 : $O(n \log_2n)$
• 특징
  • 안정성 : $O(n \log_2n)$ 항상 보장
  • 공간 비효율성 : 메모리 추가 사용

Quick Sort

• Divide
  • 랜덤 원소를 Pivot으로 설정
  • Pivot 보다 작은값, 큰값들을 각각 left, right로 분할
• Conquer
  • 리스트 길이가 1이하일 경우 분할을 멈춤
• Merge
  • left + pivot value + right
  • 분할 과정에서 이미 정렬이 이루어졌기 때문에 추가 정렬 작업X
• 시간 복잡도 : 평균적으로 $O(n \log_2n)$
• 특징
  • 평균적으로 매우 빠름
  • 최악의 경우 $O(n^2)$

정렬 알고리즘 성능 비교

이름	최선	평균	최악	메모리	안정
Bubble Sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	O
Insertion Sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	O
Merge Sort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	O
Quick Sort	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(n \log n)$	X

마치며

알고 있던 내용도 있고 처음 듣는 내용과 개념들도 많았다. 그냥 재미로만 풀던 알고리즘 문제들을 더 효율적이고 성능 좋게 만드는 방법들과 여러 문제들에 대한 유형을 알게 되어 많은 도움이 될 것 같고, 빨리 응용해서 복잡한 문제를 풀어보고 싶은 마음이 생겼다.