2024-03-12 AI 코딩 TIL

어제 다 풀지 못했던 문제를 마저 풀었습니다..

피보나치 1

코드가 기본적으로 주어지 때문에 파이썬 방식으로 기입을 하고 카운터를 넣어주면 됩니다.
다만 python3으로 실행하면 시간 초과가 되므로
pypy3로 작동을 해야 하더군요

count1 = 0
count2 = 0


def fib(num):
    global count1
    if num == 1 or num == 2:
        count1 += 1
        return 1  # 코드1
    else:
        return fib(num - 1) + fib(num - 2)


def fibonacci(num):
    global count2
    f = [0] * (num + 1)
    f[1] = f[2] = 1
    for i in range(3, num + 1):
        count2 += 1
        f[i] = f[i - 1] + f[i - 2]  # 코드2
    return f[num]


n = int(input())
fib(n)
fibonacci(n)
print(count1, count2)

 

 

피보나치 2

이 문제는 앞서 풀었던 경험이 있어서 피보나치 단축 방법으로 쉽게 만들었습니다.

def fib(num):
    if num < 2:
        return num
    fib_list = [0, 1]
    for i in range(2, num + 1):
        fib_list.append(fib_list[i - 1] + fib_list[i - 2])
    return fib_list[num]


n = int(input())
print(fib(n))

 

 

1, 2, 3 더하기

이거는 앞 전에 풀었던 문제의 유형
코딩테스트 연습 - 멀리 뛰기 | 프로그래머스 스쿨 (programmers.co.kr)
이거랑 방법이 똑같아서 값만 찾아주면 쉽게 문제를 풀 수 있었던 것 같습니다.

def solution(n):
    if n < 4:
        if n < 3:
            return n
        else:
            return 4
    d = [0] * (n + 1)
    d[1] = 1
    d[2] = 2
    d[3] = 4
    for i in range(4, n + 1):
        d[i] = d[i - 1] + d[i - 2] + d[i - 3]
    return d[n]


# 테스트 반복 !
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    a = int(input())
    result = solution(a)
    print(result)

 

1로 만들기

이 문제는 튜터 님이 알려주신 메모이징? 을 활용하면 쉽게 풀 수 있었습니다 
다만 조건 순서에 따라 작용해야 하다 보니 먼저 3을 나누는 것이 -1을 빼는 것과 2를 나누는 것에 비해 유효한 값인지는 판단하는 기준이 필요 했습니다.  

def make_one(num):
    if num == 1:
        return 0
    count_list = [0, 0]
    for i in range(2, num + 1):
        if i % 3 == 0 and count_list[i // 3] + 1 <= count_list[i // 2] + 1 and count_list[i // 3] + 1 <= count_list[i - 1] + 1:
            count_list.append(count_list[i // 3] + 1)
        elif i % 2 == 0 and count_list[i // 2] + 1 <= count_list[i - 1] + 1:
            count_list.append(count_list[i // 2] + 1)
        else:
            count_list.append(count_list[i - 1] + 1)
    return count_list[num]


n = int(input())
print(make_one(n))

---

그리고 금일 문제 풀이!

카드 2

처음에 재귀 방식으로 했는데 재귀 최대량이 초과 되어 런타임 에러 (RecursionError)
가 발생 하였습니다 그래서 방식을 바꾸어서 while문을  사용 하였습니다.

import sys

# 표준 입력을 파일로 설정
sys.stdin = open("input.txt", "r")

from collections import deque

num = int(input())
queue = deque()
for i in range(1, num + 1):
    queue.append(i)


def card_shuffle(card):
    while len(queue) > 1:
        card.popleft()

        card.append(card.popleft())
    return card[0]


print(card_shuffle(queue))

# ---- 재귀 방식 -----


# from collections import deque
# 
# num = int(input())
# queue = deque()
# for i in range(1, num + 1):
#     queue.append(i)
# 
# 
# def card_shuffle(card):
#     if len(card) == 1:
#         return card[0]
#     card.popleft()
# 
#     card.append(card.popleft())
#     return card_shuffle(card)
# 
# 
# print(card_shuffle(queue))

 

프린터 큐

프린터를 하면서 반복하면서 카운터를 넣어주는 방법으로 했습니다. 

from collections import deque, defaultdict


def printer(paper, imp, value):
    counter = 0
    while paper:
        if imp[0] == max(imp):
            if paper[0] == value:
                return counter + 1
            paper.popleft()
            imp.popleft()
            counter += 1
        else:
            paper.append(paper.popleft())
            imp.append(imp.popleft())


T = int(input())
for _ in range(T):

    num, index = map(int, input().split())
    papers = deque()
    importance = deque()

    for i in range(num):
        papers.append(i)
    for i in map(int, input().split()):
        importance.append(i)
    index_value = papers[index]

    print(printer(papers, importance, index_value))

 

최소 힙

이 부분은 반복문에 입력을 받으면 시간 초과가 나는 부분이 문제 였습니다

일반적으로 사용을 할 때에는 input을 사용해도 무관하지만 큰 반복이 필요한 부분에서는 
int(sys.stdin.readline())를 사용해 주는 것이 좋다고 합니다!
그리고 import sys를 같이 해주어야지 에러가 발생하지 않으므로 함께 사용해 주어야 합니다.

# Code
import sys

# 표준 입력을 파일로 설정
# sys.stdin = open("input.txt", "r")
import heapq


n = int(input())

heap = []


while n > 0:
    a = int(sys.stdin.readline())
    if a == 0:
        if len(heap) == 0:
            print(0)
        else:
            print(heapq.heappop(heap))

    else:
        heapq.heappush(heap, a)
    n -= 1

 

최대 힙

이 부분은 반대로 생각을 하면 편했습니다

에 초에 값을 넣을 때 음수의 값으로 넣어주고 찾을 때 가장 낮은 값을 찾고 다시 음수를 붙여서 
꺼내면 가장 큰 값이 됩니다.

# Code
import sys

# 표준 입력을 파일로 설정
sys.stdin = open("input.txt", "r")
import heapq


n = int(input())

heap = []


while n > 0:
    a = int(sys.stdin.readline())
    if a == 0:
        if len(heap) == 0:
            print(0)
        else:
            print(-heapq.heappop(heap))

    else:
        heapq.heappush(heap, -a)
    n -= 1

 

 

카드 합체 놀이

 

힙을 이용해서 꺼내고 합체하고 다시 넣기를 하면 쉽게 할 수 있습니다.

# Code
import sys

# 표준 입력을 파일로 설정
sys.stdin = open("input.txt", "r")
import heapq


n, m = map(int, input().split())

heap = []
for i in map(int, input().split()):
    heapq.heappush(heap, i)

while m > 0:
    a = heapq.heappop(heap)
    b = heapq.heappop(heap)
    heapq.heappush(heap, a + b)
    heapq.heappush(heap, a + b)
    m -= 1

print(sum(heap))

 

---

오늘은 오후에 예비군이 있어서 아쉽게도 오전밖에 못했지만 다행이 문제가 잘 풀려서 그런지 문제를 다 풀고 갈 수 있어서 기분이 좋습니다 ^^