데브코스-데이터엔지니어링
힙, 동적계획법, DFS, BFS, PEP8 스타일, Tim Sort
묠니르묘묘
2024. 4. 1. 12:18
데이터 엔지니어링 데브코스 Day 5
- 자료구조 및 알고리즘 풀기 5
🚀 힙(Heap) 대표 문제 : 더 맵게
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville) # 리스트를 힙으로 변환
while scoville[0] < K:
if len(scoville) < 2:
return -1
min1 = heapq.heappop(scoville) # 가장 작은 원소
min2 = heapq.heappop(scoville) # 두번째 작은 원소
new_scoville = min1 + (min2 * 2)
heapq.heappush(scoville, new_scoville)
answer += 1
return answer
🚀 동적계획법 (DP, Dynamic Programming)
- 주어진 최적화 문제를 재귀적인 방식으로 보다 작은 부분 문제로 나누어 부분 문제를 풀어, 이 해를 조합하여 전체 문제의 해답에 이르는 방식
- 알고리즘의 진행에 따라 탐색해야 할 범위를 동적으로 결정함으로써 탐색 범위를 한정할 수 있음
- 동적 계획법도 그리디 알고리즘처럼 최적 부분 구조 조건(Optimal Substructure)를 지닌 중복된 하위 문제들(Overlapping Subproblems)을 분할 정복으로 풀이하는 문제해결 패러다임
📝 대표 문제 : N으로 표현
def solution(N, number):
s = [set() for _ in range(8)]
for i, x in enumerate(s, start=1):
x.add(int(str(N) * i))
for i in range(len(s)):
for j in range(i):
for op1 in s[j]:
for op2 in s[i-j-1]:
s[i].add(op1 + op2)
s[i].add(op1 - op2)
s[i].add(op1 * op2)
if op2 != 0:
s[i].add(op1 // op2)
if number in s[i]:
answer = i + 1
break
else:
answer = -1
return answer
🚀 PEP8 스타일 가이드
- 파이썬 개선 제안서, 파이썬 코드를 어떻게 구상할 지 알려주는 스타일 가이드
- 다른 사람과 원활하게 협업하려면 공통된 스타일 공유 필요
- 일관성 있는 스타일은 나중에 수정하기 쉬움
whitespace
- 한 줄의 문자 길이가 79자 이하여야 함
- 함수와 클래스는 빈 줄 두개로 구분함
- 클래스에서 메서드는 빈 줄 하나로 구분함
- 변수 할당 앞 뒤에 스페이스를 하나만 사용
- 리스트 인덱스, 함수 호출, 키워드 인수 할당에는 스페이스를 사용 X
naming
- 함수, 변수, 속성 : lowercase_underscore , 소문자로만 이루어지고 단어 사이 구분은 _ 으로 함
- 보호(protected) 인스턴스 속성 : _leading_underscore , 언더바로 시작하고 구분은 _ 으로 함
- 비공개(private) 인스턴스 속성 : __double_leading_underscore , 더블 언더바로 시작하고 구분은 _ 로 함
- 클래스와 예외 : CapitalizeWord , 단어의 첫글자들을 대문자로 표시 (Carmel Case)
- 모듈 수준 상수 : ALL_CAPS , 전부 대문자
- 클래스의 인스턴스 메서드에서는 첫번째 파라미터 (해당 객체 참조)의 이름을 self로 지정
- 클래스 메서드에서는 첫 번째 파라미터 (해당 클래스 참조)의 이름을 cls 로 지정
표현식과 문장
- if no a is b 보다는 if a is not b 를 사용
- if not somelist 처럼 빈 값은 암시적으로 False가 된다고 가정
- if somelist 처럼 값이 있는 리스트는 암시적으로 True가 된다고 가정
- 한 줄로 된 if문, for, while loop, except 복합문을 쓰지 않음
- 항상 파일의 맨 위에 import 문을 놓음
- 모듈 임포트시에는 항상 모듈의 절대 이름을 사용 import foo 대신 from bar import foo
- 상대적인 임포트를 해야 한다면 명시적인 구문을 서서 from . import foo 라고 함
- import 순서 : 표준 라이브러리 모듈 → 서브파티 모듈 → 자신이 만든 모듈 / 각각의 하위 섹션에서는 알파벳 순서
🚀 Tim Sort
- Tim Sort의 갤로핑 모드(Galloping Mode) 덕분에 배상 비용 최소화 문제에서 sort를 써도 통과 가능
- 평균적으로 느린 정렬 알고리즘 : Bubble Sort, Insertion Sort
- 평균적으로 빠른 정렬 알고리즘 : Heap Sort, Merge Sort, Quick Sort
시간 복잡도가 O(n log n)이라는 말은 실제 동작 시간은 C * n log n + a 라는 의미이다.
C라는 상수가 곱해져 있어서 이 값에 큰 영향을 끼치는 요소로 '알고리즘이 참조 지역성(Locality of Reference) 원리를 얼마나 잘 만족하는가?' 가 있음.
참조 지역성 원리란, CPU가 미래에 원하는 데이터를 예측하여 속도가 빠른 캐시 메모리에 담아 놓는데 이 때의 예측률을 높이기 위해 사용하는 원리
평균적으로 빠른 알고리즘도 상수 C의 값이 너무 커지지 않게 동작하며, 추가 메모리도 많이 사용하지 않고, 최악의 경우 O(n log n)으로 동작하는 정렬 알고리즘이 필요했다.
Tim Sort 등장
- 2002년 소프트웨어 엔지니어 Tim Peters에 의해 등장
- 수많은 종류의 실세계 데이터에 잘 수행하도록 설계된 하이브리드형 안정 정렬 알고리즘
- Insertion Sort + Merge Sort 결합하여 만든 정렬
- Binary Insertion Sort 사용
- 실생활 데이터 특성을 고려하여 최선 O(n), 평균 O(n log n), 최악 O(n log n)
- 파이썬 2.3 이후 버전, Java SE 7, Android, Google chrome V8 등 많은 언어에서 표준 정렬 알고리즘으로 채택되어 사용
- 전체를 작은 덩어리로 잘라 각각의 덩어리를 Insertion Sort로 정렬한 뒤 병합하면 좀 더 빠르지 않을까 하는 것이 기본적인 아이디어
출처 : https://d2.naver.com/helloworld/0315536
🚀 DFS (깊이우선탐색, Depth-First Search)
- 한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하되, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 다음 정점으로 진행
- 스택(Stack)을 이용하여 어느 정점에서 DFS를 하고 있는지를 기억하고 되돌아감
🚀 BFS (너비우선탐색, Breadth-First Search)
- 한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하고, 방문한 각 인접 정점을 기준으로 (방문한 순서에 따라) 또 다시 너비 우선 탐색을 행함
- 큐(Queue)를 이용하여 어느 정점에서 BFS를 해야 하는지를 기록하고 진행
대표 문제 : 여행 경로
from collections import defaultdict
def solution(tickets):
routes = defaultdict(list)
for start, end in tickets:
routes[start].append(end)
for r in routes:
routes[r].sort(reverse=True)
stack = ["ICN"]
path = []
while stack:
top = stack[-1]
if top not in routes or not routes[top]:
path.append(stack.pop())
else:
stack.append(routes[top].pop())
return path[::-1]