from collections import deque
queue = deque()
queue.append(5) # push
queue.append(3)
queue.popleft() # pop
queue.append(2)
print(queue) # [3, 2]
python에서 queue는 deque을 사용해서 구현한다.
삽입: append(요소) # O(1)
삭제: popleft() # O(1)
deque은 내부적으로 연결 리스트로 구현이 되어 있다.
따라서 삽입, 삭제가 O(1)으로 가능하다.
단 random access가 불가능하기에, 요소 접근에는 O(N)이 소요된다.
재귀 함수 Recursive Fuction
출처: inDepth.dev
재귀 함수란? 자기 자신을 다시 호출하는 함수.
재귀 함수는 반복문으로 동일하게 구현이 가능하다. 역도 그렇다.
코드의 길이는 짧아지지만, 인간에게 직관적이지 않으므로 신중하게 사용해야 한다.
문제 풀이에 활용하려면 종료 조건을 반드시 명시해야 한다.
종료 조건 없이 함수가 무한히 호출되면, stack overflow가 발생하기 때문.
import sys
sys.setrecursionlimit(10 ** 5)
python3는 기본적으로 재귀 깊이를 1,000으로 제한해 놓았다.
그러나 문제를 풀다보면 이 제한을 해제해야 하는 경우가 있다.
sys.setrecursionlimit()으로 이 제한을 늘려주자
재귀 깊이가 29945를 넘어가면 에러 발생
직접 해본 결과 재귀 깊이가 29945를 넘어가면, segmentation fault 에러가 발생한다.
프로그램이 메모리를 잘못 액세스 했을 때 발생하는 오류로, stack overflow를 원인으로 발생하는 오류 중 하나이다.
정해진 메모리 공간을 넘어가면, 다른 데이터를 건드릴 수 있기에 이를 방지하기 위한 에러이다.
실전에서는 재귀 깊이 제한을 10 ** 5 정도로 설정한 뒤에, 종료 조건을 반드시 작성하자.
예시1. 팩토리얼
def factorial_recursive(n)
if n <=1 :
return 1
return n * factorial_recursive(n - 1)
# 0! == 1
# 1! == 1
예시2. 유클리드 호제법
def gcd(a, b)
if a % b == 0 :
return b
else :
return gcd(b, a % b)
# 성질: a와 b의 나머지가 r이라면, a와 b의 최대 공약수 == b와 r의 최대 공약수
# a, b의 대소 관계와 상관없이 동작한다.
DFS (Depth First Search)
출처: GeeksforGeeks
정의
깊이 우선 탐색.
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.
뼈대
def dfs(graph, v, visited):
visited[v] = True # 현재 노드 방문 처리
print(v, end = " ") # 방문한 노드를 순서대로 출력
for i in graph[v]: # 인접한 노드를 모두 확인
if not visited[v]: # 방문하지 않은 노드가 있다면
dfs(graph, i, visited) # 재귀적으로 탐색
스택 혹은 재귀 함수를 이용한다.
탐색 시작 노드를 스택에 삽입 / 방문 처리
스택 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접한 노드가 없으면 스택 최상단 노드 꺼냄.
2번 과정을 수행할 수 없을 때 까지 반복
BFS (Breadth First Search)
출처: GeeksforGeeks
정의
너비 우선 탐색.
가까운 노드부터 우선적으로 탐색하는 알고리즘.
뼈대
from collections import deque
def bfs(graph, start, visited):
queue = deque([start]) # deque에 시작 노드를 추가해서 초기화
visited[start] = True # 현재 노드 방문 처리
while queue: # 큐가 빌 때까지 반복
v = queue.popleft() # 가장 먼저 들어온 노드를 제거 # 처음에는 시작 노드
print(v, end = " ") # 순서대로 출력
for i in graph[v]: # 인접한 노드를 모두 확인
if not visited[i]: # 방문하지 않은 노드가 있다면
queue.append(i) # 큐에 추가하고
visited[i] = True # 방문 처리
큐를 이용한다.
탐색 시작 노드를 큐에 삽입 / 방문 처리
큐에서 노드 꺼내고 해당 노드의 인접 노드 중에서, 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
정당성 분석이 선행되어야 한다. --> 단순하게 가장 좋아보이는 것만 선택하면, 최적의 해를 구할 수 있는지?
실제로 유형을 모른 채로 문제를 만났을 때, 그리디 알고리즘을 사용해야 하는 근거는 다음과 같다.
1. 문제의 구조:
최적 부분 구조: 작은 문제의 최적 해결책이, 전체 문제에도 적용될 수 있어야 함.
2. 선택의 기준:
탐욕적: 현재 정보에 한해, 제일 좋은 것을 선택.
단기적: 각 선택은 현재 정보만을 기반으로 이루어짐. 이전 혹은 미래의 선택을 고려하지 않음.
불가역적: 선택이 이루어지고 나면, 이후의 과정에서 그 선택을 되돌릴 수 없음. 모든 선택은 최종 선택임.
1. 거스름 돈
큰 단위가 항상 작은 단위의 배수이므로 최적의 해를 보장한다. 예: [500, 400, 100]이라면, 큰 단위(500)가 작은 단위(400)의 배수가 아니므로, 그리디를 적용할 수 없다.
2. 1이 될 때까지
1빼기 보다, 나누기를 많이 하는 것이 대부분의 상황에서 유리하다.
현재 값이 2이상이면 나누는 것이 1 빼는 것보다 빠르게 조건을 달성할 수 있으니까.
n, k = map(int, input().split())
result = 0
while True:
target = (n // k) % k # n과 가장 가까우면서 작은 k로 나누어 떨어지는 수
result += (n - target) # 어차피 1씩 빼면서 target까지 가야한다. 그것을 한 번에.
n = target # 1씩 빼서 target까지 도착했다고 치고
if n < k: # 나누는 수보다 작아지면 탈출
break
result += 1
n //= k # while을 한 번 반복할 때마다, k로 한 번씩 나누는 셈
result += (n - 1) # 더 이상 나눌 수 없는 상태이므로, 1씩 빼서 1에 도착할 때까지 횟수
print(result)
3. 곱하기 혹은 더하기
피연산자가 1 또는 0이 아니라면 항상 곱하기가 유리하다.
4. 모험가 길드
배열을 정렬하고, 작은 값부터 임시 그룹에 추가하며, 조건을 만족하는 즉시 마을을 떠나면 최적의 해를 구할 수 있다.
그리디 알고리즘을 적용해야 하는지 헷갈릴 수 있다.
그리디 알고리즘 선택 근거를 다시 생각해보자.
1. 문제의 구조: [1]인 경우와 [1, 2, 3]인 경우, 모두 같은 풀이를 적용할 수 있다.
2. 선택의 기준: [1]인 경우와 [1, 2, 3]인 경우, 탐욕적으로 선택해도 최적의 해가 나온다. 각 선택은 단기적이고 불가역적이다.
구현
chatGPT가 생각하는 구현
정의
풀이를 떠올리는 것은 쉽지만 소스 코드로 옮기기 어려운 문제
알고리즘은 간단한데 코드가 지나칠 정도로 길어짐
실수 연산을 다루고, 특정 소수점 자리까지 출력해야 함
문자열을 다룸
적절한 라이브러리를 찾아서 사용해야 함
1. 상하좌우
방향 벡터를 사용한 문제.
행렬의 시작 부분인 (0, 0)이 좌상단 임을 기억할 것.
2. 시각
h = int(input())
count = 0
for i in range(h + 1):
for j in range(60):
for k in range(60):
if "3" in str(i) + str(j) + str(k): # 이렇게 하면 쉽다.
count += 1
print(count)
완전 탐색.
하루는 86,400초이므로 완탐을 하기에 무리 없다.
파이썬은 1초에 2,000만 번 정도 연산을 수행할 수 있다고 생각하기.
3. 왕실의 나이트
8방향 벡터.
4. 문자열 재정렬
data = input()
result = []
value = 0
for x in data:
if x.isalpha(): # 문자면 True 아니면 False # isNumeric()도 있음
result.append(x)
else:
value += int(x)
result.sort()
if value != 0: # 숫자가 없을 경우 표시하면 안 되니까
result.append(str(value))
print("".join(result)) # 리스트의 원소를 합쳐서 문자열로 만드는 방법
