오늘은 더 힘내보려고 한다.
오늘 배운 것들
1. 재귀 함수
재귀함수에 대해 추가적으로 공부한 것들을 정리해보려고 한다.
1-1. 재귀함수의 장점
- 상태를 저장하기 위한 변수를 만들지 않아도 된다. 예: 팩토리얼을 반복문으로 구현하면 곱셈 상태를 변수에 저장해야 하지만, 재귀함수로 구현하면 변수를 별도로 생성하지 않아도 된다.
- 작업을 마트료시카처럼 동일한 형태의 부분으로 나눌 수 있는 문제의 경우 간단한 코드로 구현할 수 있다.
1-2. 재귀함수의 단점
- 재귀가 종료될 때까지 함수 스택을 계속 차지하기 때문에 스택오버플로우의 가능성이 있다.
- 오버플로우가 되지 않더라도 재귀호출에 따른 공간 생성 및 컨텍스트 전환을 위해 시간을 잡아먹어 실행속도가 느려질 수 있다.
꼬리 재귀를 지원하는 경우 꼬리 재귀를 사용하면 재귀호출 전 기존 함수가 차지하던 메모리를 제거하기 때문에 1의 문제는 해결될 수 있다. 단 파이썬은 아직 꼬리 재귀를 지원하지 않는다고 한다.
2. 분할 정복
분할 정복은 반대로 큰 문제들을 분할하여 작은 문제를 해결하면 큰 문제가 해결되도록 하는 방식이다.
'작은' 문제란 답을 쉽게 내릴 수 있는 문제를 말한다.
앞서 배웠던 하노이 탑 문제도 (n-1층의 탑을 옮기는 방법)+(1개의 판을 옮기는 방법)으로 계속 분할하다 (답이 쉽게 나오는)2층의 탑까지 나눴으므로 분할 정복의 일종이라고 볼 수 있을 것 같다.
작은 문제만 해결하면 큰 문제는 자연히 해결되도록 하는 만큼 문제가 단순해지지만,
상태를 계속 쌓아두어야 하므로 메모리 관리가 큰 단점.(대처법으로는 캐시가 있다)
효율이 떨어질 가능성도 크다.
'작은' 문제를 어떻게 정의할 것이냐에 대한 고민도 필요하다.
그럼에도 직관적으로 접근할 수 있는 것이 큰 장점인 것 같다.
2-1. 색종이 만들기(백준 2630번)
import sys
N :int = int(sys.stdin.readline())
PAPER :list = [[int(a) for a in sys.stdin.readline().split()] for _ in range(N)]
def main() -> None:
# 색종이가 한가지 색으로 이루어졌으면 색깔(0또는1)을, 아니면 -1을 반환
def _check_papers(row :int, col :int, width :int) -> int:
total_std = sum(PAPER[row][col:col+width])
if total_std != width and total_std!=0:
return -1
for i in PAPER[row+1:row+width]:
total = sum(i[col:col+width])
if total!=total_std:
return -1
return total_std//width
# 색종이를 4등분해 시작 인덱스를 반환
def _cut_papers(row :int, col :int, width :int) -> list[tuple]:
new_width = width//2
return [(row, col), (row+new_width, col), (row, col+new_width), (row+new_width, col+new_width)]
# 한 가지 색으로 구성된 색종이라면 n_papers에 색깔 별 개수를 추가
# 아니라면 4등분 하고 다시 색종이별로 판별
def _make_papers(row :int, col :int, width :int) -> None:
paper = _check_papers(row, col, width)
if paper != -1:
n_papers[paper] += 1
else:
for i, j in _cut_papers(row, col, width):
_make_papers(i, j, width//2)
n_papers = [0, 0]
_make_papers(0, 0, N)
print(n_papers[0])
print(n_papers[1])
main()색종이를 한 가지 색만 갖도록 십자로 4분할 하는 문제이다.
최대 N이 크지 않아 직관대로 구현하면 쉽게 풀린다.
2-2. 곱셈(백준 1629)
단순히 A의 B제곱수를 C로 나눈 나머지를 구하는 문제.
A, B, C < 2^31이기 때문에 A**B % C를 제출하는 것을 참는 것이 포인트이다.
import sys
A, B, C = [int(a) for a in sys.stdin.readline().split()]
def main() -> None:
def _find_remainder(A :int, B :int, C :int) -> int:
B_half = B//2
if B_half in cache:
left = cache[B_half]
else:
left = _find_remainder(A, B_half, C)
if B-B_half in cache:
right = cache[B-B_half]
else:
right = _find_remainder(A, B-B_half, C)
quotient = (left*right)%C
cache[B] = quotient
return quotient
cache = {0: 1,
1: A%C}
print(_find_remainder(A, B, C))
main()모든 자연수는
꼴로 표현할 수 있다.
일 때
꼴로 나타낼 수 있으므로
을 만족하는 자연수 z가 존재한다!
사실상 수학 문제.
반복문을 쓴다면 몫은 이미 B의 배수이기 때문에 나머지만을 캐시하며 돌리면 되겠지만
N 제한이 무지막지하게 크기 때문에 시간복잡도를 고려해야 한다.
A가 q_A B + r로 표현될 수 있음을 떠올린다면 답을 찾을 수 있다.(깨닫고 나서는 무릎을 탁 쳤다. 근데 이게 실버라고..?)
인 A^B를 A^(B/2) A^(B/2)로 나누는 분할 정복 알고리즘을 사용하였다.
속도를 높이기 위해 캐시를 사용하였다.
알고리즘 분류에 분할정복이라고 써있지 않았으면 못 풀었을 것 같다.
힌트 없이 풀 실력은 언제 달성할 수 있을까
3. 스택과 큐
3-1. 탑(백준 2493)
import sys
N = int(sys.stdin.readline())
A = [int(i) for i in sys.stdin.readline().split()]
class Stack:
def __init__(self) -> None:
self.data = []
self.index = []
self.last = None
def push(self, data :int, index :int) -> None:
self.data.append(data)
self.index.append(index)
self.last = data
def pop(self) -> tuple[int | None]:
if self.data and self.index:
if len(self.data)>1:
self.last = self.data[-2]
else:
self.last = None
return self.data.pop(-1), self.index.pop(-1)
else:
return None, None
def main() -> None:
stack = Stack()
answer = ['0'] * N
stack.push(A[N-1], N-1)
for i in range(N-2, -1, -1):
while (stack.last is not None) and stack.last <= A[i]:
_, idx = stack.pop()
answer[idx] = str(i+1)
stack.push(A[i], i)
print(" ".join(answer))
main()peek는 .last로 구현
스택은 자연스럽게 정렬된 상태가 된다는게 포인트
스택 개념을 제대로 이해하지 못 했다면 그 포인트를 떠올리기 힘들다.
내가 그랬다.
3-2. 괄호의 값(백준 2504)
import sys
A :list[str] = list(sys.stdin.readline()[:-1])
class Stack:
def __init__(self) -> None:
self.data = []
self.last = None
def push(self, data :str) -> None:
self.data.append(data)
self.last = data
def pop(self) -> str:
if self.data:
if len(self.data)>1:
self.last = self.data[-2]
else:
self.last = None
return self.data.pop(-1)
else:
return None
def main() -> int | None:
# 한 항의 값을 반환하는 함수(단일 괄호인 경우 값을 출력한다.)
def _term(s :str):
stack = Stack()
if s in bracket:
stack.push(s)
else:
return None
term_value = 0
# 스택이 비지 않은 경우(같은 항인 경우)
while stack.last is not None:
# 다음 글자를 가져온다.
if len(A) <= 0:
return None
next = A.pop(0)
# 다음 글자가 열리는 괄호면 덧셈
if next in bracket:
if (term := _term(next)) is None:
return None
else:
term_value += term
# 다음 글자가 닫히는 괄호면 곱셈
else:
pop = stack.pop()
# 근데 이제 알맞게 닫힌 경우에만
if next == bracket[pop]:
if term_value == 0:
term_value = 1
term_value *= bracket_value[pop]
else:
return None
# 이번 항은 끝남
return term_value
bracket = {'(': ')',
'[': ']'}
bracket_value = {'(': 2,
'[': 3}
result = 0
while A:
if (term := _term(A.pop(0))) is None:
result = 0
break
else:
result += term
print(result)
main()대표적인 스택 사용 예시인 괄호 검사에서 곱셈과 덧셈이 추가된 문제.
완성된 괄호를 하나의 항으로 보고 덧셈/곱셈을 할 상황을 구분하면 된다.
(매우)헷갈릴 뿐이지 난이도 자체는 탑보다 쉬운 것 같다.
3-3. 요세푸스 문제 0(백준 11866)
from collections import deque
def josephus_permutation(n, k):
# 1부터 n까지의 숫자를 큐에 넣음
queue = deque(range(1, n + 1))
result = []
while queue:
# k-1개의 요소를 큐의 뒤로 보냄
queue.rotate(-(k-1))
# k번째 요소를 제거하고 결과에 추가
result.append(queue.popleft())
return result
# 예제 사용법
n = 7
k = 3
result = josephus_permutation(n, k)
print("Josephus permutation:", result)큐로 어떻게 해야 할 지 도저히 모르겠어서 GPT의 도움을 받았다.
이렇게 간단할 수가..
큐에 대한 이해가 아직 부족한가보다.
문제를 코드로 번역했을 뿐인 내 답안은 부끄러워 남기지 않는다.
4. 힙
4-1. 최대 힙(백준 11279)
문제는 구현만 하면 된다.
개념이 더 중요하다.(삽입, 삭제의 메커니즘)
소감
오늘은 어제보다 훨씬 보람있었다. 쉽지 않은 문제들을 많이 풀었다.
하지만 단순히 풀고 이해한다고 해서 머리 속에 남아있으리란 법이 없다.
내가 떠올린 생각이라도 정리해 담아두지 않으면 사라진다.
