[백준] 힙, 재귀함수_11866, 1927, 11286, 5430, 10870, 17478, 1914, 11729

요세푸스 문제 0

• 코드

from collections import deque

n, k = map(int,input().split())
arr = [i for i in range(1,n+1)]
q = deque(arr)
print("<",end="")

while q:
    for i in range(k-1):
        q.append(q[0])
        q.popleft()
    print(q.popleft(),end='')
    
    if q:
        print(", ",end='')
print(">")

• 풀이를 생각해낸 과정
  • 풀이 참고
• 시간복잡도 계산

최소 힙

• 코드

import heapq
import sys
input = sys.stdin.readline

n = int(input())
heap = []

for i in range(n):
    k = int(input())
    if k == 0:
        if len(heap)==0:
            print(0)
        else:
            print(heapq.heappop(heap))
    else:    
        heapq.heappush(heap,k)

• 풀이를 생각해낸 과정
  • heapq를 이용하여 최소 힙 구현
  • heapq.heappop(heap) : 가장 작은 원소 제거
  • heapq.heappush(heap,k) : heap에 k 값을 넣기
• 시간복잡도 계산
  • O(log2n)

절대값 힙

• 코드

import heapq
import sys
input = sys.stdin.readline
n = int(input())

heap = []

for i in range(n):
    k = int(input())
    
    if k == 0:
        if len(heap) == 0:
            print(0)
        else:
            print(heapq.heappop(heap)[1])
    else:
        heapq.heappush(heap,(abs(k),k))

• 풀이를 생각해낸 과정
  • 풀이 참고
  • heappush를 할 때 튜플로 힙에 넣을 수 있다.
    • 튜플의 왼쪽은 비교 대상이 되고, 오른쪽은 실제 값을 넣어서 비교할 수 있다.
• 시간복잡도 계산
  • O(log2n)

AC

• 코드

from collections import deque
 
t = int(input())
 
for i in range(t):
    p = input()
    n = int(input())
    arr = input()[1:-1].split(',')
 
    queue = deque(arr)
 
    flag = 0
 
    if n == 0:
        queue = []
 
    for j in p:
        if j == 'R':
            flag += 1
        elif j == 'D':
            if len(queue) == 0:
                print("error")
                break
            else:
                if flag % 2 == 0:
                    queue.popleft()
                else:
                    queue.pop()
 
    else:
        if flag % 2 == 0:
            print("[" + ",".join(queue) + "]")
        else:
            queue.reverse()
            print("[" + ",".join(queue) + "]")

• 풀이를 생각해낸 과정
  • R의 연속 여부를 확인하여 연산을 줄여야 시간 초과가 나지 않는다.
  • n = 0 일때 따로 처리
  • for ~ else문 : for문과 같이 사용되는 else문은 for문이 break 등으로 중간에 빠져나오지 않고 끝까지 실행 됐을 경우 else문이 실행되는 방식
  • flag를 이용하여 R의 연속 여부를 확인한다.
• 시간복잡도 계산

피보나치 수 5

• 코드

n = int(input())

dp = [0] * (n+1)

if n !=0 :
    dp[1] = 1

for i in range(2, len(dp)):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n])

• 풀이를 생각해낸 과정
  • dp를 이용하여 계산
  • n이 0인 경우 dp[1]을 넣을 수 없으므로 따로 처리 → 안해주면 런타임 에러
• 시간복잡도 계산
  • O(N)

재귀함수가 뭔가요?

• 코드

def recursive(m):
    print("_" * (4 * (n - m)) + '"재귀함수가 뭔가요?"')

    if not m:
        print("_" * (4 * (n - m)) + '"재귀함수는 자기 자신을 호출하는 함수라네"')
        print("_" * (4 * (n - m)) + "라고 답변하였지.")
        return

    print("_" * (4 * (n - m)) + '"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.')
    print("_" * (4 * (n - m)) + "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.")
    print("_" * (4 * (n - m)) + '그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."')
    recursive(m - 1)
    print("_" * (4 * (n - m)) + "라고 답변하였지.")

n = int(input())
print("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.")
recursive(n)

• 풀이를 생각해낸 과정
  • n부터 0까지 재귀 함수를 호출한다.
  • 0일 때 "재귀함수는 자기 자신을 호출하는 함수라네" 출력
• 시간복잡도 계산

하노이 탑

• 코드

def f(n, start, end, sub):
    if(n == 1):
        print(start, sub, sep = " ")
    else:
        f(n-1, start, sub, end)
        f(1, start, end, sub)
        f(n-1, end, start, sub)

n = int(input())
print(2**n-1)
if(n <= 20):
  f(n, 1, 2, 3)

• 풀이를 생각해낸 과정
  • 참고 : https://mgyo.tistory.com/185
• 시간복잡도 계산

하노이 탑 이동 순서

• 코드

def f(n, start, end, sub):
    if(n == 1):
        print(start, sub, sep = " ")
    else:
        f(n-1, start, sub, end)
        f(1, start, end, sub)
        f(n-1, end, start, sub)

n = int(input())
print(2**n-1)
if(n <= 20):
  f(n, 1, 2, 3)

• 풀이를 생각해낸 과정
• 시간복잡도 계산